Abstract The Quantum Alternating Operator Ansatz (QAOA) and Quantum Annealing (QA) are quantum algorithms that are both based on the adiabatic theorem and both have the goal of sampling the optimal solution(s) of combinatorial optimization problems. Quantum annealing has been physically instantiated on D-Wave devices using superconducting flux qubits, and QAOA can be programmed on digital gate-model quantum computers such as the programmable superconducting transmon qubit devices manufactured by IBM Quantum, for instance ibm_washington. QAOA and QA address the same types of problems, but it is unclear how they will scale to large problem sizes and to larger and higher-fidelity quantum computers. In this article, we present a direct comparison between QAOA, one and two rounds, run on all 127 qubits of ibm_washington and QA run on D-Wave Advantage_system4.1 and Advantage_system6.1. The problems which allow for this comparison are random Ising model problems whose connectivity matches the heavy hexagonal lattice topology of ibm_washington and the Pegasus graph connectivity of the two D-Wave devices. We create two classes of problem instances for this comparison: one with higher order terms (ZZZ variable interactions), linear terms, and quadratic terms, and a separate problem type with only linear and quadratic terms. The QAOA circuits are novel and extremely short depth, with a CNOT depth of 6 per round, which allows whole chip usage of ibm_washington's heavy hexagonal lattice and can be applied to future heavy-hex chips. We also test the effectiveness of the error suppression technique digital dynamical decoupling on the QAOA circuits, allowing one of the largest experimental evaluations of dynamical decoupling to date. The QAOA circuits compiled to ibm_washington are composed of approximately 3,000 gate instructions making these some the largest quantum circuits ever executed on a digital quantum processor. QAOA and QA are compared against the classical heuristic algorithm of simulated annealing and all problem instances are exactly solved using CPLEX in order to evaluate ground state success sampling probability. We find that (i) QA outperforms QAOA on all problem instances, (ii) QAOA samples the problems better than random sampling, and (iii) QAOA parameters exhibit clear parameter concentration across the ensemble of Ising models.
Abstract The Quantum Alternating Operator Ansatz (QAOA) and Quantum Annealing (QA) are quantum algorithms that are both based on the adiabatic theorem and both have the goal of sampling the optimal solution(s) of combinatorial optimization problems. Quantum annealing has been physically instantiated on D-Wave devices using superconducting flux qubits, and QAOA can be programmed on digital gate-model quantum computers such as the programmable superconducting transmon qubit devices manufactured by IBM Quantum, for instance ibm_washington. QAOA and QA address the same types of problems, but it is unclear how they will scale to large problem sizes and to larger and higher-fidelity quantum computers. In this article, we present a direct comparison between QAOA, one and two rounds, run on all 127 qubits of ibm_washington and QA run on D-Wave Advantage_system4.1 and Advantage_system6.1. The problems which allow for this comparison are random Ising model problems whose connectivity matches the heavy hexagonal lattice topology of ibm_washington and the Pegasus graph connectivity of the two D-Wave devices. We create two classes of problem instances for this comparison: one with higher order terms (ZZZ variable interactions), linear terms, and quadratic terms, and a separate problem type with only linear and quadratic terms. The QAOA circuits are novel and extremely short depth, with a CNOT depth of 6 per round, which allows whole chip usage of ibm_washington's heavy hexagonal lattice and can be applied to future heavy-hex chips. We also test the effectiveness of the error suppression technique digital dynamical decoupling on the QAOA circuits, allowing one of the largest experimental evaluations of dynamical decoupling to date. The QAOA circuits compiled to ibm_washington are composed of approximately 3,000 gate instructions making these some the largest quantum circuits ever executed on a digital quantum processor. QAOA and QA are compared against the classical heuristic algorithm of simulated annealing and all problem instances are exactly solved using CPLEX in order to evaluate ground state success sampling probability. We find that (i) QA outperforms QAOA on all problem instances, (ii) QAOA samples the problems better than random sampling, and (iii) QAOA parameters exhibit clear parameter concentration across the ensemble of Ising models.
We investigate and compare the performance of two quantum optimization approaches, the Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, applied to the Minimum Vertex Cover (MVC) problem. The problem is encoded as an and Ising model, and experiments are conducted on IBM’s GenericBackendV2 noisy superconducting qubit simulator and the D-Wave Advantage2 quantum annealer. Performance is evaluated in terms of solution quality, measurement probability, and proportion of valid solutions. The results we obtained show that, within our experimental setting, quantum annealing consistently outperforms its classical counterpart on small instances, while QAOA, though currently limited by simulation constraints, shows promising behavior that improves with increasing circuit depth. As problem size grows, both approaches exhibit sensitivity to parameter choices such as the penalty term and graph density, underscoring the need for careful tuning. These findings suggest that while both paradigms hold potential for combinatorial optimization, further advances in hardware capabilities and parameter calibration will be necessary to achieve reliable performance on larger instances.
Abstract We show that the quantum approximate optimization algorithm (QAOA) for higher-order, random coefficient, heavy-hex compatible spin glass Ising models has strong parameter concentration across problem sizes from 16 up to 127 qubits for p = 1 up to p = 5, which allows for computationally efficient parameter transfer of QAOA angles. Matrix product state (MPS) simulation is used to compute noise-free QAOA performance. Hardware-compatible short-depth QAOA circuits are executed on ensembles of 100 higher-order Ising models on noisy IBM quantum superconducting processors with 16, 27, and 127 qubits using QAOA angles learned from a single 16-qubit instance using the JuliQAOA tool. We show that the best quantum processors find lower energy solutions up to p = 2 or p = 3, and find mean energies that are about a factor of two off from the noise-free distribution. We show that p = 1 QAOA energy landscapes remain very similar as the problem size increases using NISQ hardware gridsearches with up to a 414 qubit processor.
We establish and discuss a number of connections between a digitized version of Quantum Annealing (QA) with the Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi et al. (arXiv:1411.4028) as an alternative hybrid quantum-classical variational scheme for quantum-state preparation and optimization. We introduce a technique that allows to prove, for instance, a rigorous bound concerning the performance of QAOA for MaxCut on a 2-regular graph, equivalent to an unfrustrated antiferromagnetic Ising chain. The bound shows that the optimal variational error of a depth-P quantum circuit has to satisfy εPres≥(2P+2)−1. In a separate work (Mbeng et al., arXiv:1911.12259) we have explicitly shown, exploiting a Jordan-Wigner transformation, that among the 2P degenerate variational minima which can be found for this problem, all strictly satisfying the equality εPres=(2P+2)−1, one can construct a special {\em regular} optimal solution, which is computationally optimal and does not require any prior knowledge about the spectral gap. We explicitly demonstrate here that such a schedule is adiabatic, in a digitized sense, and can therefore be interpreted as an optimized digitized-QA protocol. We also discuss and compare our bound on the residual energy to well-known results on the Kibble-Zurek mechanism behind a continuous-time QA. These findings help elucidating the intimate relation between digitized-QA, QAOA, and optimal Quantum Control.
The emergent practical applicability of the Quantum Approximate Optimization Algorithm (QAOA) for approximate combinatorial optimization is a subject of considerable interest. One of the primary limitations of QAOA is the task of finding a set of good parameters, which is usually done using a variational optimization loop. Parameter transfer, or parameter concentration, is a phenomenon where QAOA angles trained on problem instances that are self-similar tend to perform well for other problem instances from that similar class. This suggests a potentially highly efficient and scalable nonvariational learning method for QAOA angle finding. In this work, we systematically study QAOA parameter transferability from small problem sizes (16 and 27 decision variables) onto large problem instances (up to 156 qubits) for heavy-hex graph Ising models with geometrically local higher-order terms using the Julia based QAOA simulation tool to perform classical angle finding for up to 49 QAOA layers ( p ) . Parameter transfer of the fixed angles is validated using a combination of full state vector, projected entangled pair states, matrix product state, and LOWESA numerical simulations. We find that the QAOA parameter transfer from single instances applied to other (unseen) problem instances does not in general provide monotonically improving performance as a function of p —there are many cases where the performance temporarily decreases as a function of p —but despite this the transferred angles have a general trend of improved expectation value as the QAOA depth increases, in many cases converging close to the true ground-state energy of the 100 + qubit instances. We also sample the hardware-compatible Ising models using the ensemble of transfer-learned QAOA parameters on several superconducting qubit IBM quantum processors with 127, 133, and 156 qubits. We find continuous solution quality improvement of the hardware-compatible QAOA circuits run on the IBM noisy intermediate-scale quantum processors up to p = 5 on , up to p = 9 on , and up to p = 10 on .
The recent advances in the world of quantum technologies have prompted the development of various quantum-based algorithms, some of which are suitable to run on available quantum devices. Two leading candidates in this area are Quantum Annealing (QA) and hybrid quantum-classical variational algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA). In the first part of the Thesis, we re-examine the issue of whether Simulated Quantum Annealing (SQA) with Path Integral Monte Carlo has anything to do with the coherent QA Schrödinger dynamics. We do that by studying the random quantum Ising Chain in a transverse field. In the second part of the Thesis we address the issue of schedule optimization in both {em digitized}-QA and QAOA. Traditional schedule optimization in QA requires spectral information on the problem (e.g., location of the minimum gaps), which is in most cases inaccessible. On the other hand, in QAOA, the issue of schedule optimization --- alias, the optimization of the variational parameters --- is often an expensive task that constitutes a bottleneck for the algorithm. We show that, by combining the framework of QAOA and digitized-QA, optimal digitized-QA protocols can be constructed efficiently. When using this approach, the computational cost of schedule optimization is also significantly reduced, leading to a computational advantage both over a linear-schedule QA, and over an unstructured QAOA search. While studying these issues, we also developed rigorous variational bounds that provide insight on the best possible performance that one can hope to obtain from a digital QAOA circuit.
Abstract Quantum Annealing (QA) relies on mixing two Hamiltonian terms, a simple driver and a complex problem Hamiltonian, in a linear combination. The time-dependent schedule for this mixing is often taken to be linear in time: improving on this linear choice is known to be essential and has proven to be difficult. Here, we present different techniques for improving on the linear-schedule QA along two directions, conceptually distinct but leading to similar outcomes: 1) the first approach consists of constructing a Trotter-digitized QA (dQA) with schedules parameterized in terms of Fourier modes or Chebyshev polynomials, inspired by the Chopped Random Basis algorithm for optimal control in continuous time; 2) the second approach is technically a Quantum Approximate Optimization Algorithm (QAOA), whose solutions are found iteratively using linear interpolation or expansion in Fourier modes. Both approaches emphasize finding smooth optimal schedule parameters, ultimately leading to hybrid quantum–classical variational algorithms of the alternating Hamiltonian Ansatz type. We apply these techniques to MaxCut problems on weighted 3-regular graphs with N = 14 sites, focusing on hard instances that exhibit a small spectral gap, for which a standard linear-schedule QA performs poorly. We characterize the physics behind the optimal protocols for both the dQA and QAOA approaches, discovering shortcuts to adiabaticity -like dynamics. Furthermore, we study the transferability of such smooth solutions among hard instances of MaxCut at different circuit depths. Finally, we show that the smoothness pattern of these protocols obtained in a digital setting enables us to adapt them to continuous-time evolution, contrarily to generic non-smooth solutions. This procedure results in an optimized QA schedule that is implementable on analog devices.