Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.13563 · Physical Review A

Forbidden subspaces for level-1 quantum approximate optimization algorithm and instantaneous quantum polynomial circuits

Michael Streif, Martin Leib

Published Oct 28, 2020• 7 citations
arXivHTMLPDF

Abstract

We present a thorough investigation of problems that can be solved exactly with the level-1 quantum approximate optimization algorithm (QAOA). To this end, we implicitly define a class of problem Hamiltonians that are employed as phase separators in a level-1 QAOA circuit and provide unit overlap with a target subspace spanned by a set of computational basis states. For one-dimensional target subspaces, we identify instances within the implicitly defined class of Hamiltonians for which quantum annealing (QA) and simulated annealing (SA) have an exponentially small probability of finding the solution. Consequently, our results define a demarcation line between QAOA on one hand and QA and SA on the other, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively. Moreover, for two-dimensional solution subspaces, we are able to show that the depth of the QAOA circuit grows linearly with the Hamming distance between the two target states. We further show that there are no genuine solutions for target subspaces of dimension higher than 2 and smaller than ${2}^{n}$. We also transfer these results to instantaneous quantum polynomial (IQP) circuits.

DOI
10.1103/physreva.102.042416

Related papers

Comparison of QAOA with Quantum and Simulated Annealing

Michael Streif, Martin Leib

We present a comparison between the Quantum Approximate Optimization Algorithm (QAOA) and two widely studied competing methods, Quantum Annealing (QA) and Simulated Annealing (SA). To achieve this, we define a class of optimization problems with respect to their spectral properties which are exactly solvable with QAOA. In this class, we identify instances for which QA and SA have an exponentially small probability to find the solution. Consequently, our results define a first demarcation line between QAOA, Simulated Annealing and Quantum Annealing, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively.

arXiv:1901.01903•Jan 7, 2019•35 citations

Exploring the neighborhood of 1-layer QAOA with instantaneous quantum polynomial circuits

Sebastian Leontica, David Amaro

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

arXiv:2210.05526•Physical Review Research•Jan 19, 2024•7 citations

Short-depth QAOA circuits and quantum annealing on higher-order ising models

Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz

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.

npj Quantum Information•Mar 12, 2024•47 citations

Universal resources for quantum approximate optimization algorithm and quantum annealing

Pablo Díez-Valle, Fernando J. Gómez-Ruiz, Diego Porras +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a variational ansatz that resembles the Trotterized dynamics of a Quantum Annealing (QA) protocol. This work formalizes this connection formally and empirically, showing the angles of a multilayer QAOA circuit converge to universal QA trajectories. Furthermore, the errors in both QAOA circuits and QA paths act as thermal excitations in pseudo-Boltzmann probability distributions whose temperature decreases with the invested resource -- i.e. integrated angles or total time -- and which in QAOA also contain a higher temperature arising from the Trotterization. This also means QAOA and QA are cooling protocols and simulators of partition functions whose target temperature can be tuned by rescaling the universal trajectory. The average cooling power of both methods exhibits favorable algebraic scalings with respect to the target temperature and problem size, whereby in QAOA the coldest temperature is inversely proportional to the number of layers, $T\sim 1/p$, and to the integrated angles -- or integrated interactions in QA.

quant-pharXiv:2506.03241•Physical Review Research•Jun 5, 2025•3 citations

Quantum Approximate Optimization Algorithm in Finite Size and Large Depth and Equivalence to Quantum Annealing

Sami Boulebnane, James Sud, Ruslan Shaydulin +1 more

The quantum approximate optimization algorithm (QAOA) and quantum annealing are two of the most popular quantum optimization heuristics. While QAOA is known to be able to approximate quantum annealing, the approximation requires QAOA angles to vanish with the problem size $n$, whereas optimized QAOA angles are observed to be size-independent for small $n$ and constant in the infinite-size limit. This fact led to a folklore belief that QAOA has a mechanism that is fundamentally different from quantum annealing. In this work, we provide evidence against this by analytically showing that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant. These conditions are known to hold for near-optimal QAOA angles empirically. Our proof relies on a series expansion of QAOA energy in sum of angles, which we show converges to quantum annealing limit as QAOA depth grows for constant sum of angles even if angles do not vanish with problem size $n$. A corollary of our results is a quadratic improvement for the bound on depth required to compile Trotterized quantum annealing of the SK model in the average case.

arXiv:2503.09563•Mar 12, 2025•1 citation

The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions

Francisco Chicano, Zakaria Abdelmoiz Dahi, Gabriel Luque

