Double-bracket quantum algorithms

Recently Marek Gluza visited SUTD to give a seminar on double-bracket quantum algorithms. This is an interesting family of quantum optimization algorithms based on Riemannian geometry, which diagonalize an operator (or minimize an energy) using gradient descent in the space of unitary operators. For example, minimization of energy via this gradient descent is realized as the flow,

$$ \partial_t \rho = [ [\rho (t), H], \rho(t) ], $$

where the first commutator $[\rho(t), H]$ is the energy gradient in the space of unitary operators - the direction that locally minimises the energy of the state $\rho(t)$ - and the second commutator evolves $\rho(t)$ in this direction. In other words, this is a nonlinear evolution governed by the effective time-dependent Hamiltonian $H_{\mathrm{eff}} = [\rho(t),H]$. Similar flows were introduced by R. W. Brockett in the 1990s as a way to use dynamical systems to diagonalize matrices. When implemented with a finite step size $s$, this flow recursively generates better approximations to the ground state as

$$ \rho_{k+1} =  e^{s [\rho, H]} \rho_k.$$

Because of the recursion (you need to first generate $\rho_k$ before applying the next set of gates to make $\rho_{k+1}$), the circuit depth grows exponentially with the number of steps. On the other hand, in contrast to variational quantum algorithms (where one has to measure gradients of all the classical control parameters of the circuit), to implement the double-bracket flow you only need specify the initial state $\rho_0$ and the step size $s$, avoiding big problems such as barren plateaux and choosing an appropriate variational ansatz. Double-bracket flow is guaranteed to converge, so it can pick up after other methods get stuck.

Marek noted that because of the circuit depth blow up, a warm start is essential to get the best performance. For example, one might optimize a shallow variational quantum circuit such as QAOA to obtain a low energy state, followed by a few steps of double-bracket flow to home in on the ground state.

This is a great example of how quantum computing can draw inspiration from classical algorithms and control theory, giving a fresh application of the humble idea of optimization via gradient descent! 

The slides are available here.