PaperlayerView exact revision on arXiv

Source-linked AI summary

Warm-starting quantum optimization

Daniel J. Egger, Jakub Marecek, Stefan Woerner

arXiv:2009.10095v4quant-ph

TL;DR

Quantum optimization lacks the classical approximation guarantees available from continuous relaxations and randomized rounding. The paper warm-starts quantum algorithms with relaxation-derived states, showing that they can inherit classical guarantees and improve low-depth performance in portfolio optimization and MAXCUT settings.

  • Problem

    The paper asks how quantum optimization can obtain approximation guarantees comparable to classical methods based on continuous relaxations and randomized rounding.

  • Method

    The paper initializes QAOA-based algorithms using solutions of continuous relaxations, including semidefinite-program solutions and Goemans-Williamson randomized rounding.

  • Results

    Warm-started quantum algorithms inherit classical relaxation guarantees, with improved low-depth portfolio solutions and systematic Recursive QAOA improvements for warm-started MAXCUT.

  • Takeaways & Limitations

    Warm-starting provides a framework for quantum optimization algorithms applicable to other relaxed binary or combinatorial optimization problems.

  • Takeaways & Limitations

    The analysis is constrained by assumptions such as the Unique Games Conjecture for impossibility of improving Goemans-Williamson guarantees, and some simulations use limited graph instances.

Abstract

from arXiv · show

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

1 Introduction

The paper motivates warm-starting QAOA with solutions from continuous relaxations to improve guarantees and performance while retaining quantum optimization structure.

  • Quantum approximate optimization: QAOA encodes a combinatorial optimization problem in a cost Hamiltonian and optimizes alternating mixer and cost-evolution layers.A classical optimizer selects the layer parameters to minimize the cost-Hamiltonian energy.
  • Related approaches: The paper examines prior empirical improvements to QAOA, including mixer choices, reinforcement learning, multi-start methods, and local optimization.These approaches aim to improve convergence or navigate the QAOA optimization landscape.
  • Classical relaxations: Continuous relaxations, often semidefinite programs, can be solved efficiently and converted into discrete solutions through randomized rounding.For MAXCUT, Goemans-Williamson rounding achieves an expected α fraction of the global optimum, with 0.87856 < α < 0.87857.
  • Guarantees and results: For MAXCUT, the warm-start can preserve the Goemans-Williamson approximation ratio at any QAOA depth.Simulations consistently perform as well as the Goemans-Williamson algorithm or better.
  • Warm-start framework: Warm-starting uses a relaxation-derived initial solution to provide QAOA with a favorable starting point for combinatorial optimization.The paper studies continuous relaxations of Quadratic Unconstrained Binary Optimization problems and uses Goemans-Williamson rounding to warm-start Recursive QAOA.

2 Warm-start Quantum Optimization

Warm-starting replaces QAOA’s equal-superposition initialization with states derived from continuous relaxations or rounded solutions, while adapting the mixer accordingly. The approach addresses reachability constraints and can preserve classical approximation guarantees, subject to resource and complexity limits.

  • 2.1 Preliminaries: QUBO uses binary decision variables, and its continuous relaxation is efficiently solvable when the quadratic matrix is positive semidefinite.
  • 2.1 Preliminaries: Semidefinite relaxations provide alternative continuous solutions and can be followed by randomized rounding to produce discrete QUBO solutions with approximation guarantees.The basic SDP relaxation can be solved classically to fixed precision in polynomial time.
  • 2.2 Continuous warm-start QAOA: Warm-starting initializes QAOA with a state corresponding to a continuous relaxation rather than |+⟩⊗n, with each qubit rotation determined by the relaxed solution coordinate.The probability of measuring |1⟩ in qubit i equals c∗_i.
  • 2.2 Continuous warm-start QAOA: The warm-start mixer is implemented as ˆRY(θi) ˆRZ(−2β) ˆRY(−θi), rotating around an axis determined by the initial-state angle.The circuit applies the mixer after the time-evolved problem Hamiltonian.
  • 2.2 Continuous warm-start QAOA: A regularization parameter ε interpolates between warm-start and standard QAOA and mitigates reachability issues caused by coordinates at the binary endpoints.At ε = 0.5, the initial state is the equal-superposition state and the mixer is the X operator.
  • 2.2 Continuous warm-start QAOA: For interior relaxation coordinates or ε > 0, WS-QAOA converges to the QUBO optimum as depth p approaches infinity, while parameter optimization seeks faster evolution.The warm-start construction can inherit classical approximation guarantees, while stronger relaxations may require impractical qubit counts or super-polynomial preprocessing.

