Lyapunov-control-inspired strategies for quantum combinatorial optimization

The prospect of using quantum computers to solve combinatorial optimization problems via the quantum approximate optimization algorithm (QAOA) has attracted considerable interest in recent years. However, a key limitation associated with QAOA is the need to classically optimize over a set of quantum circuit parameters. This classical optimization can have significant associated costs and challenges. Here we provide an expanded description of Lyapunov control-inspired strategies for quantum optimization, as presented in [Magann et al., Phys. Rev. Lett. 129, 250502 (2022)], that do not require any classical optimization effort. Instead, these strategies utilize feedback from qubit measurements to assign values to the quantum circuit parameters in a deterministic manner, such that the combinatorial optimization problem solution improves monotonically with the quantum circuit depth. Numerical analyses are presented that investigate the utility of these strategies towards MaxCut on weighted and unweighted 3-regular graphs, both in ideal implementations and in the presence of measurement noise. We also discuss how how these strategies compare with QAOA and how they may be used to seed QAOA optimizations in order to improve performance for near-term applications, and we explore connections to quantum annealing.

Figure 1

The performance of FALQON, as quantified by the approximation ratio $r_{\text{A}}$ in (a) and the success probability $\varphi$ in (b) is shown for different values of $n$ as a function of layer $k$, where each layer is formed by an application of the problem Hamiltonian, $H_{\mathrm{p}}$, and a driver Hamiltonian, $H_{\mathrm{d}}$, defined according to Eqs. (45) and (46), respectively. This leads to full circuits with an alternating structure, as per Eq. (30). The solid curves of different colors show the mean results for MaxCut on unweighted 3-regular graphs over a set of different graphs at each problem size $n$, where the latter denotes the number of vertices (equivalently, the number of qubits) of the graph. For $n=8,10$, all possible graphs are considered; for $n=12,14,16$, 50 graphs are considered at each problem size. The dotted curves show mean results for weighted 3-regular graphs, where edge weights are assigned to each graph, selected from a uniform distribution between 0 and 2. The solid black lines show the reference values $r_A=0.932$ and $\varphi =0.25$. In (c), the mean values of $\beta$ are plotted as a function of layer.

Figure 2

Performance of FALQON using the iterative QLC approach, applied to a weighted 3-regular graph with $n=8$ vertices. Three iterations are shown, using a time step of $\mathrm{\Delta }t=0.012$. In (a) and (b), the approximation ratio, $r_{\text{A}}$ and the success probability, $\varphi$ are plotted as a function of layer, respectively. Panel (c) shows how the associated $\beta$ curves are refined at each iteration of the procedure.

Figure 3

Performance of FALQON on an instance of MaxCut on an unweighted, 3-regular graph with $n=8$ vertices in the presence of sampling noise. The time step is set to $\mathrm{\Delta }t=0.034$. In panel (a), the approximation ratio $r_{\text{A}}$ is plotted as a function of layer when $m=2,5,20$, and 50 measurement samples are used to evaluate each of the expectation values $A_k$, $k=1,\cdots ,400$. The solid black curves show the ideal, noiseless reference case. The remaining solid curves represent the mean taken over 100 realizations of this sampling process using different numbers of measurement samples, $m$; the shading shows the associated standard deviation over these realizations. Panels (b) and (c) show analogous results for the success probability, $\varphi$, of measuring the 2-degenerate ground state, and the circuit parameter, $\beta$, respectively.

Figure 4

Numerical analysis of the performance of QAOA for an instance of MaxCut on an unweighted, 3-regular graph with $n=8$ vertices; the instance of MaxCut considered here is the same that is considered in the analysis presented in Fig. 3. For this analysis, we simulate implementations of QAOA that scan over $k=1,2,\cdots ,25$ layers. A series of 100 realizations are performed at each value of $k$, in which the initial circuit parameter values are selected at random, and $q=1000$ iterations of SPSA are performed in order to optimize the circuit parameters. SPSA makes two calls to the objective function per iteration, and for each of these calls, we consider estimating the value of $\langle H_{\mathrm{p}}\rangle$ using $m=10$, $m=1000$, and $m=\infty$ samples, where the latter corresponds to the case of ideal measurements and perfect resolution of the expectation value $\langle H_{\mathrm{p}}\rangle$. The performance of QAOA for each pair of $(m,k)$ values is then quantified by the approximation ratio, $r_A$, and the success probability, $\varphi$, in panels (a) and (b), respectively. In each panel, the dotted curves and shaded regions show the mean and standard deviations computed over the realizations, respectively, as a function of $k$ for each value of $m$. Meanwhile, the gray horizontal lines denote the references values of $r_A=0.932$ and $\varphi =0.25$.

