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:2409.09012 · International Conference on Quantum Communications, Networking, and Computing (QCNC)

The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution

Sean Feeney, Reuben Tate, Stephan Eidenbenz

Published Mar 31, 2025• 5 citations
arXivHTMLPDF

Abstract

This paper presents a numerical simulation investigation of the Warm-Start Quantum Approximate Optimization Algorithm (QAOA) as proposed by Tate et al. [1], focusing on its application to 3-regular Max-Cut problems. Our study demonstrates that Warm-Start QAOA consistently outperforms theoretical lower bounds on approximation ratios across various tilt angles, highlighting its potential in practical scenarios beyond worst-case predictions. Despite these improvements, Warm-Start QAOA with traditional parameters optimized for expectation value does not exceed the performance of the initial classical solution. To address this, we introduce an alternative parameter optimization objective, the Better Solution Probability (BSP) metric. Our results show that BSP-optimized Warm-Start QAOA identifies solutions at non-trivial tilt angles that are better than even the best classically found warm-start solutions with non-vanishing probabilities. These findings underscore the importance of both theoretical and empirical analyses in refining QAOA and exploring its potential for quantum advantage.

DOI
10.1109/qcnc64685.2025.00077

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

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

Solving General QUBOs with Warm-Start QAOA via a Reduction to Max-Cut

Bikrant Bhattacharyya, Michael Capriotti, Reuben Tate

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.

arXiv:2504.06253•Apr 8, 2025•9 citations

Difference of Convex Algorithm for Warm‐Start Quantum Approximate Optimization Algorithm

Phuc Nguyen Ha Huy, Viết Hùng Nguyễn, Anh Son Ta

Abstract The Quantum Approximate Optimization Algorithm (QAOA) stands as a hybrid classical‐quantum algorithm utilized for addressing combinatorial optimization challenges. Central to its effectiveness is the initial mixer, which is responsible for instigating the optimization process by generating the starting state. However, conventional QAOA implementations often assign equal probabilities to all solutions at the outset, potentially resulting in suboptimal performance when tackling complex combinatorial optimization problems. In this study, a novel enhancement is proposed to the QAOA, leveraging the Difference of Convex Algorithm (DCA). This method aims to refine QAOA's performance by facilitating the discovery of optimal parameters through a continuous warm‐start approach, as originally introduced by Egger et al. Through experimentation utilizing datasets from prior studies focusing on the weighted maximum cut problem, the efficacy of our proposed method is evaluated. Comparative analysis against existing methodologies reveals a significant improvement in the approximate ratio achieved by our approach.

Advanced Quantum Technologies•May 20, 2025•0 citations

Bridging Classical and Quantum with SDP initialized warm-starts for QAOA

Reuben Tate, Majid Farhadi, Creston D. Herold +2 more

We study the Quantum Approximate Optimization Algorithm ( QAOA ) in the context of the Max-Cut problem. Noisy quantum devices are only able to accurately execute QAOA at low circuit depths, while classically-challenging problem instances may call for a relatively high circuit-depth. This is due to the need to build correlations between reachable pairs of vertices in potentially large graphs [ 16 ]. To enhance the solving power of low-depth QAOA, we introduce a classical pre-processing step that initializes QAOA with a biased superposition of possible cuts in the graph, referred to as a warm-start . In particular, we initialize QAOA with a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA , called QAOA-warm , is able to outperform standard QAOA on lower circuit depths in solution quality and training time. While this improvement is partly due to the classical warm-start, we find strong evidence of further improvement using QAOA circuit at small depth. We provide experimental evidence of improved performance as well as theoretical properties of the proposed framework.

arXiv:2010.14021•ACM Transactions on Quantum Computing•Jul 19, 2022•85 citations

Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths

Reuben Tate, Jai Moondra, Bryan Gard +2 more

We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi et al. (2014) to allow for arbitrary separable initial states with corresponding mixers such that the starting state is the most excited state of the mixing Hamiltonian. We demonstrate this version of QAOA, which we call Q A O A − w a r m e s t , by simulating Max-Cut on weighted graphs. We initialize the starting state as a w a r m − s t a r t using 2 and 3 -dimensional approximations obtained using randomized projections of solutions to Max-Cut's semi-definite program, and define a warm-start dependent c u s t o m m i x e r . We show that these warm-starts initialize the QAOA circuit with constant-factor approximations of 0.658 for 2 -dimensional and 0.585 for 3 -dimensional warm-starts for graphs with non-negative edge weights, improving upon previously known trivial (i.e., 0.5 for standard initialization) worst-case bounds at p = 0 . These factors in fact lower bound the approximation achieved for Max-Cut at higher circuit depths, since we also show that QAOA-warmest with any separable initial state converges to Max-Cut under the adiabatic limit as p → ∞ . However, the choice of warm-starts significantly impacts the rate of convergence to Max-Cut, and we show empirically that our warm-starts achieve a faster convergence compared to existing approaches. Additionally, our numerical simulations show higher quality cuts compared to standard QAOA, the classical Goemans-Williamson algorithm, and a warm-started QAOA without custom mixers for an instance library of 1148 graphs (upto 11 nodes) and depth p = 8 . We further show that QAOA-warmest outperforms the standard QAOA of Farhi et al. in experiments on current IBM-Q and Quantinuum hardware.

