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.
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.
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.
Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RWS-QAOA), which initializes qubits by minimizing expected energy with a regularizer that penalizes near-bitstring states, preventing QAOA from stalling. We further propose a protocol that yields fixed, instance-independent parameters, enabling RWS-QAOA to operate as a non-variational algorithm in which the quantum circuit parameters are fixed and only a classical warm starting step is instance-dependent. We evaluate RWS-QAOA on the Max-Cut problem for random regular graphs, where this protocol yields a constant-depth quantum circuit, across three complementary settings. First, on Quantinuum's trapped-ion processor, RWS-QAOA outperforms the classical algorithms with the best provable guarantees for Max-Cut on 3-regular graphs, namely Goemans-Williamson and Halperin-Livnat-Zwick, on 96-node instances. Second, tensor-network simulations on graphs with up to N=10,000 nodes show that depth-6 RWS-QAOA, achieving an average cut fraction of 0.9167, surpasses the best classical heuristics under matched restrictions (no local-search post-processing and no iterative refinement). Third, we remove these restrictions and benchmark against the strongest unrestricted classical heuristics, including an optimized parallel Burer-Monteiro solver that improves upon the MQLib implementation. Even against this stronger baseline, we project that surface-code RWS-QAOA reaches a quantum-classical runtime crossover below 0.2 seconds on 3,000-node graphs with fewer than 1.3 million physical qubits. Our results show that constant-depth quantum circuits combined with a classical warm start have a credible potential to surpass classical solvers on the Max-Cut problem when executed on future quantum computers.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-k-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth p=1
We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle θ, we consider warm-starts where the initial state is a product state where each qubit position is angle θ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring b. We illustrate through plots how the properties of b and the initialization angle θ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the classical algorithm used to create the warm-start. Additionally, we show that at θ=60∘, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion.
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 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 optimization algorithms, such as the Quantum Approximate Optimization Algorithm, are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such as XY mixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with an XY mixer ansatz, enabling constraint-preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over valid one-hot quantum states, maintaining compatibility with the XY mixer's constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world Vehicle Routing Problems. Our method is benchmarked against both the standard XY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.