3 Simulations with Continuous-Valued Warm-start

Continuous-relaxation warm starts improve QAOA performance for portfolio optimization, especially at low depth, and the modified mixer also accelerates annealing convergence.

  • Portfolio QAOA: More than 5 times higher probability of sampling the optimal binary solution occurs with WS-QAOA than standard QAOA for depths 1 ≤ p ≤ 5.The warm-start optimized energy is also closer to the minimum energy E0.
  • Portfolio QAOA: At depth p ≥ 4, standard QAOA can satisfy the budget constraint but still samples the optimal solution with low probability.Low energy alone does not imply high probability of obtaining the optimal portfolio.
  • Portfolio QAOA: The warm-start mixer is needed when initializing with the continuous solution, because the unmodified mixer does not converge to the minimum energy.With the standard mixer, optimal-solution sampling depends strongly on COBYLA's initial point.
  • Low-depth portfolio results: Across 250 random portfolio instances at depth p = 1, WS-QAOA produces optimized variational states much closer to each problem's minimum energy than standard QAOA.WS-QAOA tends to perform better when the overlap d∗T c∗/B between discrete and continuous optima is closer to 1.
  • Trotterized annealing: Warm-start annealing requires less total time T and fewer Trotter steps N than the equal-superposition mixer to minimize energy.At T = 40 and N = 60, the warm-start mixer has lower initial and final energies, indicating faster convergence.

4 Simulations with Rounded Warm-Start

The section studies rounded warm starts for QAOA and Recursive QAOA on MAXCUT, including their dependence on regularization, depth, graph structure, and initialization. Warm-started variants can outperform classical or standard quantum baselines in the reported simulations, although low-depth expressivity and optimization landscapes remain limiting factors.

  • MAXCUT warm starts: MAXCUT is encoded as a graph partitioning problem whose classical guarantees motivate warm-starting QAOA with Goemans-Williamson-rounded solutions.Under the Unique Games Conjecture, random-hyperplane rounding provides the best classical polynomial-time guarantees described here.
  • Regularization and WS-QAOA: At ε = 0, the median normalized energy is 0.907, while at ε = 0.25 it rises to 0.929 and exceeds the energy of the GW warm-start cuts.The normalized energy initially decreases as ε increases, then begins increasing around ε = 0.15.
  • Recursive QAOA: WS-RQAOA outperforms standard RQAOA in simulations, although the number of maximum cuts found decreases as graph size increases and fully connected 30-node graphs are hardest.The benchmark compares random sparse graphs and fully connected graphs with random signed weights.
  • Recursive QAOA: The classical recursive solver using correlations from the five best GW cuts performs better than standard RQAOA but slightly worse than WS-RQAOA.The comparison is shown against the recursive classical procedure described for Fig. 8.
  • Optimization landscape: For depth greater than one, deeper WS-QAOA trial states need not remain at the initial GW cut, while the six-node graph has a maximum cut of size 27 and starts from a cut of size 23.The deeper variational form is more flexible, but its optimum is no longer necessarily the initial cut.
  • Optimization landscape: At depth one, random parameter initialization can miss the optimal β1 = π/2 and γ1 = 0 because the QAOA energy landscape is non-convex with many local minima.This optimization difficulty may explain why optimized trial-state energy decreases slowly with depth for the six-node example.

5 Discussion and Conclusion

