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:2204.10324 · Quantum Information Processing

Grover search inspired alternating operator ansatz of quantum approximate optimization algorithm for search problems

Chen-Fu Chiang, Paul M. Alsing

Published May 19, 2023• 4 citations
arXivHTMLPDF

Abstract

Abstract We use the mapping between two computation frameworks, Adiabatic Grover Search (AGS) and Adiabatic Quantum Computing (AQC), to translate the Grover search algorithm into the AQC regime. We then apply Trotterization on the schedule-dependent Hamiltonian of AGS to obtain the values of variational parameters in the Quantum Approximate Optimization Algorithm (QAOA) framework. The goal is to carry the optimal behavior of Grover search algorithm into the QAOA framework without the iterative machine learning processes.

DOI
10.1007/s11128-023-03968-5

Related papers

Quantum Alternating Operator Ansatz (QAOA) Phase Diagrams and Applications for Quantum Chemistry

Vladimir Kremenetski, Tad Hogg, Stuart Hadfield +2 more

Determining Hamiltonian ground states and energies is a challenging task with many possible approaches on quantum computers. While variational quantum eigensolvers are popular approaches for near term hardware, adiabatic state preparation is an alternative that does not require noisy optimization of parameters. Beyond adiabatic schedules, QAOA is an important method for optimization problems. In this work we modify QAOA to apply to finding ground states of molecules and empirically evaluate the modified algorithm on several molecules. This modification applies physical insights used in classical approximations to construct suitable QAOA operators and initial state. We find robust qualitative behavior for QAOA as a function of the number of steps and size of the parameters, and demonstrate this behavior also occurs in standard QAOA applied to combinatorial search. To this end we introduce QAOA phase diagrams that capture its performance and properties in various limits. In particular we show a region in which non-adiabatic schedules perform better than the adiabatic limit while employing lower quantum circuit depth. We further provide evidence our results and insights also apply to QAOA applications beyond chemistry.

arXiv:2108.13056•Aug 30, 2021•14 citations

Quantum-Walk-Inspired Dynamic Adiabatic Local Search

Chen-Fu Chiang, Paul M. Alsing

We investigate the irreconcilability issue that arises when translating the search algorithm from the Continuous Time Quantum Walk (CTQW) framework to the Adiabatic Quantum Computing (AQC) framework. For the AQC formulation to evolve along the same path as the CTQW, it requires a constant energy gap in the Hamiltonian throughout the AQC schedule. To resolve the constant gap issue, we modify the CTQW-inspired AQC catalyst Hamiltonian from an XZ operator to a Z oracle operator. Through simulation, we demonstrate that the total running time for the proposed approach for AQC with the modified catalyst Hamiltonian remains optimal as CTQW. Inspired by this solution, we further investigate adaptive scheduling for the catalyst Hamiltonian and its coefficient function in the adiabatic path of Grover-inspired AQC to improve the adiabatic local search.

arXiv:2204.09830•Entropy•Aug 31, 2023•1 citation

Alternative adiabatic quantum algorithms with algorithmic applications

Cunningham, Joseph

Adiabatic Quantum Computing (AQC) is a powerful framework for designing quantum algorithms, yet its practical implementation is often hampered by the difficulty of engineering precise, continuous time-dependent Hamiltonians or the substantial computational overhead of time discretisation. This thesis develops alternative adiabatic frameworks based on dissipative and stochastic quantum evolution to circumvent these challenges.The core methodology introduces novel dynamics where discrete quantum operations, such as time-independent Hamiltonian evolution with Poisson-distributed phase randomisation or randomised unitary applications (qubitization), replace continuous evolution. This stochastic approach allows the system’s average behaviour to be rigorously analysed using new, generalised adiabatic theorems, including the development of novel quantitative bounds for unbounded Hamiltonians and specialised dissipative generators.Algorithmically, this work demonstrates that these discrete, stochastic procedures can achieve the optimal asymptotic time complexity of continuous AQC while mitigating discretisation costs. Specifically, adapted-schedule implementations are shown to yield optimal scaling for the Quantum Linear Systems Problem (QLSP), achieving complexity proportional to the condition number $O(\kappa)$, and $O(\sqrt{N/M})$ scaling for unstructured search. By establishing highly efficient, implementable alternatives to continuous AQC, this research offers a significant pathway toward robust and scalable quantum computation. The study also investigates the general family of diagonal Hamiltonians for optimisation problems, revealing that finding the optimal scheduling required for peak performance is, in general, an NP-hard problem.

