Quantum-Informed Recursive Optimization Algorithms

We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for combinatorial optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps that recursively simplify the problem. These reduction steps address the limitations of the quantum component (e.g., locality) and ensure solution feasibility in constrained optimization problems. Additionally, we use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware. We showcase the capabilities of our approach by informing QIRO with correlations from classical simulations of shallow circuits of the quantum approximate optimization algorithm, solving instances of maximum independent set and maximum satisfiability problems with hundreds of variables. We also demonstrate how QIRO can be deployed on a neutral atom quantum processor to find large independent sets of graphs. In summary, our scheme achieves results comparable to classical heuristics even with relatively weak quantum resources. Furthermore, enhancing the quality of these quantum resources improves the performance of the algorithms. Notably, the modular nature of QIRO offers various avenues for modifications, positioning our work as a template for a broader class of hybrid quantum-classical algorithms for combinatorial optimization.

Popular Summary

Improving the efficiency of everyday tasks, whether it’s streamlining an assembly line or planning efficient delivery routes, typically involves solving combinatorial optimization problems. Because solving combinatorial problems involves choosing the best configuration of variables from a vast search space, they present some of the most difficult problems in computer science and operations research. This has given rise to the field of quantum optimization, which investigates whether harnessing quantum computers can provide more efficient algorithms for combinatorial optimization. Currently, quantum computers face significant limitations not only in scale but also in their applicability to real-world problems. In this work we introduce a family of hybrid quantum-classical algorithms designed to address some of these challenges.

Here, we use correlations obtained from quantum resources to inform problem-specific classical update rules that solve the optimization problem via recursive simplification. We demonstrate the performance of the method through simulations as well as actual runs on a neutral-atom quantum device. We observe that higher quality quantum correlations lead to an improved performance of the algorithm, suggesting that advancements in hardware could unlock further performance gains.

Figure 1

Schematic visualization of the core principles of the quantum-informed recursive optimization (QIRO) algorithm presented in this work. Quantum resources (e.g., QAOA) are used to obtain information, e.g., in the form of one-point and two-point correlations. This information is then used to simplify the problem through problem-specific classical update rules. Here we exemplify the update rules with simple examples for the maximum independent set and satisfiability problems—details on the update rules can be found in Sec. 3b. The (simplified) problem obtained by means of the classical update rules is then used to restart the cycle. The algorithm terminates when the problem has been fully simplified.

Figure 2

MIS update rules described in the main text carried out on an example graph. Panels (a) and (b) show reduction rules for the case of a positive and negative one-point correlation, respectively. Analogously, panels (c) and (d) show the respective reduction rules for the case of a positive and negative two-point correlation.

Figure 3

Schematic visualization of the backtracking procedure used to obtain improved solutions. Starting from the original problem $P^{(0)}$ and an empty solution $S^{(0)}$, we perform a series of reductions (red arrows and nodes) that recursively simplify the problem, until the first candidate solution (${\mathrm{Solution}}^{(0\cdots 00)}$) is reached. This corresponds to applying QIRO as outlined in Algorithm 4. Backtracking, as visualized by the dashed teal arrows, then amounts to revisiting reduction steps made along the path. At the chosen ancestor node we have backtracked to, we can then make an alternative reduction, here denoted by $\overline{\mathtt{\text{Reduce}}}$ (see the black arrows). Concretely, $\overline{\mathtt{\text{Reduce}}}$ amounts to reversing the initially made decision, not needing extra calls to the quantum device. In this work, we limit ourselves to making a binary decision at each node. As such, we can label the reduced problem and partial solution at each node with a binary string encoding the path connecting the node to the original problem node. Each 0 (1) in the superscript labeling $P$ and $S$ corresponds to one application of $\mathtt{\text{Reduce}}$ ($\overline{\mathtt{\text{Reduce}}}$) starting from the original problem.

Figure 4

