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:2105.11946 · Physical Review Research

Quantum approximate optimization algorithm with adaptive bias fields

Yunlong Yu, Chenfeng Cao, Carter Dewey, Xiang‐Bin Wang, Nic Shannon, Robert Joynt

Published Jun 27, 2022• 41 citations
arXivHTMLPDF

Abstract

The quantum approximate optimization algorithm (QAOA) transforms a simple many-qubit wave function into one that encodes a solution to a difficult classical optimization problem. It does this by optimizing the schedule according to which two unitary operators are alternately applied to the qubits. In this paper, the QAOA is modified by updating the operators themselves to include local fields, using information from the measured wave function at the end of one iteration step to improve the operators at later steps. It is shown by numerical simulation on MaxCut problems that, for a fixed accuracy, this procedure decreases the runtime of QAOA very substantially. This improvement appears to increase with the problem size. Our method requires essentially the same number of quantum gates per optimization step as the standard QAOA, and no additional measurements. This modified algorithm enhances the prospects for quantum advantage for certain optimization problems.

DOI
10.1103/physrevresearch.4.023249

Related papers

Warm-start adaptive-bias quantum approximate optimization algorithm

Yunlong Yu, Xiang‐Bin Wang, Nic Shannon +1 more

In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with $40$ to $180$ qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to $1000$ qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the $1000$-qubit case even in level 1 can only be matched by the GW algorithm after about $10^{5.5}$ random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.

arXiv:2503.20048•Physical Review A•Jul 14, 2025•10 citations

Solution of SAT problems with the adaptive-bias quantum approximate optimization algorithm

Yunlong Yu, Chenfeng Cao, Xiang‐Bin Wang +2 more

The quantum approximate optimization algorithm (QAOA) is a promising method for solving certain classical combinatorial optimization problems on near-term quantum devices. When employing the QAOA to 3-SAT and Max-3-SAT problems, the quantum cost exhibits an easy-hard-easy or easy-hard pattern, respectively, as the clause density is changed. The quantum resources needed in the hard-region problems are out of reach for current noisy intermediate-scale quantum (NISQ) devices. We show by numerical simulations with up to 14 variables and analytical arguments that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. For similar accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT problems as compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7 levels and 62 levels. The improvement comes from a more targeted and more limited generation of entanglement during the evolution. We demonstrate that classical optimization is not strictly necessary in the ab-QAOA since local fields are used to guide the evolution. This leads us to propose an optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT problems effectively with significantly fewer quantum gates as compared to the original ab-QAOA. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.

arXiv:2210.02822•Physical Review Research•Jun 2, 2023•21 citations

Quantum Approximate Optimization Algorithm with Sparsified Phase Operator

Xiaoyuan Liu, Ruslan Shaydulin, Ilya Safro

The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate algorithm for demonstrating quantum advantage in optimization using near-term quantum computers. However, QAOA has high requirements on gate fidelity due to the need to encode the objective function in the phase separating operator, requiring a large number of gates that potentially do not match the hardware connectivity. Using the MaxCut problem as the target, we demonstrate numerically that an easier way to implement an alternative phase operator can be used in lieu of the phase operator encoding the objective function, as long as the ground state is the same. We observe that if the ground state energy is not preserved, the approximation ratio obtained by QAOA with such phase separating operator is likely to decrease. Moreover, we show that a better alignment of the low energy subspace of the alternative operator leads to better performance. Leveraging these observations, we propose a sparsification strategy that reduces the resource requirements of QAOA. We also compare our sparsification strategy with some other classical graph sparsification methods, and demonstrate the efficacy of our approach.

arXiv:2205.00118•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•7 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•67 citations

Improving the Quantum Approximate Optimization Algorithm with postselection

Sami Boulebnane

Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.

arXiv:2011.05425•Nov 10, 2020•3 citations

An Efficient QAOA via a Polynomial QPU-Needless Approach

