Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm

Yunlong Yu, Xiang-Bin Wang, Nic Shannon, Robert Joynt · 2025

Read Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm by Yunlong Yu, Xiang-Bin Wang, Nic Shannon, Robert Joynt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20048.txt.

Introduction

Yunlong Yu, Xiang-Bin Wang, Nic Shannon, and Robert Joynt boost a quantum optimizer with a classical head start in a 2025 paper. Quantum approximate optimization can refine answers that good classical methods find first. How best to blend the two remains an open design question.

The authors build a general model covering a family of warm-start variants. For the classic MaxCut problem they derive exact formulas for the first level's expected score. Those formulas allow fair averaging over many random instances at forty to one hundred eighty qubits. A variant seeded by a leading classical algorithm beats earlier warm-start designs in their tests. The study maps where quantum refinement may add real value over classical seeds.

Catalog record

CREATORYunlong Yu, Xiang-Bin Wang, Nic Shannon, Robert Joynt
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20048

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm Yunlong Yu, Xiang-Bin Wang, Nic Shannon, Robert Joynt Abstract 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 40 to 180 180 qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to 1000 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 1000 -qubit case even in level 1 can only be matched by the GW algorithm after about 10 5.5 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. I Introduction Quantum computing hardware continues to make strides [ 1 , 2 , 3 ] . Most recently, quantum error correction has been successfully demonstrated [ 4 , 5 , 6 , 7 , 8 , 9 , 10 ] . However, large-scale fault-tolerant quantum computation [ 11 , 12 ] is still out of reach and we have not yet emerged from the age of noisy intermediate-scale quantum (NISQ) devices [ 13 ] . On this intermediate time scale, hybrid quantum-classical algorithms such as the variational quantum algorithm (VQA) [ 14 , 15 , 16 , 17 ] are some of the most promising quantum algorithms to realize a quantum advantage. For many paradigmatic combinatorial optimization problems, the leading candidate among hybrid algorithms is the quantum approximate optimization algorithm (QAOA). It can be thought of as a kind of flexible Trotterization of a continuous quantum annealing process [ 18 , 19 , 20 , 21 ] . Extensive experimental demonstrations [ 22 , 23 , 24 , 25 ] with up to 289 qubits using Rydberg atom arrays [ 23 ] and numerical simulations for up to 54 qubits with neural networks [ 26 ] have explored the possibility of a quantum advantage for QAOA. The canonical benchmarking problem for QAOA in the literature is the MaxCut problem [ 18 , 19 , 20 , 21 , 27 , 28 ] , which aims to cut the vertex set of a graph into two subsets in such a way as to maximize the number of cuts, the edges connecting the two subsets. The performance criterion for an algorithm is usually the approximation ratio r [ 18 , 19 ] . This is defined as the calculated cut value divided by the exact maximal cut value. It is NP-hard to obtain the solution with r\geq 16/17\approx 0.941 on arbitrary graphs [ 29 ] . The Goemans-Williamson (GW) algorithm is based on a semi-definite program (SDP) [ 30 ] followed by a random projection to produce an approximate solution. It solves the MaxCut problem in polynomial time with a guarantee that r\geq 0.878 for arbitrary graphs [ 31 ] . There is evidence that this value cannot be substantially improved classically. Modifications to the SDP and the projection are not effective in doing so [ 32 ] , and more generally, an improvement would contradict the Unique Games Conjecture [ 33 , 34 ] . This possible gap between P and NP-hard is very suggestive: does there exist an intermediate r -value such that the problem is NP-intermediate, and thus analogous to factoring? Such problems are promising candidates for a quantum advantage. To find an approximate solution to the MaxCut problem or other combinatorial optimization problems through QAOA, the problem is converted into a cost Hamiltonian H_{\mathrm{C}} of the Ising type, meaning that it contains only Pauli Z operators. Its ground state or the most highly excited state represents the solution [ 35 ] . The evolution starts from the ground state of the mixing Hamiltonian H_{\mathrm{M}}^{\mathrm{s}} , which is usually the uniform superposition of Pauli X operators of all the qubits. The unitary operators \exp(-i\beta_l H_\mathrm{M}^\mathrm{s}) and \exp(-i\gamma_l H_\mathrm{C}) are alternately applied p times to produce the approximate solution. p is referred to the level. The schedule parameters \vec{\beta} and \vec{\gamma} are trained to optimize the expectation values of the cost Hamiltonian [ 18 , 19 ] . Vector notation such as \vec{\beta} and \vec{\gamma} will be used to represent a set of parameters \{\beta_{1},\beta_{2},...,\beta_{p}\} and \{\gamma_{1},\gamma_{2},...,\gamma_{p}\} henceforth. To enhance the prospects for quantum advantage, numerous strategies have been proposed to further improve the QAOA, such as heuristic initialization methods of the schedule parameters [ 19 , 36 ] , modifications of the cost Hamiltonian [ 37 , 38 ] and the mixing Hamiltonian [ 28 , 39 , 40 , 34 ] . For the purposes of this paper, there are two types of modifications that are of most interest: inclusion of bias fields in the mixing Hamiltonian [ 28 , 39 ] , and warm start, in which an approximate solution from a classical solver is used to determine the ansatz [ 34 , 41 , 42 , 43 ] . The adaptive-bias quantum approximate optimization algorithm (ab-QAOA) includes the adaptive longitudinal bias fields [ 44 ] in the mixing Hamiltonian which are updated in the optimization process [ 28 , 39 ] . The starting state is the ground state of the modified mixing Hamiltonian. For the MaxCut problem where the QAOA performs very well [ 18 , 19 ] and the SAT/Max-SAT problems where the QAOA appears to have difficulties [ 45 , 46 ] , the ab-QAOA has demonstrated a considerable speedup over the QAOA. The well-known easy-hard-easy phase transitions in the SAT problems [ 45 ] and the reachability-deficit phenomenon in the Max-SAT problems [ 46 ] are almost absent in the ab-QAOA. The recently proposed warm start QAOA variants modify the ansatz to encode the approximate solution from the classical solver [ 34 , 41 , 42 ] . Additional Pauli Y , Z operators operators are introduced in the mixing Hamiltonian and the starting state is accordingly adjusted either for recovering the input classical solution [ 34 ] or satisfying the adiabaticity in the limit p\rightarrow\infty [ 41 ] . The simulation on small-scale graphs suggests the superiority of warm start QAOA over the GW algorithm [ 34 , 41 ] . This motivates us to combine

Read the complete text