arXiv:2112.11354•Quantum•Sep 26, 2023•62 citations
This paper presents a numerical simulation investigation of the Warm-Start Quantum Approximate Optimization Algorithm (QAOA) as proposed by Tate et al. [1], focusing on its application to 3-regular Max-Cut problems. Our study demonstrates that Warm-Start QAOA consistently outperforms theoretical lower bounds on approximation ratios across various tilt angles, highlighting its potential in practical scenarios beyond worst-case predictions. Despite these improvements, Warm-Start QAOA with traditional parameters optimized for expectation value does not exceed the performance of the initial classical solution. To address this, we introduce an alternative parameter optimization objective, the Better Solution Probability (BSP) metric. Our results show that BSP-optimized Warm-Start QAOA identifies solutions at non-trivial tilt angles that are better than even the best classically found warm-start solutions with non-vanishing probabilities. These findings underscore the importance of both theoretical and empirical analyses in refining QAOA and exploring its potential for quantum advantage.
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.
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 quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.
Abstract The Quantum Approximate Optimization Algorithm (QAOA) stands as a hybrid classical‐quantum algorithm utilized for addressing combinatorial optimization challenges. Central to its effectiveness is the initial mixer, which is responsible for instigating the optimization process by generating the starting state. However, conventional QAOA implementations often assign equal probabilities to all solutions at the outset, potentially resulting in suboptimal performance when tackling complex combinatorial optimization problems. In this study, a novel enhancement is proposed to the QAOA, leveraging the Difference of Convex Algorithm (DCA). This method aims to refine QAOA's performance by facilitating the discovery of optimal parameters through a continuous warm‐start approach, as originally introduced by Egger et al. Through experimentation utilizing datasets from prior studies focusing on the weighted maximum cut problem, the efficacy of our proposed method is evaluated. Comparative analysis against existing methodologies reveals a significant improvement in the approximate ratio achieved by our approach.
We study the Quantum Approximate Optimization Algorithm ( QAOA ) in the context of the Max-Cut problem. Noisy quantum devices are only able to accurately execute QAOA at low circuit depths, while classically-challenging problem instances may call for a relatively high circuit-depth. This is due to the need to build correlations between reachable pairs of vertices in potentially large graphs [ 16 ]. To enhance the solving power of low-depth QAOA, we introduce a classical pre-processing step that initializes QAOA with a biased superposition of possible cuts in the graph, referred to as a warm-start . In particular, we initialize QAOA with a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA , called QAOA-warm , is able to outperform standard QAOA on lower circuit depths in solution quality and training time. While this improvement is partly due to the classical warm-start, we find strong evidence of further improvement using QAOA circuit at small depth. We provide experimental evidence of improved performance as well as theoretical properties of the proposed framework.
We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi et al. (2014) to allow for arbitrary separable initial states with corresponding mixers such that the starting state is the most excited state of the mixing Hamiltonian. We demonstrate this version of QAOA, which we call Q A O A − w a r m e s t , by simulating Max-Cut on weighted graphs. We initialize the starting state as a w a r m − s t a r t using 2 and 3 -dimensional approximations obtained using randomized projections of solutions to Max-Cut's semi-definite program, and define a warm-start dependent c u s t o m m i x e r . We show that these warm-starts initialize the QAOA circuit with constant-factor approximations of 0.658 for 2 -dimensional and 0.585 for 3 -dimensional warm-starts for graphs with non-negative edge weights, improving upon previously known trivial (i.e., 0.5 for standard initialization) worst-case bounds at p = 0 . These factors in fact lower bound the approximation achieved for Max-Cut at higher circuit depths, since we also show that QAOA-warmest with any separable initial state converges to Max-Cut under the adiabatic limit as p → ∞ . However, the choice of warm-starts significantly impacts the rate of convergence to Max-Cut, and we show empirically that our warm-starts achieve a faster convergence compared to existing approaches. Additionally, our numerical simulations show higher quality cuts compared to standard QAOA, the classical Goemans-Williamson algorithm, and a warm-started QAOA without custom mixers for an instance library of 1148 graphs (upto 11 nodes) and depth p = 8 . We further show that QAOA-warmest outperforms the standard QAOA of Farhi et al. in experiments on current IBM-Q and Quantinuum hardware.