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

ADAPT-QAOA with a classically inspired initial state

Vishvesha K. Sridhar, Yanzhu Chen, Bryan Gard, Edwin Barnes, Sophia E. Economou

Published Oct 15, 2023• 1 citation
arXivHTMLPDF

Abstract

Quantum computing may provide advantage in solving classical optimization problems. One promising algorithm is the quantum approximate optimization algorithm (QAOA). There have been many proposals for improving this algorithm, such as using an initial state informed by classical approximation solutions. A variation of QAOA called ADAPT-QAOA constructs the ansatz dynamically and can speed up convergence. However, it faces the challenge of frequently converging to excited states which correspond to local minima in the energy landscape, limiting its performance. In this work, we propose to start ADAPT-QAOA with an initial state inspired by a classical approximation algorithm. Through numerical simulations we show that this new algorithm can reach the same accuracy with fewer layers than the standard QAOA and the original ADAPT-QAOA. It also appears to be less prone to the problem of converging to excited states.

DOI
10.48550/arxiv.2310.09694

Related papers

Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement

Stefan H. Sack, Raimel A. Medina, Richard Kueng +1 more

The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of $p$ layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large $p$ remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of $2p+1$ transition states---saddle points with a unique negative curvature direction---for QAOA with $p+1$ layers that use the local minimum of QAOA with $p$ layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for $p$ layers. We use the Greedy procedure to navigate the exponentially increasing with $p$ number of local minima resulting from the recursive application of our analytic construction. The performance of the Greedy procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers $p$.

arXiv:2209.01159•Physical Review A•Jun 2, 2023•20 citations

Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions

Ken N. Okada, Hirofumi Nishi, Taichi Kosugi +1 more

Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently it has been revealed that warm-start approaches can improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affects the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA achieves higher fidelity (probability that exact solutions are observed) and approximation ratio than QAOA as the Hamming distance of approximate solutions to the exact ones becomes smaller. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having higher fidelity and approximation ratio than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions.

arXiv:2209.02942•Scientific Reports•Jan 12, 2024•8 citations

An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer

Zhu, Linghua, 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ätze. 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.

arXiv:2005.10258•May 20, 2020•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

Quantum approximate optimization via learning-based adaptive optimization

Lixue Cheng, Yuqin Chen, Shi‐Xin Zhang +1 more

Abstract Combinatorial optimization problems are ubiquitous and computationally hard to solve in general. Quantum approximate optimization algorithm (QAOA), one of the most representative quantum-classical hybrid algorithms, is designed to solve combinatorial optimization problems by transforming the discrete optimization problem into a classical optimization problem over continuous circuit parameters. QAOA objective landscape is notorious for pervasive local minima, and its viability significantly relies on the efficacy of the classical optimizer. In this work, we design double adaptive-region Bayesian optimization (DARBO) for QAOA. Our numerical results demonstrate that the algorithm greatly outperforms conventional optimizers in terms of speed, accuracy, and stability. We also address the issues of measurement efficiency and the suppression of quantum noise by conducting the full optimization loop on a superconducting quantum processor as a proof of concept. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.

arXiv:2303.14877•Communications Physics•Mar 6, 2024•48 citations

Quantum approximate optimization algorithm with adaptive bias fields

Yunlong Yu, Chenfeng Cao, Carter Dewey +3 more

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.

arXiv:2105.11946•Physical Review Research•Jun 27, 2022•33 citations
Quantum computing may provide advantage in solving classical optimization problems. One promising algorithm is the quantum approximate optimization algorithm (QAOA). There have been many proposals for improving this algorithm, such as using an initial state informed by classical approximation solutions. A variation of QAOA called ADAPT-QAOA constructs the ansatz dynamically and can speed up convergence. However, it faces the challenge of frequently converging to excited states which correspond to local minima in the energy landscape, limiting its performance. In this work, we propose to start ADAPT-QAOA with an initial state inspired by a classical approximation algorithm. Through numerical simulations we show that this new algorithm can reach the same accuracy with fewer layers than the standard QAOA and the original ADAPT-QAOA. It also appears to be less prone to the problem of converging to excited states.
The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of ppp layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large ppp remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of 2p+12p+12p+1 transition states---saddle points with a unique negative curvature direction---for QAOA with p+1p+1p+1 layers that use the local minimum of QAOA with ppp layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for ppp layers. We use the Greedy procedure to navigate the exponentially increasing with ppp number of local minima resulting from the recursive application of our analytic construction. The performance of the Greedy procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers ppp.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm to solve combinatorial optimization problems in the era of noisy intermediate-scale quantum computers. Recently it has been revealed that warm-start approaches can improve the performance of QAOA, where approximate solutions are obtained by classical algorithms in advance and incorporated into the initial state and/or unitary ansatz. In this work, we study in detail how the accuracy of approximate solutions affects the performance of the warm-start QAOA (WS-QAOA). We numerically find that in typical MAX-CUT problems, WS-QAOA achieves higher fidelity (probability that exact solutions are observed) and approximation ratio than QAOA as the Hamming distance of approximate solutions to the exact ones becomes smaller. We reveal that this could be quantitatively attributed to the initial state of the ansatz. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having higher fidelity and approximation ratio than QAOA especially when the circuit is relatively shallow. We believe that our study may deepen understanding of the performance of WS-QAOA and also provide a guide as to the necessary quality of approximate solutions.
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ätze. 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.
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.
Abstract Combinatorial optimization problems are ubiquitous and computationally hard to solve in general. Quantum approximate optimization algorithm (QAOA), one of the most representative quantum-classical hybrid algorithms, is designed to solve combinatorial optimization problems by transforming the discrete optimization problem into a classical optimization problem over continuous circuit parameters. QAOA objective landscape is notorious for pervasive local minima, and its viability significantly relies on the efficacy of the classical optimizer. In this work, we design double adaptive-region Bayesian optimization (DARBO) for QAOA. Our numerical results demonstrate that the algorithm greatly outperforms conventional optimizers in terms of speed, accuracy, and stability. We also address the issues of measurement efficiency and the suppression of quantum noise by conducting the full optimization loop on a superconducting quantum processor as a proof of concept. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.
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.