Optimal Control for Quantum Optimization of Closed and Open Systems

Optimization is one of the key applications of quantum computing where a quantum speedup has been an eagerly anticipated outcome. A promising approach to optimization using quantum dynamics is to consider a linear combination $s(t)B+[1-s(t)]C$ of two noncommuting Hamiltonians $B$ and $C$, where $C$ encodes the solution to the optimization problem in its ground state, $B$ is a Hamiltonian whose ground state is easy to prepare, and $s(t)\in [0,1]$ is the bounded “switching schedule” or “path,” with $t\in [0,t_f]$. This approach encompasses two of the most widely studied quantum-optimization algorithms: quantum annealing [QA; continuous $s(t)$] and the quantum approximate optimization algorithm [QAOA; piecewise constant $s(t)$]. While it is notoriously difficult to prove a quantum advantage for either algorithm, it is possible to compare and contrast them by finding the optimal $s(t)$. Here we provide a rigorous analysis of this quantum optimal control problem, entirely within the geometric framework of Pontryagin’s maximum principle of optimal control theory. We extend earlier results, derived in a purely closed-system setting, to open systems. This is the natural setting for experimental realizations of QA and QAOA. In the closed-system setting it was shown that the optimal solution is a “bang-anneal-bang” schedule, with the bangs characterized by $s(t)=0$ and $s(t)=1$ in finite subintervals of $[0,t_f]$, in particular, $s(0)=0$ and $s(t_f)=1$, in contrast to the standard prescription $s(0)=1$ and $s(t_f)=0$ of QA. As an example, we prove that for a single spin-$1/2$, the optimal solution in the closed-system setting is the bang-bang schedule, switching midway from $s\equiv 0$ to $s\equiv 1$. For finite-dimensional environments and without any approximations we identify sufficient conditions ensuring that either the bang-anneal, anneal-bang, or bang-anneal-bang schedules are optimal, and recover the optimality of $s(0)=0$ and $s(t_f)=1$. However, for infinite-dimensional environments and a system described by an adiabatic Redfield master equation we do not recover the bang-type optimal solution. In fact we can only identify conditions under which $s(t_f)=1$, and even this result is not recovered in the fully Markovian limit, suggesting that the pure anneal-type schedule is optimal. Our open-system results have implications for the use of experimental quantum-information processors, which are by necessity noisy, and suggest that in this practical sense the optimal schedules for quantum optimization are likely to be continuous.

Figure 1

Single-qubit case. Optimal trajectory on the Bloch sphere with initial condition ${\mathit{v}}_0=(-1,0,0{)}^T$. Here $t_f=0.95\pi$ so the ground state of $C$, corresponding to the point $(0,0,-1)$, is not reached exactly.

Figure 2

Switching diagram for optimal control candidates. Starting from the point $(\lambda ,0)$ the dynamics stay on the line $x_C=\lambda$. In principle, even negative values of $x_B$ can be attained, but eventually the point $(\lambda ,\lambda )$ must be reached, followed by an alternation of vertical and horizontal lines (where, in principle, one can also extend to negative values of $x_C$) through $(\lambda ,\lambda )$ with time intervals where the dynamics do not move from $(\lambda ,\lambda )$, representing the singular arcs. In the last interval, the dynamics follow a horizontal line (with $s\equiv 1$) reaching the point $(x_C,x_B)=(0,\lambda )$.

Figure 3

(a) Behavior of the optimal cost in the regular case where the reachable set increases with the final time at the optimal point $\mathit{\rho }(t_f)$. In this case we expect $\lambda >0$. (b) Behavior of the optimal cost in the case where the reachable set increases with the final time but not at the optimal final point $\mathit{\rho }(t_f)$. In this case we expect $\lambda =0$.