By Jernej Rudi Finžgar, Aron Kerschbaumer, Christian Mendl, Helmut Katzgraber, and Martin Schuetz | on 26 MAR 2024
The optimization of processes and operations is a critical challenge for businesses in just about any industry sector. Often it involves so-called combinatorial optimization problems that are simple to conceptualize yet solving them optimally yields some of the most difficult computational tasks known. In some cases, the problem’s difficulty lies in the presence of feasibility constraints – a set of rules that determine whether a proposed solution can be realized in practice. You can see an example of this in a previous post about robot motion optimization.
Because of their computational complexity and far-reaching importance, the last few decades have seen much research invested in exploring alternative computational paradigms for solving combinatorial optimization problems. One particularly exciting avenue has been sparked by the recent advent of quantum computing. Investigating the potential benefits of quantum computing for combinatorial optimization has led to the development of various algorithmic approaches, both for digital and analog devices.
In this post we present a hybrid, quantum-informed recursive optimization (QIRO) algorithm that can help ensure solution feasibility in constrained optimization problems. We show how QIRO leverages quantum resources within problem-specific classical reduction steps that recursively simplify the problem. We showcase our scheme with experiments on the QuEra Aquila neutral atom quantum device available through Amazon Braket – the quantum computing service of AWS.
Quantum optimization for constrained problems
In most existing quantum optimization approaches one needs to reformulate the given optimization problem in terms of a Hamiltonian – the quantum mechanical equivalent of a cost function in a combinatorial optimization problem – which can in turn be implemented on the desired quantum hardware. This is typically performed by first (classically) reformulating the combinatorial optimization problem as an instance of a quadratic unconstrained binary optimization (QUBO) problem:
In what has become a standard procedure in quantum optimization (see [1, 2]), the QUBO instance is then promoted to a quantum Hamiltonian by transforming the binary variables xi into quantum mechanical operators Zi, while the matrix Qij and the vector bi are classical (real) parameters encoding the particular problem at hand. However, as indicated by its name, QUBO instances are natively only equipped to handle unconstrained combinatorial optimization problems.
Let’s illustrate some of the potential pitfalls of the QUBO encoding for constrained problems for the specific case of the maximum independent set (MIS) problem. In the MIS problem we are tasked with finding the largest independent (i.e., mutually unconnected) set of nodes in a graph; see Figure 1.
Figure 1 A graph with its maximum independent set (MIS) indicated with the green-colored nodes. Note that no two green-colored nodes are connected by an edge, which means that the set is independent. The largest such set of unconnected nodes in a graph corresponds to the MIS.
Despite its simple formulation, the problem finds many applications in diverse areas like vehicle routing, antenna placement, or portfolio optimization [3]. Further, it is a constrained problem which belongs to the class of so-called NP-hard problems. These are problems for which it is widely believed that no classical algorithm exists that can solve all instances efficiently.
In a QUBO formulation of the MIS problem, one is tasked with minimizing the following expression over binary variables xi ∈{0,1}:
Here, the first term counts the number of vertices included in the proposed candidate set, and the second term enforces the independence constraint. The coefficient λ needs to be fixed to a number greater than one to ensure that the bit strings x that minimize H correspond to maximum independent sets of the graph.
However, even in this simple case, the exact value of λ needs to be set carefully – see Figure 2. Choose it too small, and the low energetic difference between feasible and infeasible solutions will make the (quantum) algorithm susceptible to experimental noise which will lead to the generation of infeasible candidate solutions. Conversely, if the λ coefficient is too large, the penalty term will move infeasible solutions out of optimization algorithm’s reach, preventing it from using them as stepping stones in between feasible solutions during the search. Moreover, implementing a Hamiltonian with terms on largely different energy scales is a formidable technical challenge that might induce additional errors. For these reasons we generally need to fine-tune the magnitude of the penalty term. While this can typically be done relatively effectively for such a simple constraint, this guiding example illustrates the potential pitfalls one may encounter in more complex cases.
Figure 2 A schematic visualization of the spectrum of a QUBO formulation of the MIS problem, highlighting the issues that an inappropriately set penalty term λ can cause. Here, orange (black) lines correspond to infeasible (feasible) candidate solutions.
Quantum-informed recursive optimization (QIRO)
To address this feasibility problem with constrained problems from the beginning, in Ref [4] we propose a novel hybrid quantum-classical family of quantum-informed recursive optimization (QIRO) algorithms (see Figure 3).
Here, we present a member of this family of algorithms, one that is tailored to solve MIS problems. This algorithm operates by recursively simplifying the problem based on information obtained from a quantum device, which is used to prepare a superposition of (low energy) candidate solutions to the optimization problem. The information of the quantum state is extracted by measuring observables that we are interested in (in our case the Pauli Z operators). This can be done with any of the standard quantum optimization approaches, like the quantum approximate optimization algorithm (QAOA) [5], which runs on digital quantum computers, as well as analog approaches such as quantum annealing on Rydberg atom arrays [6,7], previously discussed on this blog here and here. The iterative problem simplification is then performed on a classical device and enables us to directly integrate the feasibility constraints into the algorithm.
Figure 3 Scheme illustrating the quantum-informed recursive optimization (QIRO) algorithm. Quantum algorithms such as QAOA or quantum adiabatic protocols run on quantum resources are used to measure correlations between variables, which are in turn used to inform update rules that recursively simplify the problem by enforcing constraints or exploiting other problem-specific features.
Concretely, here is how QIRO works in the case of the maximum independent set: If measurements of a low-energy quantum state indicates that a certain node belongs to the independent set (xi = 1), we can assign the node to the set. After this, none of the neighboring nodes of the chosen node can simultaneously belong to the independent set, as to not violate the feasibility constraint. Hence, we remove these nodes from the graph, before preparing a new low-energy state for this simplified graph; see case (a) in Fig. 4. Conversely, if the results of the measurement indicate that a certain node is not in the independent set (xi = 0), we simply remove it, as no violations will be caused; see panel (b) in Fig. 4.
Moreover, we use the relative value of variables as captured by their correlation coefficient, to perform problem simplifications. If the variables are positively correlated, we know that they are predominantly in the xi = xj = 0 state, because xi = xj = 1 would violate the feasibility constraint. Thus, we remove both nodes. If variables are anticorrelated, we know that at least one of them is in the independent set – however, we cannot be certain which one it is, solely based on the observed correlation. Therefore, we remove nodes that are connected to both anticorrelated nodes, as we know at least one of them will likely belong to the independent set; see Fig. 4d.
The independence constraint plays a central role in the proposed simplification rules. In fact, it is easy to see that every update step is designed such that no violations of the independence constraint occur. As such we are guaranteed to obtain feasible solutions at the end of the algorithm.
Figure 4 MIS update rules; case (a) described in the main text corresponds to a node included in the independent set, leading to the removal of all adjacent nodes. In case (b) a node is removed from the graph due to its rare appearance in candidate solutions (as suggested by measured quantum correlations). Cases (c) and (d) correspond to cases where the assignments of the two nodes connected by the highlighted edge are correlated and anticorrelated, respectively. In the correlated case, both variables are removed, as the only positively correlated assignment consistent with the independence constraint is that of neither node belonging to the solution. In the anticorrelated case, one node is guaranteed to be in the independent set, meaning that any node that is connected to both nodes are removed.
Experiments on neutral atom quantum hardware
We set out to test this algorithm using different sources of correlations. Specifically, we focused on using classical simulations of shallow (depth p=1) QAOA circuits and adiabatic protocols on the QuEra Aquila neutral atom quantum computer, accessed through Amazon Braket. Because the simplification rules in both versions of QIRO are held equal, we can use the performance of the QIRO algorithm to infer the merit of the respective sources of correlations (QuEra & QAOA) for suggesting the simplifications. Moreover, we used the minimal degree greedy (Min. greedy) algorithm as a classical benchmark since it likewise operates by recursively simplifying the problem graph by greedily choosing the node with the minimal degree and includes it in the candidate solution while preserving feasibility [8].
Figure 5 Comparison of the approximation ratios, defined as the ratio between the size of the independent set found by the respective algorithms (|IS|) and the maximum independent set (|MIS|), for ten graph instances with 137 nodes, akin to the one displayed in Fig. 1. Different colors correspond to different algorithms, with the error bars indicating the best and worst performance across five independent runs.
The results shown in Fig. 5 indicate that QIRO informed by correlations from the QuEra device outperforms QIRO with QAOA correlations, as well as the greedy benchmark – albeit we should be mindful of the relatively small sample size. We also have to keep in mind that the QAOA correlations were generated at its lowest depth of p=1; despite that, it is still encouraging to see an actual experimental implementation on today’s quantum hardware beat an error-free, classical numerical simulation.
Outlook
The modular design of QIRO offers several routes for potential improvements. Beginning with the quantum component, it would likely be beneficial to improve the adiabatic protocols used to generate the correlations with previous techniques, such as the use of Bayesian optimization [9], as discussed in a previous post on that topic.
Finally, one may tailor the update rules to the specific optimization problem in question – for example, in the original publication [4], we also proposed specific update rules for a maximum satisfiability (Max-SAT) problem. Note that the results shown here merely serve as a simple proof of concept. We are excited to see the broader quantum optimization community further improve on these results and apply related algorithms to one of the many important constrained optimization problems.
References
[1] Lucas, Andrew. 2014. ‘Ising Formulations of Many NP Problems’. Frontiers in Physics 2. doi: 10.3389/fphy.2014.00005.
[2] Glover, F., Kochenberger, G., and Du, Y., “A Tutorial on Formulating and Using QUBO Models, arXiv:1811.11538.
[3] Wurtz, Jonathan, Pedro Lopes, Nathan Gemelke, Alexander Keesling, and Shengtao Wang. 2022. ‘Industry Applications of Neutral-Atom Quantum Computing Solving Independent Set Problems’.
[4] Finžgar, J. R., Kerschbaumer, A., Schuetz, M. J. A., Mendl, C. B., and Katzgraber, H. G., “Quantum-Informed Recursive Optimization Algorithms”, arXiv:2308.13607.
[5] Farhi, E., Goldstone, J., and Gutmann, S., “A Quantum Approximate Optimization Algorithm”, arXiv:1411.4028.
[6] Pichler, Hannes, Sheng-Tao Wang, Leo Zhou, Soonwon Choi, and Mikhail D. Lukin. 2018. ‘Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays’. doi: 10.48550/arXiv.1808.10816.
[7] Ebadi, S., A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J. G. Liu, R. Samajdar, X. Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S. T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. 2022. ‘Quantum Optimization of Maximum Independent Set Using Rydberg Atom Arrays’. Science 376(6598):1209–15. doi: 10.1126/science.abo6587.
[8] Halldórsson, M.M. , Radhakrishnan, J. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 145–163 (1997). 10.1007/BF02523693
[9] Finžgar, Jernej Rudi, Martin J. A. Schuetz, J. Kyle Brubaker, Hidetoshi Nishimori, and Helmut G. Katzgraber. 2023. ‘Designing Quantum Annealing Schedules Using Bayesian Optimization’.
Leave a Reply