We embed 1-layer QAOA circuits into the larger class of parametrized instantaneous quantum polynomial circuits to produce an improved variational quantum algorithm for solving combinatorial optimization problems. The use of analytic expressions to find optimal parameters classically makes our protocol robust against barren plateaus and hardware noise. The average overlap with the ground state scales as 2−0.31(2)N with the number of qubits N for random Sherrington-Kirkpatrick (SK) Hamiltonians of up to 29 qubits, a polynomial improvement over 1-layer QAOA. Additionally, we observe that performing variational imaginary time evolution on the manifold approximates low-temperature pseudo-Boltzmann states. Our protocol outperforms 1-layer QAOA on the recently released Quantinuum H2 trapped-ion quantum hardware and emulator, where we obtain an average approximation ratio of 0.985 across 312 random SK instances of 7 to 32 qubits, from which almost 44% are solved optimally using only 4 to 1208 shots per instance. Published by the American Physical Society 2024
We embed 1-layer QAOA circuits into the larger class of parametrized instantaneous quantum polynomial circuits to produce an improved variational quantum algorithm for solving combinatorial optimization problems. The use of analytic expressions to find optimal parameters classically makes our protocol robust against barren plateaus and hardware noise. The average overlap with the ground state scales as 2−0.31(2)N with the number of qubits N for random Sherrington-Kirkpatrick (SK) Hamiltonians of up to 29 qubits, a polynomial improvement over 1-layer QAOA. Additionally, we observe that performing variational imaginary time evolution on the manifold approximates low-temperature pseudo-Boltzmann states. Our protocol outperforms 1-layer QAOA on the recently released Quantinuum H2 trapped-ion quantum hardware and emulator, where we obtain an average approximation ratio of 0.985 across 312 random SK instances of 7 to 32 qubits, from which almost 44% are solved optimally using only 4 to 1208 shots per instance. Published by the American Physical Society 2024
The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.
Variational quantum algorithms involve training parametrized quantum circuits using a classical coprocessor. An important variational algorithm, designed for combinatorial optimization, is the quantum approximate optimization algorithm. Realization of this algorithm on any modern quantum processor requires either embedding a problem instance into a Hamiltonian or emulating the corresponding propagator by a gate sequence. For a vast range of problem instances this is impossible due to current circuit depth and hardware limitations. Hence we adapt the variational approach---using ion-native Hamiltonians---to create ansatz families that can prepare the ground states of more general problem Hamiltonians. We analytically determine symmetry protected classes that make certain problem instances inaccessible unless this symmetry is broken. We exhaustively search over six qubits and consider up to 20 circuit layers, demonstrating that symmetry can be broken to solve all problem instances of the Sherrington-Kirkpatrick Hamiltonian. Going further, we numerically demonstrate training convergence and levelwise improvement for up to 20 qubits. Specifically these findings widen the class problem instances which might be solved by ion based quantum processors. Generally these results serve as a test bed for quantum approximate optimization approaches based on system native Hamiltonians and symmetry protection.
Advances in quantum algorithms suggest a tentative scaling advantage on certain combinatorial optimization problems. Recent work, however, has also reinforced the idea that barren plateaus render variational algorithms ineffective on large Hilbert spaces. Hence, finding annealing protocols by variation ultimately appears to be difficult. Similarly, the adiabatic theorem fails on hard problem instances with first-order quantum phase transitions. Here we show how to use the spin coherent-state path integral to shape the geometry of quantum adiabatic evolution, leading to annealing protocols at polynomial overhead that provide orders-of-magnitude improvements in the probability to measure optimal solutions, relative to linear protocols. These improvements are not obtained on a controllable toy problem but on randomly generated hard instances (Sherrington-Kirkpatrick and maximum 2-satisfiability), making them generic and robust. Our method works for large systems and may thus be used to improve the performance of state-of-the-art quantum devices.
Solving combinatorial optimization problems using variational quantum algorithms (VQAs) has emerged as a promising research direction. Since the introduction of the Quantum Approximate Optimization Algorithm (QAOA), numerous variants have been proposed to enhance its performance. QAOA was later extended to the Quantum Alternating Operator Ansatz (QAOA+), which generalizes the initial state, phase-separation operator, and mixer to address constrained problems without relying on the standard Quadratic Unconstrained Binary Optimization (QUBO) formulation. However, QAOA+ often requires additional ancilla qubits and a large number of multi-controlled Toffoli gates to prepare the superposition of feasible states, resulting in deep circuits that are challenging for near-term quantum devices. Furthermore, VQAs are generally hindered by issues such as barren plateaus and suboptimal local minima. Recently, Quantum Imaginary Time Evolution (QITE), a groundstate preparation algorithm, has been explored as an alternative to QAOA and its variants. QITE has demonstrated improved performance in quantum chemistry problems and has been applied to unconstrained combinatorial problems such as MaxCut. In this work, we apply the variational form of QITE (VarQITE) to solve the Multiple Knapsack Problem (MKP), a constrained problem, using a Max-Cut-tailored ansatz. To the best of our knowledge, this is the first attempt to address constrained optimization using VarQITE. We show that VarQITE achieves significantly lower mean optimality gaps compared to QAOA and other conventional methods. Moreover, we demonstrate that scaling the Hamiltonian coefficients can further reduce optimization costs and accelerate convergence.
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p . While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within ( 1 − ϵ ) times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2 p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O ( 16 p ) complexity. We evaluate the formula up to p = 12 , and find that the QAOA at p = 11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n → ∞ , measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024