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

Polynomial scaling of QAOA for ground-state preparation: taming first-order phase transitions

Matteo M. Wauters, Glen Bigan Mbeng, Giuseppe E. Santoro

Published Mar 16, 2020• 2 citations
OpenAlex

Abstract

We show that the quantum approximate optimization algorithm (QAOA) can construct with polynomially scaling resources the ground state of the fully-connected p-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a Quantum Annealing (QA) approach, due to the exponentially small gaps encountered at first-order phase transition for ${\rm p} \ge 3$. For a generic target state, we find that an appropriate QAOA parameter initialization is necessary to achieve a good performance of the algorithm when the number of variational parameters $2{\rm P}$ is much smaller that the system size ${\rm N}$, because of the large number of sub-optimal local minima. We find that when ${\rm P} > {\rm P}^*_{\rm N} \propto {\rm N}$, the structure of the parameter space simplifies, as all minima become degenerate. This allows to achieve the ground state with perfect fidelity with a number of parameters scaling extensively with ${\rm N}$, and with resources scaling polynomially with ${\rm N}$.

Related papers

Polynomial scaling of QAOA for ground-state preparation of the fully-connected p-spin ferromagnet

Matteo M. Wauters, Glen Bigan Mbeng, Giuseppe E. Santoro

We show that the quantum approximate optimization algorithm (QAOA) can construct with polynomially scaling resources the ground state of the fully-connected p-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a Quantum Annealing (QA) approach, due to the exponentially small gaps encountered at first-order phase transition for ${\rm p} \ge 3$. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve a good performance of the algorithm when the number of variational parameters $2{\rm P}$ is much smaller than the system size ${\rm N}$, because of the large number of sub-optimal local minima. Instead, when ${\rm P}$ exceeds a critical value ${\rm P}^*_{\rm N} \propto {\rm N}$, the structure of the parameter space simplifies, as all minima become degenerate. This allows to achieve the ground state with perfect fidelity with a number of parameters scaling extensively with ${\rm N}$, and with resources scaling polynomially with ${\rm N}$.

arXiv:2003.07419•Mar 16, 2020•9 citations

Polynomial scaling of the quantum approximate optimization algorithm for ground-state preparation of the fully connected p -spin ferromagnet in a transverse field

Matteo M. Wauters, Glen Bigan Mbeng, Giuseppe E. Santoro

We show that the quantum approximate optimization algorithm (QAOA) can construct, with polynomially scaling resources, the ground state of the fully connected $p$-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a vanilla quantum annealing (QA) approach due to the exponentially small gaps encountered at first-order phase transition for $p\ensuremath{\ge}3$. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve good performance of the algorithm when the number of variational parameters $2P$ is much smaller than the system size $N$ because of the large number of suboptimal local minima. Instead, when $P$ exceeds a critical value ${P}_{N}^{*}\ensuremath{\propto}N$, the structure of the parameter space simplifies, as all minima become degenerate. This allows achieving the ground state with perfect fidelity with a number of parameters scaling extensively with $N$ and with resources scaling polynomially with $N$.

Physical Review A•Dec 3, 2020•21 citations

Parity Mapping for Quantum Optimization on Frustrated Ising Rings

Ruiyi Wang, Anita Weidinger, Glen Bigan Mbeng +2 more

The frustrated Ising ring is one of the simplest models exhibiting exponential closing spectral gaps, making it a paradigmatic and challenging benchmark for quantum annealing (QA). Ground-state preparation for this model has therefore been studied extensively in both continuous-time QA and digitized protocols such as the Quantum Approximate Optimization Algorithm (QAOA). Here, we use the frustrated Ising ring to investigate how the parity mapping affects the performance of both QA and QAOA. For QA, finite-size calculations show that the parity mapping increases the minimum spectral gap under the energy normalization used in this work, thereby enabling faster continuous-time ground state preparation protocols. An ideal implementation of Parity-QA, with a single global constraint, shows no evidence of exponential gap closing over the accessible system sizes, whereas a hardware-motivated decomposition into local constraints restores the exponential decrease, albeit with a smaller fitted exponent than conventional QA. For the digitized protocol, we find that the number of Parity-QAOA layers required to prepare the exact ground state remains constant over the simulated sizes, improving upon the quadratic scaling required by conventional QAOA. To investigate the role of constraints in Parity-QAOA, we further consider a modified Ising ring instance in which the constraint term is essential for preparing the target ground state. We then compare the corresponding resource requirements with those of conventional QAOA.

quant-pharXiv:2608.12213•Aug 13, 2026•0 citations

Heuristics for multi-stage quantum walks to find Ising ground states

Asa Hopkins, Viv Kendon

One way to approximate a quantum annealing schedule is to use multiple quantum walks chained together, without intermediate measurements, to produce a multi-stage quantum walk (MSQW). Previous work has shown that a MSQW is better than QAOA (quantum alternating operator ansatz) for solving optimization tasks using multiple stages [Gerblich et al, arXiv:2407.06663]. In this work, we develop an efficient heuristic for choosing the free parameters in MSQW, and use it to obtain improved scaling compared to single stage quantum walks. We show numerically that the heuristic works well for problems with a large minimum energy gap, giving a polynomial scaling in the number of stages, and leading to an overall algorithm that scales polynomially in time. For problems with a small minimum gap, the scaling breaks down such that adding more stages decreases the success probability, leading to an overall scaling that is exponential in time as expected. Our methods are general and can be applied to any optimization problem to obtain good annealing schedules.