The discussion presents warm-start quantum optimization as a framework that can inherit classical relaxation guarantees and reports advantages at low circuit depth. It also identifies scope boundaries and several directions for extending the approach.

  • Guarantees: Warm-start quantum algorithms can achieve the same guarantees as the classical relaxations on which they are based.Under the Unique Games Conjecture, these guarantees cannot be improved by polynomial-time classical or quantum algorithms unless NP-Hard problems become polynomial-time solvable.
  • Empirical implications: Warm-starting provides an advantage at low depth, with portfolio simulations finding better solutions than standard QAOA.This is especially relevant for dense problems intended for noisy hardware that struggles with deep circuits.
  • Algorithmic framework: WS-QAOA can be continuously transformed into conventional QAOA using the regularization parameter ε.The paper also applies Goemans-Williamson warm starts to Recursive QAOA, while noting an inconsistency between the mixer and initial state.
  • Limitations and future work: The reported Recursive QAOA results are limited by application to a single graph at depths p > 1, motivating tests on more graphs and sizes.The discussion also proposes modified mixers and additional warm-start sources as future work.
  • Scope: The framework is expected to extend to other combinatorial optimization and integer-programming problems with good randomized-rounding solutions.Potential encodings include QUBO, mixed-integer linear, and polynomial unconstrained binary optimization formulations.

A The Unique Games Conjecture

This appendix summarizes the Unique Games Conjecture and its connection to approximation hardness. It states the conjecture through unique label cover instances and explains why semidefinite relaxations are central to the discussion.

  • PCP background: The PCP theorem implies that approximating the satisfiable fraction of certain constraint-satisfaction problems within a constant factor is NP-Hard.For constraints involving at most k variables, the stated gap separates fully satisfiable instances from instances where every assignment satisfies fewer than an α fraction.
  • Unique label cover: Unique label cover uses a bipartite graph, an alphabet, and edge-specific bijections to define consistency constraints between assignments.The appendix relates this formulation to MAXCUT.
  • Unique Games Conjecture: The Unique Games Conjecture asserts that, for arbitrarily small ζ and δ, distinguishing optimum at least 1 − ζ from at most δ is NP-Hard for some alphabet size k.The alphabet size is specified as k = |M| and may depend on ζ and δ.
  • Approximation consequences: Under the UGC, a canonical semidefinite-programming relaxation provides the best possible approximation ratio for a constraint-satisfaction problem.The appendix notes that the conjecture remains neither proven nor disproven.
  • Quantum-complexity context: Quantum-complexity work considers related two-prover games in which provers may share entanglement, including results on unique games with entangled provers.The cited result uses polynomial-time rounding of an SDP relaxation in a setting with more than two possible answers.

B Goemans-Williamson Algorithm

The Goemans-Williamson algorithm solves the MAXCUT semidefinite relaxation and rounds its vector solution with a uniformly random hyperplane. For positive edge weights, this achieves an average cut size of 87.9% of the maximum, which is classically optimal under the Unique Games Conjecture.

  • GW first solves the MAXCUT semidefinite relaxation, replacing binary variables with unit-norm vectors.
  • A uniformly random unit-sphere vector defines a hyperplane, and each node is assigned according to the sign of its vector’s inner product with that vector.
  • 87.9%: GW cuts are guaranteed on average to reach 87.9% of the maximum-cut size for positive edge weights.
  • The expected rounded cut size is expressed relative to the maximum-cut value through the GW hardness factor.
  • Under the Unique Games Conjecture, this guarantee is the best achievable by any classical polynomial-time algorithm.

C Extensions towards QUBO

