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

Advantages of multistage quantum walks over QAOA

Lasse Gerblich, Tamanna Dasanjh, Horatio Q. X. Wong, Ross, David, Leonardo Novo, Nicholas Chancellor, Viv M. Kendon

Published Jul 9, 2024• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2407.06663

Related papers

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•3 citations

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

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou, Sheng-Tao Wang, Soonwon Choi +2 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

arXiv:1812.01041•Physical Review X•Jun 24, 2020•1,132 citations

Obstacles to Variational Quantum Optimization from Symmetry Protection

Sergey B. Bravyi, Alexander Kliesch, Robert König +1 more

The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.

arXiv:1910.08980•Physical Review Letters•Dec 24, 2020•336 citations

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Guido Pagano, Aniruddha Bapat, Patrick Becker +13 more

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

arXiv:1906.02700•Proceedings of the National Academy of Sciences•Oct 6, 2020•304 citations

Analytical Dimensions and Performance Evaluation of the Quantum Approximate Optimization Algorithm

Blas Trigueros, Pedro Juan Roig, Salvador Alcaraz +1 more

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most extensively studied variational approaches for tackling combinatorial optimization problems on near-term quantum devices. An extensive body of literature has examined the algorithm from multiple perspectives, including ansatz design, parameter optimization, computational resource requirements, solution quality, and noise effects.This paper adopts these principal analytical dimensions as a structured framework and revisits them from a performance-assessment perspective. By synthesizing representative theoretical, numerical, and experimental contributions, the discussion highlights recurring tendencies in reported results, particularly regarding approximation behavior, depth–noise trade-offs, optimization stability, and resource accounting.The analysis indicates that QAOA performance must be interpreted through a multidimensional lens that jointly considers solution quality, classical and quantum resource costs, optimization dynamics, and hardware constraints. By organizing existing results along common evaluation axes, this work provides a coherent basis for interpreting benchmarking outcomes and for guiding future assessment methodologies in realistic computational settings.

International Conference on Integrated Intelligence and Cognitive Engineering (ICIICE)•Apr 18, 2026•0 citations
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.
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.
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.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.
Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most extensively studied variational approaches for tackling combinatorial optimization problems on near-term quantum devices. An extensive body of literature has examined the algorithm from multiple perspectives, including ansatz design, parameter optimization, computational resource requirements, solution quality, and noise effects.This paper adopts these principal analytical dimensions as a structured framework and revisits them from a performance-assessment perspective. By synthesizing representative theoretical, numerical, and experimental contributions, the discussion highlights recurring tendencies in reported results, particularly regarding approximation behavior, depth–noise trade-offs, optimization stability, and resource accounting.The analysis indicates that QAOA performance must be interpreted through a multidimensional lens that jointly considers solution quality, classical and quantum resource costs, optimization dynamics, and hardware constraints. By organizing existing results along common evaluation axes, this work provides a coherent basis for interpreting benchmarking outcomes and for guiding future assessment methodologies in realistic computational settings.