quant-pharXiv:2511.01312•Nov 4, 2025•0 citations

Quantum annealing initialization of the quantum approximate optimization algorithm

Stefan H. Sack, Maksym Serbyn

The quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm due to its modest circuit depth and promising benchmarks. However, an external parameter optimization required in QAOA could become a performance bottleneck. This motivates studies of the optimization landscape and search for heuristic ways of parameter initialization. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs, demonstrating that random initialization of the QAOA is prone to converging to local minima with sub-optimal performance. We introduce the initialization of QAOA parameters based on the Trotterized quantum annealing (TQA) protocol, parameterized by the Trotter time step. We find that the TQA initialization allows to circumvent the issue of false minima for a broad range of time steps, yielding the same performance as the best result out of an exponentially scaling number of random initializations. Moreover, we demonstrate that the optimal value of the time step coincides with the point of proliferation of Trotter errors in quantum annealing. Our results suggest practical ways of initializing QAOA protocols on near-term quantum devices and reveals new connections between QAOA and quantum annealing.

arXiv:2101.05742•Quantum•Jul 1, 2021•145 citations

Approximating Ground States of Quantum Hamiltonians with Snapshot-QAOA

Reuben Tate, Quinn Langfitt, Elijah Pelofske +4 more

Abstract We present Snapshot-QAOA, a variation of the Quantum Approximate Optimization Algorithm (QAOA) that finds approximate minimum energy eigenstates of a large set of quantum Hamiltonians (i.e. Hamiltonians with non-diagonal terms). Traditionally, QAOA targets the task of approximately solving combinatorial optimization problems --- Snapshot-QAOA enables a significant expansion of the use case space for QAOA to more general quantum Hamiltonians, where the goal is to approximate the ground-state. Such ground-state finding is a common challenge in quantum chemistry and material science applications. Snapshot-QAOA retains desirable variational-algorithm qualities of QAOA, in particular small parameter count and relatively shallow circuit depth. Snapshot-QAOA is thus a better trainable alternative to the (Near Intermediate-Scale Quantum) NISQ-era Variational Quantum Eigensolver (VQE) algorithm, while retaining a significant circuit-depth advantage over the (Quantum Error Corrected) QEC-era Quantum Phase Estimation (QPE) algorithm. Our fundamental approach is inspired by the idea of Trotterization of a continuous-time linear adiabatic anneal schedule, which for sufficiently large QAOA depth gives very good performance. Snapshot-QAOA restricts the QAOA evolution to not phasing out the mixing Hamiltonian completely at the end of the evolution, instead evolving only a partial typical linear QAOA schedule, thus creating a type of snapshot of the typical QAOA evolution. As a test case, we simulate Snapshot-QAOA on a particular 16 qubit 2D J1-J2 frustrated square transverse field Ising model with periodic boundary conditions.

