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:2003.07419

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

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

Published Mar 16, 2020• 9 citations
arXivHTMLPDF

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 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}$.

DOI
10.48550/arxiv.2003.07419

Related papers

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

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

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 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}$.

•Mar 16, 2020•2 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

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

Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy

Shuntaro Okada, Masayuki Ohzeki

Quantum annealing is a heuristic algorithm for searching the ground state of an Ising model. Heuristic algorithms aim to obtain near-optimal solutions with a reasonable computation time. Accordingly, many algorithms have so far been proposed. In general, the performance of heuristic algorithms strongly depends on the instance of the combinatorial optimization problem to be solved because they escape the local minima in different ways. Therefore, combining several algorithms to exploit their complementary strength is effective for obtaining highly accurate solutions for a wide range of combinatorial optimization problems. However, quantum annealing cannot be used to improve a candidate solution obtained by other algorithms because it starts from an initial state where all spin configurations are found with a uniform probability. In this study, we propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy. Our formulation exploits the biased sampling of degenerated ground states in transverse magnetic field quantum annealing. We also analytically show that a first-order phase transition is successfully avoided for a fully connected ferromagnetic Potts model if the overlap between a ground state and a candidate solution exceeds a threshold. The proposed formulation is applicable to a wide range of integer optimization problems and enables us to hybridize quantum annealing with other optimization algorithms.

arXiv:2211.03957•Nov 8, 2022•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
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.
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.
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.
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.
Quantum annealing is a heuristic algorithm for searching the ground state of an Ising model. Heuristic algorithms aim to obtain near-optimal solutions with a reasonable computation time. Accordingly, many algorithms have so far been proposed. In general, the performance of heuristic algorithms strongly depends on the instance of the combinatorial optimization problem to be solved because they escape the local minima in different ways. Therefore, combining several algorithms to exploit their complementary strength is effective for obtaining highly accurate solutions for a wide range of combinatorial optimization problems. However, quantum annealing cannot be used to improve a candidate solution obtained by other algorithms because it starts from an initial state where all spin configurations are found with a uniform probability. In this study, we propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy. Our formulation exploits the biased sampling of degenerated ground states in transverse magnetic field quantum annealing. We also analytically show that a first-order phase transition is successfully avoided for a fully connected ferromagnetic Potts model if the overlap between a ground state and a candidate solution exceeds a threshold. The proposed formulation is applicable to a wide range of integer optimization problems and enables us to hybridize quantum annealing with other optimization algorithms.
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.