•Oct 17, 2025•0 citations

Threshold-Based Quantum Optimization

John K. Golden, Andreas Bärtschi, Daniel O’Malley +1 more

We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase separator operator, which encodes the objective function, with a threshold function that returns a value 1 for solutions with an objective value above the threshold and a 0 otherwise. We vary the threshold value to arrive at a quantum optimization algorithm. We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover’s quantum search algorithm and its minimum/maximum finding cousin to approximate optimization.Our main findings include: (i) we provide intuitive arguments and show empirically that the optimum parameter values of GM-Th-QAOA (angles and threshold value) can be found with O(log(p) × log M) iterations of the classical outer loop, where p is the number of QAOA rounds and M is an upper bound on the solution value (often the number of vertices or edges in an input graph), thus eliminating the notorious outer-loop parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be simulated classically with little effort up to 100 qubits through a set of tricks that cut down memory requirements; (iii) somewhat surprisingly, GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios achieved. This third result holds across a range of optimization problems (MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various experimental design parameters, such as different input edge densities and constraint sizes.

arXiv:2106.13860•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•27 citations

A Quantum Approximate Optimization Algorithm for continuous problems

Guillaume Verdon, Juan Miguel Arrazola, Kamil Brádler +1 more

We introduce a quantum approximate optimization algorithm (QAOA) for continuous optimization. The algorithm is based on the dynamics of a quantum system moving in an energy potential which encodes the objective function. By approximating the dynamics at finite time steps, the algorithm can be expressed as alternating evolution under two non-commuting Hamiltonians. We show that each step of the algorithm updates the wavefunction in the direction of its local gradient, with an additional momentum-dependent displacement. For initial states in a superposition over many points, this method can therefore be interpreted as a coherent version of gradient descent, i.e., 'gradient descent in superposition.' This approach can be used for both constrained and unconstrained optimization. In terms of computational complexity, we show how variants of the algorithm can recover continuous-variable Grover search, and how a single iteration can replicate continuous-variable instantaneous quantum polynomial circuits. We also discuss how the algorithm can be adapted to solve discrete optimization problems. Finally, we test the algorithm through numerical simulation in optimizing the Styblinski-Tang function.

arXiv:1902.00409•Feb 1, 2019•25 citations

Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer

Linghua Zhu, Ho Lun Tang, George S. Barron +4 more

The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA Ansatz is not optimal, there is no systematic approach for finding better Ans\"atze. We address this problem by developing an iterative version of QAOA that is problem tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.

Physical Review Research•Jul 11, 2022•209 citations
Abstract We use the mapping between two computation frameworks, Adiabatic Grover Search (AGS) and Adiabatic Quantum Computing (AQC), to translate the Grover search algorithm into the AQC regime. We then apply Trotterization on the schedule-dependent Hamiltonian of AGS to obtain the values of variational parameters in the Quantum Approximate Optimization Algorithm (QAOA) framework. The goal is to carry the optimal behavior of Grover search algorithm into the QAOA framework without the iterative machine learning processes.
Determining Hamiltonian ground states and energies is a challenging task with many possible approaches on quantum computers. While variational quantum eigensolvers are popular approaches for near term hardware, adiabatic state preparation is an alternative that does not require noisy optimization of parameters. Beyond adiabatic schedules, QAOA is an important method for optimization problems. In this work we modify QAOA to apply to finding ground states of molecules and empirically evaluate the modified algorithm on several molecules. This modification applies physical insights used in classical approximations to construct suitable QAOA operators and initial state. We find robust qualitative behavior for QAOA as a function of the number of steps and size of the parameters, and demonstrate this behavior also occurs in standard QAOA applied to combinatorial search. To this end we introduce QAOA phase diagrams that capture its performance and properties in various limits. In particular we show a region in which non-adiabatic schedules perform better than the adiabatic limit while employing lower quantum circuit depth. We further provide evidence our results and insights also apply to QAOA applications beyond chemistry.
We investigate the irreconcilability issue that arises when translating the search algorithm from the Continuous Time Quantum Walk (CTQW) framework to the Adiabatic Quantum Computing (AQC) framework. For the AQC formulation to evolve along the same path as the CTQW, it requires a constant energy gap in the Hamiltonian throughout the AQC schedule. To resolve the constant gap issue, we modify the CTQW-inspired AQC catalyst Hamiltonian from an XZ operator to a Z oracle operator. Through simulation, we demonstrate that the total running time for the proposed approach for AQC with the modified catalyst Hamiltonian remains optimal as CTQW. Inspired by this solution, we further investigate adaptive scheduling for the catalyst Hamiltonian and its coefficient function in the adiabatic path of Grover-inspired AQC to improve the adiabatic local search.
Adiabatic Quantum Computing (AQC) is a powerful framework for designing quantum algorithms, yet its practical implementation is often hampered by the difficulty of engineering precise, continuous time-dependent Hamiltonians or the substantial computational overhead of time discretisation. This thesis develops alternative adiabatic frameworks based on dissipative and stochastic quantum evolution to circumvent these challenges.The core methodology introduces novel dynamics where discrete quantum operations, such as time-independent Hamiltonian evolution with Poisson-distributed phase randomisation or randomised unitary applications (qubitization), replace continuous evolution. This stochastic approach allows the system’s average behaviour to be rigorously analysed using new, generalised adiabatic theorems, including the development of novel quantitative bounds for unbounded Hamiltonians and specialised dissipative generators.Algorithmically, this work demonstrates that these discrete, stochastic procedures can achieve the optimal asymptotic time complexity of continuous AQC while mitigating discretisation costs. Specifically, adapted-schedule implementations are shown to yield optimal scaling for the Quantum Linear Systems Problem (QLSP), achieving complexity proportional to the condition number O(κ)O(\kappa)O(κ), and O(N/M)O(\sqrt{N/M})O(N/M​) scaling for unstructured search. By establishing highly efficient, implementable alternatives to continuous AQC, this research offers a significant pathway toward robust and scalable quantum computation. The study also investigates the general family of diagonal Hamiltonians for optimisation problems, revealing that finding the optimal scheduling required for peak performance is, in general, an NP-hard problem.
We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase separator operator, which encodes the objective function, with a threshold function that returns a value 1 for solutions with an objective value above the threshold and a 0 otherwise. We vary the threshold value to arrive at a quantum optimization algorithm. We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover’s quantum search algorithm and its minimum/maximum finding cousin to approximate optimization.Our main findings include: (i) we provide intuitive arguments and show empirically that the optimum parameter values of GM-Th-QAOA (angles and threshold value) can be found with O(log(p) × log M) iterations of the classical outer loop, where p is the number of QAOA rounds and M is an upper bound on the solution value (often the number of vertices or edges in an input graph), thus eliminating the notorious outer-loop parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be simulated classically with little effort up to 100 qubits through a set of tricks that cut down memory requirements; (iii) somewhat surprisingly, GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios achieved. This third result holds across a range of optimization problems (MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various experimental design parameters, such as different input edge densities and constraint sizes.
We introduce a quantum approximate optimization algorithm (QAOA) for continuous optimization. The algorithm is based on the dynamics of a quantum system moving in an energy potential which encodes the objective function. By approximating the dynamics at finite time steps, the algorithm can be expressed as alternating evolution under two non-commuting Hamiltonians. We show that each step of the algorithm updates the wavefunction in the direction of its local gradient, with an additional momentum-dependent displacement. For initial states in a superposition over many points, this method can therefore be interpreted as a coherent version of gradient descent, i.e., 'gradient descent in superposition.' This approach can be used for both constrained and unconstrained optimization. In terms of computational complexity, we show how variants of the algorithm can recover continuous-variable Grover search, and how a single iteration can replicate continuous-variable instantaneous quantum polynomial circuits. We also discuss how the algorithm can be adapted to solve discrete optimization problems. Finally, we test the algorithm through numerical simulation in optimizing the Styblinski-Tang function.
The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA Ansatz is not optimal, there is no systematic approach for finding better Ans\"atze. We address this problem by developing an iterative version of QAOA that is problem tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.