Figure 5

Performance of MaxCut on ensembles of 3-regular graphs with $n$ vertices for $n\in \{8,10,12,14\}$ for FALQON, $\mathrm{FALQON}+$, and multistart QAOA for 10-layer circuits, quantified by (a) the approximation ratio $r_{\text{A}}$ and (b) the success probability $\varphi$, where ${\mathrm{QAOA}}_{max}$, ${\mathrm{QAOA}}_{\mathrm{med}}$, and ${\mathrm{QAOA}}_{min}$ denote distributions of maximum, median, and minimum QAOA results, respectively. In both figures, the color-shaded boxes and encompassed horizontal line represent the interquartile range and the median value of the data, respectively, while the whiskers extend out to 1.5 of the interquartile range; points beyond this range are identified as “outliers” (represented as gray diamond symbols).

Figure 6

Comparison of FALQON and corresponding $\mathrm{FALQON}+$ parameters for example instances of 3-regular graphs with $n$ vertices for $n=8$ (a), $n=10$ (b), $n=12$ (c), and $n=14$ (d). Orange and black diamonds denote FALQON ${\beta }_k\mathrm{\Delta }t$ and ${\gamma }_k=\mathrm{\Delta }t$ parameters; red and blue circles denote $\mathrm{FALQON}+$ ${\beta }_k$ and ${\gamma }_k$ parameters, as described in Eq. (53). Because each FALQON and QAOA circuit layer contains a sequence of unitary operations, i.e., $U_{\mathrm{d}}\left({\beta }_k\right)U_{\mathrm{p}}\left({\gamma }_k\right)$ in Eqs. (2) and (23), we plot ${\gamma }_k$ at $k$ and ${\beta }_k$ at $k+1/2$ for clarity.

Figure 7

The population in the ground state, $\varphi$, and the population in the instantaneous ground state, ${\varphi }_{\mathrm{inst}}$, are plotted as a function of layer, for an application of FALQON to MaxCut on an unweighted 3-regular graph with $n=8$ vertices.

Figure 8

The mean digitized time $T=2k\mathrm{\Delta }t$ needed to achieve the reference values of $r_{\text{A}}=0.932$ (brown) and $\varphi =0.25$ (black) using a FALQON-inspired annealing schedule is shown for the unweighted MaxCut problems considered in Fig. 1. The mean is taken over the set of unweighted, 3-regular graphs that are considered at each problem size $n$, and the error bars show the associated standard deviations.

Figure 9

(a) The mean approximation ratios, $r_A$, obtained by FALQON (solid curves) and a linear quantum annealing schedule (dotted curves) for MaxCut on unweighted, 3-regular graphs with $n=8,10,12,14$ vertices. The mean is taken over the set of different graphs that are considered at each problem size $n$. For the linear quantum annealing schedule, $T$ is chosen to be the time when FALQON reaches the reference value $r_{\text{A}}=0.932$ for each value of $n$. This reference value is plotted as a horizontal black line. Panel (b) shows the corresponding results for the success probabilities, $\varphi$.

Figure 10

Typical behavior when the time step $\mathrm{\Delta }t$ is chosen to be too large, leading to a violation of the QLC criterion that $\langle H_{\mathrm{p}}\rangle$ decreases monotonically with respect to layer, $k$. In (a) the behavior of the approximation ratio, $r_{\text{A}}$, and the success probability, $\varphi$, are shown, with the violation in monotonicity occurring around 100 layers. In (b) the associated behavior of the circuit parameter $\beta$ is plotted, indicating that the violation of the QLC criterion corresponds to the creation of rapid oscillations in $\beta$.

Figure 11

The performance of FALQON, as quantified by the approximation ratio $r_{\text{A}}$ in (a) and the success probability $\varphi$ in (b), is shown as a function of the layer $k$ for different qubit counts $n$ on a log-log scale. The same results are plotted on a linear scale in Fig. 1. The solid curves show the average results for unweighted 3-regular graphs, and the dotted curves show average results for weighted 3-regular graphs.