Francisco Chicano, Zakaria Abdelmoiz Dahi, Gabriel Luque

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum algorithm described as ansatzes that represent both the problem and the mixer Hamiltonians. Both are parameterizable unitary transformations executed on a quantum machine/simulator and whose parameters are iteratively optimized using a classical device to optimize the problem's expectation value. To do so, in each QAOA iteration, most of the literature uses a quantum machine/simulator to measure the QAOA outcomes. However, this poses a severe bottleneck considering that quantum machines are hardly constrained (e.g. long queuing, limited qubits, etc.), likewise, quantum simulation also induces exponentially-increasing memory usage when dealing with large problems requiring more qubits. These limitations make today's QAOA implementation impractical since it is hard to obtain good solutions with a reasonably-acceptable time/resources. Considering these facts, this work presents a new approach with two main contributions, including (I) removing the need for accessing quantum devices or large-sized classical machines during the QAOA optimization phase, and (II) ensuring that when dealing with some k-bounded pseudo-Boolean problems, optimizing the exact problem's expectation value can be done in polynomial time using a classical computer.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•3 citations
The quantum approximate optimization algorithm (QAOA) transforms a simple many-qubit wave function into one that encodes a solution to a difficult classical optimization problem. It does this by optimizing the schedule according to which two unitary operators are alternately applied to the qubits. In this paper, the QAOA is modified by updating the operators themselves to include local fields, using information from the measured wave function at the end of one iteration step to improve the operators at later steps. It is shown by numerical simulation on MaxCut problems that, for a fixed accuracy, this procedure decreases the runtime of QAOA very substantially. This improvement appears to increase with the problem size. Our method requires essentially the same number of quantum gates per optimization step as the standard QAOA, and no additional measurements. This modified algorithm enhances the prospects for quantum advantage for certain optimization problems.
In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with 404040 to 180180180 qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to 100010001000 qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the 100010001000-qubit case even in level 1 can only be matched by the GW algorithm after about 105.510^{5.5}105.5 random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.
The quantum approximate optimization algorithm (QAOA) is a promising method for solving certain classical combinatorial optimization problems on near-term quantum devices. When employing the QAOA to 3-SAT and Max-3-SAT problems, the quantum cost exhibits an easy-hard-easy or easy-hard pattern, respectively, as the clause density is changed. The quantum resources needed in the hard-region problems are out of reach for current noisy intermediate-scale quantum (NISQ) devices. We show by numerical simulations with up to 14 variables and analytical arguments that the adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of the 3-SAT problems and hard region of the Max-3-SAT problems. For similar accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT problems as compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7 levels and 62 levels. The improvement comes from a more targeted and more limited generation of entanglement during the evolution. We demonstrate that classical optimization is not strictly necessary in the ab-QAOA since local fields are used to guide the evolution. This leads us to propose an optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT problems effectively with significantly fewer quantum gates as compared to the original ab-QAOA. Our work paves the way for realizing quantum advantages for optimization problems on NISQ devices.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate algorithm for demonstrating quantum advantage in optimization using near-term quantum computers. However, QAOA has high requirements on gate fidelity due to the need to encode the objective function in the phase separating operator, requiring a large number of gates that potentially do not match the hardware connectivity. Using the MaxCut problem as the target, we demonstrate numerically that an easier way to implement an alternative phase operator can be used in lieu of the phase operator encoding the objective function, as long as the ground state is the same. We observe that if the ground state energy is not preserved, the approximation ratio obtained by QAOA with such phase separating operator is likely to decrease. Moreover, we show that a better alignment of the low energy subspace of the alternative operator leads to better performance. Leveraging these observations, we propose a sparsification strategy that reduces the resource requirements of QAOA. We also compare our sparsification strategy with some other classical graph sparsification methods, and demonstrate the efficacy of our approach.
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.
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum algorithm described as ansatzes that represent both the problem and the mixer Hamiltonians. Both are parameterizable unitary transformations executed on a quantum machine/simulator and whose parameters are iteratively optimized using a classical device to optimize the problem's expectation value. To do so, in each QAOA iteration, most of the literature uses a quantum machine/simulator to measure the QAOA outcomes. However, this poses a severe bottleneck considering that quantum machines are hardly constrained (e.g. long queuing, limited qubits, etc.), likewise, quantum simulation also induces exponentially-increasing memory usage when dealing with large problems requiring more qubits. These limitations make today's QAOA implementation impractical since it is hard to obtain good solutions with a reasonably-acceptable time/resources. Considering these facts, this work presents a new approach with two main contributions, including (I) removing the need for accessing quantum devices or large-sized classical machines during the QAOA optimization phase, and (II) ensuring that when dealing with some k-bounded pseudo-Boolean problems, optimizing the exact problem's expectation value can be done in polynomial time using a classical computer.