QAOA is a hybrid quantum-classical algorithm to solve optimization problems in gate-based quantum computers. It is based on a variational quantum circuit that can be interpreted as a discretization of the annealing process that quantum annealers follow to find a minimum energy state of a given Hamiltonian. This ensures that QAOA must find an optimal solution for any given optimization problem when the number of layers, p, used in the variational quantum circuit tends to infinity. In practice, the number of layers is usually bounded by a small number. This is a must in current quantum computers of the NISQ era, due to the depth limit of the circuits they can run to avoid problems with decoherence and noise. In this paper, we show mathematical evidence that QAOA requires exponential time to solve linear functions when the number of layers is less than the number of different coefficients of the linear function n. We conjecture that QAOA needs exponential time to find the global optimum of linear functions for any constant value of p, and that the runtime is linear only if p ≥ n. We conclude that we need new quantum algorithms to reach quantum supremacy in quantum optimization.

arXiv:2505.06404•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•1 citation
We present a thorough investigation of problems that can be solved exactly with the level-1 quantum approximate optimization algorithm (QAOA). To this end, we implicitly define a class of problem Hamiltonians that are employed as phase separators in a level-1 QAOA circuit and provide unit overlap with a target subspace spanned by a set of computational basis states. For one-dimensional target subspaces, we identify instances within the implicitly defined class of Hamiltonians for which quantum annealing (QA) and simulated annealing (SA) have an exponentially small probability of finding the solution. Consequently, our results define a demarcation line between QAOA on one hand and QA and SA on the other, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively. Moreover, for two-dimensional solution subspaces, we are able to show that the depth of the QAOA circuit grows linearly with the Hamming distance between the two target states. We further show that there are no genuine solutions for target subspaces of dimension higher than 2 and smaller than 2n{2}^{n}2n. We also transfer these results to instantaneous quantum polynomial (IQP) circuits.
We present a comparison between the Quantum Approximate Optimization Algorithm (QAOA) and two widely studied competing methods, Quantum Annealing (QA) and Simulated Annealing (SA). To achieve this, we define a class of optimization problems with respect to their spectral properties which are exactly solvable with QAOA. In this class, we identify instances for which QA and SA have an exponentially small probability to find the solution. Consequently, our results define a first demarcation line between QAOA, Simulated Annealing and Quantum Annealing, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively.
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
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a variational ansatz that resembles the Trotterized dynamics of a Quantum Annealing (QA) protocol. This work formalizes this connection formally and empirically, showing the angles of a multilayer QAOA circuit converge to universal QA trajectories. Furthermore, the errors in both QAOA circuits and QA paths act as thermal excitations in pseudo-Boltzmann probability distributions whose temperature decreases with the invested resource -- i.e. integrated angles or total time -- and which in QAOA also contain a higher temperature arising from the Trotterization. This also means QAOA and QA are cooling protocols and simulators of partition functions whose target temperature can be tuned by rescaling the universal trajectory. The average cooling power of both methods exhibits favorable algebraic scalings with respect to the target temperature and problem size, whereby in QAOA the coldest temperature is inversely proportional to the number of layers, T∼1/pT\sim 1/pT∼1/p, and to the integrated angles -- or integrated interactions in QA.
The quantum approximate optimization algorithm (QAOA) and quantum annealing are two of the most popular quantum optimization heuristics. While QAOA is known to be able to approximate quantum annealing, the approximation requires QAOA angles to vanish with the problem size nnn, whereas optimized QAOA angles are observed to be size-independent for small nnn and constant in the infinite-size limit. This fact led to a folklore belief that QAOA has a mechanism that is fundamentally different from quantum annealing. In this work, we provide evidence against this by analytically showing that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant. These conditions are known to hold for near-optimal QAOA angles empirically. Our proof relies on a series expansion of QAOA energy in sum of angles, which we show converges to quantum annealing limit as QAOA depth grows for constant sum of angles even if angles do not vanish with problem size nnn. A corollary of our results is a quadratic improvement for the bound on depth required to compile Trotterized quantum annealing of the SK model in the average case.
QAOA is a hybrid quantum-classical algorithm to solve optimization problems in gate-based quantum computers. It is based on a variational quantum circuit that can be interpreted as a discretization of the annealing process that quantum annealers follow to find a minimum energy state of a given Hamiltonian. This ensures that QAOA must find an optimal solution for any given optimization problem when the number of layers, p, used in the variational quantum circuit tends to infinity. In practice, the number of layers is usually bounded by a small number. This is a must in current quantum computers of the NISQ era, due to the depth limit of the circuits they can run to avoid problems with decoherence and noise. In this paper, we show mathematical evidence that QAOA requires exponential time to solve linear functions when the number of layers is less than the number of different coefficients of the linear function n. We conjecture that QAOA needs exponential time to find the global optimum of linear functions for any constant value of p, and that the runtime is linear only if p ≥ n. We conclude that we need new quantum algorithms to reach quantum supremacy in quantum optimization.