IEEE International Conference on Quantum Artificial Intelligence (QAI)•Nov 2, 2025•0 citations
We show that the quantum approximate optimization algorithm (QAOA) can construct with polynomially scaling resources the ground state of the fully-connected p-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a Quantum Annealing (QA) approach, due to the exponentially small gaps encountered at first-order phase transition for p≥3{\rm p} \ge 3p≥3. For a generic target state, we find that an appropriate QAOA parameter initialization is necessary to achieve a good performance of the algorithm when the number of variational parameters 2P2{\rm P}2P is much smaller that the system size N{\rm N}N, because of the large number of sub-optimal local minima. We find that when P>PN∗∝N{\rm P} > {\rm P}^*_{\rm N} \propto {\rm N}P>PN∗​∝N, the structure of the parameter space simplifies, as all minima become degenerate. This allows to achieve the ground state with perfect fidelity with a number of parameters scaling extensively with N{\rm N}N, and with resources scaling polynomially with N{\rm N}N.
We show that the quantum approximate optimization algorithm (QAOA) can construct with polynomially scaling resources the ground state of the fully-connected p-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a Quantum Annealing (QA) approach, due to the exponentially small gaps encountered at first-order phase transition for p≥3{\rm p} \ge 3p≥3. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve a good performance of the algorithm when the number of variational parameters 2P2{\rm P}2P is much smaller than the system size N{\rm N}N, because of the large number of sub-optimal local minima. Instead, when P{\rm P}P exceeds a critical value PN∗∝N{\rm P}^*_{\rm N} \propto {\rm N}PN∗​∝N, the structure of the parameter space simplifies, as all minima become degenerate. This allows to achieve the ground state with perfect fidelity with a number of parameters scaling extensively with N{\rm N}N, and with resources scaling polynomially with N{\rm N}N.
We show that the quantum approximate optimization algorithm (QAOA) can construct, with polynomially scaling resources, the ground state of the fully connected ppp-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a vanilla quantum annealing (QA) approach due to the exponentially small gaps encountered at first-order phase transition for $p\ensuremath{\ge}3$. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve good performance of the algorithm when the number of variational parameters 2P2P2P is much smaller than the system size NNN because of the large number of suboptimal local minima. Instead, when PPP exceeds a critical value ${P}_{N}^{*}\ensuremath{\propto}N$, the structure of the parameter space simplifies, as all minima become degenerate. This allows achieving the ground state with perfect fidelity with a number of parameters scaling extensively with NNN and with resources scaling polynomially with NNN.
The frustrated Ising ring is one of the simplest models exhibiting exponential closing spectral gaps, making it a paradigmatic and challenging benchmark for quantum annealing (QA). Ground-state preparation for this model has therefore been studied extensively in both continuous-time QA and digitized protocols such as the Quantum Approximate Optimization Algorithm (QAOA). Here, we use the frustrated Ising ring to investigate how the parity mapping affects the performance of both QA and QAOA. For QA, finite-size calculations show that the parity mapping increases the minimum spectral gap under the energy normalization used in this work, thereby enabling faster continuous-time ground state preparation protocols. An ideal implementation of Parity-QA, with a single global constraint, shows no evidence of exponential gap closing over the accessible system sizes, whereas a hardware-motivated decomposition into local constraints restores the exponential decrease, albeit with a smaller fitted exponent than conventional QA. For the digitized protocol, we find that the number of Parity-QAOA layers required to prepare the exact ground state remains constant over the simulated sizes, improving upon the quadratic scaling required by conventional QAOA. To investigate the role of constraints in Parity-QAOA, we further consider a modified Ising ring instance in which the constraint term is essential for preparing the target ground state. We then compare the corresponding resource requirements with those of conventional QAOA.
One way to approximate a quantum annealing schedule is to use multiple quantum walks chained together, without intermediate measurements, to produce a multi-stage quantum walk (MSQW). Previous work has shown that a MSQW is better than QAOA (quantum alternating operator ansatz) for solving optimization tasks using multiple stages [Gerblich et al, arXiv:2407.06663]. In this work, we develop an efficient heuristic for choosing the free parameters in MSQW, and use it to obtain improved scaling compared to single stage quantum walks. We show numerically that the heuristic works well for problems with a large minimum energy gap, giving a polynomial scaling in the number of stages, and leading to an overall algorithm that scales polynomially in time. For problems with a small minimum gap, the scaling breaks down such that adding more stages decreases the success probability, leading to an overall scaling that is exponential in time as expected. Our methods are general and can be applied to any optimization problem to obtain good annealing schedules.
The quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm due to its modest circuit depth and promising benchmarks. However, an external parameter optimization required in QAOA could become a performance bottleneck. This motivates studies of the optimization landscape and search for heuristic ways of parameter initialization. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs, demonstrating that random initialization of the QAOA is prone to converging to local minima with sub-optimal performance. We introduce the initialization of QAOA parameters based on the Trotterized quantum annealing (TQA) protocol, parameterized by the Trotter time step. We find that the TQA initialization allows to circumvent the issue of false minima for a broad range of time steps, yielding the same performance as the best result out of an exponentially scaling number of random initializations. Moreover, we demonstrate that the optimal value of the time step coincides with the point of proliferation of Trotter errors in quantum annealing. Our results suggest practical ways of initializing QAOA protocols on near-term quantum devices and reveals new connections between QAOA and quantum annealing.
Abstract We present Snapshot-QAOA, a variation of the Quantum Approximate Optimization Algorithm (QAOA) that finds approximate minimum energy eigenstates of a large set of quantum Hamiltonians (i.e. Hamiltonians with non-diagonal terms). Traditionally, QAOA targets the task of approximately solving combinatorial optimization problems --- Snapshot-QAOA enables a significant expansion of the use case space for QAOA to more general quantum Hamiltonians, where the goal is to approximate the ground-state. Such ground-state finding is a common challenge in quantum chemistry and material science applications. Snapshot-QAOA retains desirable variational-algorithm qualities of QAOA, in particular small parameter count and relatively shallow circuit depth. Snapshot-QAOA is thus a better trainable alternative to the (Near Intermediate-Scale Quantum) NISQ-era Variational Quantum Eigensolver (VQE) algorithm, while retaining a significant circuit-depth advantage over the (Quantum Error Corrected) QEC-era Quantum Phase Estimation (QPE) algorithm. Our fundamental approach is inspired by the idea of Trotterization of a continuous-time linear adiabatic anneal schedule, which for sufficiently large QAOA depth gives very good performance. Snapshot-QAOA restricts the QAOA evolution to not phasing out the mixing Hamiltonian completely at the end of the evolution, instead evolving only a partial typical linear QAOA schedule, thus creating a type of snapshot of the typical QAOA evolution. As a test case, we simulate Snapshot-QAOA on a particular 16 qubit 2D J1-J2 frustrated square transverse field Ising model with periodic boundary conditions.