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

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

Asa Hopkins, Viv Kendon

quant-phSubmitted Nov 3, 2025• Announced Nov 4, 2025• 0 citations• Revised May 26, 2026 (v2)
v1 · Nov 3, 2025v2 · May 26, 2026
arXivHTMLPDF

Abstract

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.

Comments
19 pages (including appendix), 9 figures. Expanded discussion section, in particular the comparison with quantum annealing. Some notation choices have been changed too: The factor of 1/2 is not absorbed into J anymore, and the energy units are in the fields A and B rather than the parameters J and h

Related papers

Advantages of multistage quantum walks over QAOA

Lasse Gerblich, Tamanna Dasanjh, Horatio Q. X. Wong +4 more

Methods to find the solution state for optimization problems encoded into Ising Hamiltonians are a very active area of current research. In this work we compare the quantum approximate optimization algorithm (QAOA) with multi-stage quantum walks (MSQW). Both can be used as variational quantum algorithms, where the control parameters are optimized classically. A fair comparison requires both quantum and classical resources to be assessed. Alternatively, parameters can be chosen heuristically, as we do in this work, providing a simpler setting for comparisons. Using both numerical and analytical methods, we obtain evidence that MSQW outperforms QAOA, using equivalent resources. We also show numerically for random spin glass ground state problems that MSQW performs well even for few stages and heuristic parameters, with no classical optimization.

arXiv:2407.06663•Jul 9, 2024•1 citation

Multi-Stage Quantum Walk for Constrained Combinatorial Optimization with Equality Constraints

T Hattori, Paul A. Warburton, Shu Tanaka

Multi-stage quantum walks (MSQW) are a promising near-term quantum algorithm. Although studies on MSQW have recently been cultivated, there is still limited evidence regarding their effectiveness for constrained combinatorial optimization problems (COPs). This study applied methods proposed in previous studies, which restrict the quantum state to a feasible space and are effective for quantum annealing, to MSQW. As a result, we reveal that the proposed method has the potential to efficiently solve constrained COPs compared to penalty-based naive formulations.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 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

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

Parameter-setting heuristic for the quantum alternating operator ansatz

James Sud, Stuart Hadfield, Eleanor Gilbert Rieffel +2 more

The quantum alternating operator ansatz (QAOA) is a generalized approach for solving challenging optimization problems that builds on the alternating structure of the quantum approximate optimization algorithm. Finding high-quality parameters efficiently for QAOA remains a major challenge in practice. In this work, we introduce a classical strategy for parameter setting, suitable for cases in which the number of distinct cost values grows only polynomially with the problem size, such as is common for constraint-satisfaction problems. The crux of our strategy is that we replace the cost function expectation value step of QAOA with a classical model that can be efficiently evaluated classically and has parameters which play an analogous role to the QAOA parameters. This model is based on empirical observations that, in some QAOA states, variable configurations with the same cost have the same amplitudes from step to step. We define this class of states as homogeneous states. For problems with particular symmetries, QAOA states are guaranteed to be homogeneous. More generally, high overlaps between QAOA states and homogeneous states have been empirically observed in a number of settings. Building on this idea, we define a classical homogeneous proxy for QAOA in which this property holds exactly and which yields information describing both states and expectation values. We then classically determine high-quality parameters for this proxy and then use these parameters in QAOA, an approach we label the homogeneous heuristic for parameter setting. We numerically examine this heuristic for MaxCut on unweighted Erdős-Rényi random graphs. For up to three QAOA levels we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously found globally optimized approaches. For levels up to 20 we obtain parameters using our heuristic with approximation ratios monotonically increasing with depth, while a strategy that uses parameter transfer instead fails to converge with comparable classical resources. These results suggest that our heuristic may find good parameters in regimes that are intractable with noisy intermediate-scale quantum devices. Finally, we outline how our heuristic may be applied to wider classes of problems. Published by the American Physical Society 2024

arXiv:2211.09270•Physical Review Research•May 15, 2024•15 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
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.
Methods to find the solution state for optimization problems encoded into Ising Hamiltonians are a very active area of current research. In this work we compare the quantum approximate optimization algorithm (QAOA) with multi-stage quantum walks (MSQW). Both can be used as variational quantum algorithms, where the control parameters are optimized classically. A fair comparison requires both quantum and classical resources to be assessed. Alternatively, parameters can be chosen heuristically, as we do in this work, providing a simpler setting for comparisons. Using both numerical and analytical methods, we obtain evidence that MSQW outperforms QAOA, using equivalent resources. We also show numerically for random spin glass ground state problems that MSQW performs well even for few stages and heuristic parameters, with no classical optimization.
Multi-stage quantum walks (MSQW) are a promising near-term quantum algorithm. Although studies on MSQW have recently been cultivated, there is still limited evidence regarding their effectiveness for constrained combinatorial optimization problems (COPs). This study applied methods proposed in previous studies, which restrict the quantum state to a feasible space and are effective for quantum annealing, to MSQW. As a result, we reveal that the proposed method has the potential to efficiently solve constrained COPs compared to penalty-based naive formulations.
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.
The quantum alternating operator ansatz (QAOA) is a generalized approach for solving challenging optimization problems that builds on the alternating structure of the quantum approximate optimization algorithm. Finding high-quality parameters efficiently for QAOA remains a major challenge in practice. In this work, we introduce a classical strategy for parameter setting, suitable for cases in which the number of distinct cost values grows only polynomially with the problem size, such as is common for constraint-satisfaction problems. The crux of our strategy is that we replace the cost function expectation value step of QAOA with a classical model that can be efficiently evaluated classically and has parameters which play an analogous role to the QAOA parameters. This model is based on empirical observations that, in some QAOA states, variable configurations with the same cost have the same amplitudes from step to step. We define this class of states as homogeneous states. For problems with particular symmetries, QAOA states are guaranteed to be homogeneous. More generally, high overlaps between QAOA states and homogeneous states have been empirically observed in a number of settings. Building on this idea, we define a classical homogeneous proxy for QAOA in which this property holds exactly and which yields information describing both states and expectation values. We then classically determine high-quality parameters for this proxy and then use these parameters in QAOA, an approach we label the homogeneous heuristic for parameter setting. We numerically examine this heuristic for MaxCut on unweighted Erdős-Rényi random graphs. For up to three QAOA levels we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously found globally optimized approaches. For levels up to 20 we obtain parameters using our heuristic with approximation ratios monotonically increasing with depth, while a strategy that uses parameter transfer instead fails to converge with comparable classical resources. These results suggest that our heuristic may find good parameters in regimes that are intractable with noisy intermediate-scale quantum devices. Finally, we outline how our heuristic may be applied to wider classes of problems. Published by the American Physical Society 2024
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.