System size scaling for the success rate of the random greedy (“Rnd. greedy”), minimal degree greedy (“Min. greedy”), RQAOA, and QIRO for Erdős-Rényi graphs with different expectation values of the average degree. At each system size and average degree 50 graphs were generated, and ten runs of each algorithm were performed. We report the median percentage of graphs for which we find independent sets of the size found by the classical ReduMis benchmark algorithm. The error bars denote the minimum and maximum performance observed across the ten runs. Note that the results for QIRO and RQAOA are obtained using simulations of QAOA at depth $p=1$.

Figure 5

(a) An example unit disk graph with 137 nodes. Teal nodes indicate a maximum independent set of size $|\mathrm{MIS}|=45$. (b) Data for 500 random unit disk graphs with 137 nodes, comparing the robustness of RQAOA and QIRO, for two different magnitudes of the penalty term $\lambda$ [see Eq. (1)]. The upper row shows the fraction of valid solutions obtained by each algorithm. The lower row displays the ratio between the size of the largest independent set (IS) found and the maximum independent set (MIS) size. Both the validity and $|\mathrm{IS}|/\mathrm{MIS}|$ are plotted with respect to the quality of the $p=1$ QAOA parameters, with parameters at $q=0.0$ corresponding to the optimal parameters, and higher values of $q$ corresponding to worse parameters (see the main text). We note that we only report the approximation ratio achieved by RQAOA if the solution produced by it is valid (i.e., corresponds to an independent set).

Figure 6

Approximation ratio comparing the size of the independent set $|\mathrm{IS}|$ found by QIRO with correlations from the QuEra neutral atom quantum processor (QIRO QuEra), and correlations from numerical simulations of $p=1$ QAOA (QIRO QAOA), with the size of the maximum independent set $|\mathrm{MIS}|$. For comparison, the ratios obtained by the minimal degree greedy algorithm (“Min. greedy”) are shown. In instance 1 the obtained approximation ratio of the greedy algorithm is outside of the range of the displayed values with $|\mathrm{IS}|/|\mathrm{MIS}|\approx 0.63$. The median value over five runs is plotted, with error bars showing the best and worst solutions found.

Figure 7

System size scaling of the performance of the different algorithms, at three different values of $\alpha$. At each system size and $\alpha$, 50 random instances were generated with two variables per clause, each variable and its polarity chosen uniformly at random. Parallel tempering (PT) was used to find nearly optimal solutions; we then report the median percentage of instances on which an algorithm performs at least as well as PT across ten independent runs. The error bars indicate the minimal and maximal performance across these ten runs. Simulation details about SA and PT can be found in Appendix pp7.

Figure 8

Time dependency of the Rabi frequency $\mathrm{\Omega }(t)$ and the laser detuning $\mathrm{\Delta }(t)$. We use $t_{\mathrm{f}}=4\text{μ}\mathrm{s}$, ${\mathrm{\Omega }}_{max}=15.8\mathrm{MHz}$, ${\tau }_{\mathrm{\Omega }}=0.1t_{\mathrm{f}}$, ${\mathrm{\Delta }}_{\mathrm{i}}=-30\mathrm{MHz}$, and ${\mathrm{\Delta }}_{\mathrm{f}}=60\mathrm{MHz}$.

Figure 9

The fraction of optimally solved instances by QIRO using QAOA at depths $p\in \{1,2,3\}$, and by the minimal degree greedy algorithm. The height of the bars show the mean fraction across ten runs of the algorithms, with the error bars indicating the best and worst performance across those runs.

Figure 10

Ratio of valid solutions obtained by RQAOA for different qualities of the QAOA parameters $q$ (at $p=1$) and different penalty factors $\lambda$. As in the results in Fig. 5, at each $(q,\lambda )$ the same 50 UDGs of size 137 were generated and ten runs of RQAOA were performed. We here report the ratio valid (i.e., independent) sets found by RQAOA. Black stars indicate values of $(q,\lambda )$ where all found solutions were feasible.