MAXCUT is a special case of QUBO, and related hardness results extend to real-valued edge weights and broader constraint-satisfaction formulations. Randomized rounding of semidefinite relaxations achieves the associated optimum hardness factors, while experiments quantify GW performance on random graphs.

  • MAXCUT is a special case of QUBO, with matrix constructions linking edge-weighted cut instances to quadratic binary optimization.
  • Constraint-satisfaction formulations provide semidefinite relaxations and subsequent rounding procedures for many combinatorial optimization problems.
  • For real-valued edge weights, MAXCUT generalizes the presented QUBO without requiring a symmetric matrix.
  • For every ϵ > 0, distinguishing QUBO instances with optima at least 2k − w from those at most 2αk − w is NP-Hard under the stated MAXCUT premise.
  • The resulting QUBO bound ratio is α + w/(α − 1)(2k − w).
  • The optimum hardness factor is achieved by randomized rounding of a semidefinite-programming relaxation.
  • 85.2% and 83.7%: GW averages reached these normalized cut sizes for the two random-graph ensembles described in the experiments.
  • 61 maximum cuts were found at N = 10^5 for fully connected graphs.

D A Stochastic-Analysis Viewpoint

Randomized rounding can be viewed through stochastic processes that convert random unit vectors into binary signs. The paper relates sticky Brownian-motion constructions to semidefinite-rounding guarantees and connects these ideas to recursive QAOA.

  • Randomized rounding procedures generate random unit vectors and produce signs through an associated stochastic process.
  • The sign is extracted when the relevant stochastic process first reaches the values −1 or 1, using Brownian motion.
  • A speed function extends sticky Brownian motion to a slowed-down process under stated assumptions.
  • A different speed function can recover the Goemans-Williamson constant, although the constant in an earlier equation is not exactly GW’s.
  • The stochastic-analysis formulation uses the standard Gaussian cumulative distribution function in its rounding characterization.
  • The proof interprets the process as discrete-time Krivine diffusions and applies a theorem from prior work.
  • RQAOA recursively eliminates variables by using the largest-magnitude QAOA correlator to replace one spin with a signed copy of another.

F Depth-one RQAOA

Depth-one Recursive QAOA can be simulated by tracking two-qubit density matrices to evaluate correlators, then recursively reducing the MAXCUT instance. Variable elimination updates graph weights while discarding only an optimization-irrelevant energy offset.

  • Depth-one RQAOA evaluates each correlator using only the density matrix of the corresponding two qubits.
  • For every other qubit, the reduced density matrix is updated using the associated two-qubit gates and mixture coefficient.
  • Single-qubit phases are moved to the circuit front because controlled-phase gates commute with the single-qubit gate.
  • The two-qubit interaction and mixer are then applied before measurement, completing the depth-one correlator computation.
  • Replacing one MAXCUT spin by ± another produces a new MAXCUT problem with one fewer node.
  • The eliminated node’s incident weights are absorbed into the surviving node’s weights, while the first sum contributes only an energy offset.
  • The depth-one warm-started QAOA energy is normalized to the maximum-cut energy as a function of ε, using a mixer that cannot reproduce GW at ε = 0.25.

H Portfolio data

The portfolio experiments construct asset-price data by simulating Geometric Brownian motion over 250 days, then derive returns, means, and covariances.

  • 250 days of asset-price trajectories are simulated using Geometric Brownian motion.Each asset price is generated day by day.
  • Initial asset prices are fixed at 1, with means sampled uniformly from [−5%, 5%] and standard deviations from [−20%, 20%].
  • Daily returns are computed from consecutive prices, while mean returns and covariances are estimated across the simulated days.Covariances are calculated pairwise from the return series.

I WS-QAOA for MAXCUT with the warm-start mixer

The study compares WS-QAOA variants for MAXCUT using the Eq. (2) mixer and a modified mixer that retains the Goemans–Williamson cut. Their performance is similar in one analysis, but the Eq. (2) variant degrades as graph difficulty grows.

  • WS-QAOA with the warm-start mixer: The Eq. (2) mixer is studied by repeating the analyses used for the modified warm-start mixer.
  • WS-QAOA with the warm-start mixer: The Eq. (2) mixer produces normalized energy that decreases with ε and does not recover at ε = 0.25.This behavior is shown in Fig. 14.
  • WS-QAOA with the warm-start mixer: As graph size and complexity increase, WS-RQAOA with the Eq. (2) mixer performs worse than the modified-mixer variant.The comparison indicates that retaining the GW cut becomes increasingly important.
Loading 2009.10095v4…