Source-linked AI summary
Multistart Methods for Quantum Approximate Optimization
Ruslan Shaydulin, Ilya Safro, Jeffrey Larson
TL;DR
QAOA’s variational optimization depends on classical parameter search in a nonconvex landscape with many local optima. This paper applies multistart optimization and parameter reuse to QAOA, reporting more efficient use of evaluation budgets and improved outcomes on similar problems. The discussion also notes practical hardware-connectivity constraints for the studied clustering problem.
Problem
Variational QAOA needs reliable classical optimization in a nonconvex parameter space with many low-quality local optima, which can trap local optimizers.
Source: §I · p. 1Method
The paper evaluates multistart APOSMM for QAOA parameter optimization and reuses optimal parameters from similar problems as starting points for local refinement.
Source: §I · p. 2, §IV · p. 4, §VI · p. 6Results
APOSMM finds better parameters than single-start local search at the same evaluation count, while reuse on similar problems improves solution quality and reduces required evaluations.
Source: §I · p. 2Takeaways & Limitations
Multistart search can use a fixed evaluation budget more efficiently, and reusing parameters can reduce amortized optimization cost across changing problems.
Source: §VI · p. 6The studied modularity-maximization problem requires all-to-all connectivity, unlike the nearest-neighbor connectivity of many superconducting-qubit implementations.
Source: §VI · p. 6
Abstract
from arXiv · showhide
Hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) are considered one of the most promising approaches for leveraging near-term quantum computers for practical applications. Such algorithms are often implemented in a variational form, combining classical optimization methods with a quantum machine to find parameters to maximize performance. The quality of the QAOA solution depends heavily on quality of the parameters produced by the classical optimizer. Moreover, the presence of multiple local optima in the space of parameters makes it harder for the classical optimizer. In this paper we study the use of a multistart optimization approach within a QAOA framework to improve the performance of quantum machines on important graph clustering problems. We also demonstrate that reusing the optimal parameters from similar problems can improve the performance of classical optimization methods, expanding on similar results for MAXCUT.
I. INTRODUCTION
Hybrid quantum-classical algorithms pair a classical optimizer with a quantum device, and variational QAOA relies on classical optimization to find useful parameters. This paper studies multistart optimization for QAOA and reusing parameters across similar problems.
I. INTRODUCTION
- NISQ devices have fewer than 100 qubits, high error rates, and restricted algorithms, motivating interest in practical applications for near-term quantum computers.Hybrid algorithms use shallow-depth circuits that can run on NISQ computers without error correction.Source: §I · p. 1
- QAOA typically uses a classical optimizer to vary parameterized gates, although some problems admit analytically derived parameters.The paper focuses on variational QAOA, while noting the approach can also apply to VQE.Source: §I · p. 1
- In variational QAOA, the quantum processor prepares and measures a parameterized trial state, and the classical optimizer updates parameters toward the ground-state energy of the cost Hamiltonian.The ground state encodes the classical optimization problem’s global optimum.Source: §I · p. 1
- QAOA parameter optimization is difficult because its nonconvex parameter space contains many low-quality, nondegenerate local optima where local optimizers can get stuck.The paper frames reliable, efficient optimization as important because function-evaluation counts translate directly into variational-algorithm performance.Source: §I · p. 1
- Multistart APOSMM finds better QAOA parameters than single-start local search at the same objective-evaluation budget, while parameter reuse improves solution quality and reduces evaluations on similar problems.These are the paper’s two stated contributions.Source: §I · p. 2
- Prior QAOA results include empirical and theoretical comparisons with classical approaches, including MAXCUT and bounded-occurrence Max E3LIN2.The paper notes that a later classical algorithm outperformed QAOA on Max E3LIN2.Source: §I · p. 2
II. PROBLEM DEFINITION
The paper formulates QAOA for modularity maximization in graph community detection. It encodes the maximization objective in a cost Hamiltonian and searches over parameters in an alternating-operator ansatz.
II. PROBLEM DEFINITION
- For maximization, the cost Hamiltonian is constructed so its highest-energy eigenstate encodes the solution, and the hybrid algorithm seeks parameters that prepare that state.This differs from the lowest-energy convention commonly used in VQE.Source: §II · p. 2
- QAOA starts in |+⟩⊗n and applies alternating operators based on the cost and mixing Hamiltonians; the number of steps p sets the sequence length.The objective is the cost-Hamiltonian energy in the resulting state, and the optimizer chooses parameters to minimize it.Source: §II · p. 2
- The objective is periodic in β and γ, so the parameter search is restricted to β_i ∈ [0, π] and γ_i ∈ [0, 2π], giving a compact domain.The full domain is D = ([0, π] × [0, 2π])^p.Source: §II · p. 2
- The target problem is modularity maximization for network community detection, which groups vertices by connectivity relative to a random-graph model.Modularity often favors many within-group edges and few between-group edges; general-graph modularity maximization is NP-hard.Source: §II · p. 2
- The paper focuses on the alternating-operator ansatz rather than hardware-efficient or nearest-neighbor ansatzes because it reports no evidence that those alternatives beat the best classical algorithms.For modularity maximization, variables are mapped to Pauli spin operators in the cost Hamiltonian.Source: §II · p. 2
III. RELATED WORK
Prior work includes analytical and grid-based approaches to QAOA parameter selection, but finding good parameters remains challenging. The figure contrasts a single local-optimizer run with a multistart trace on one objective landscape.
III. RELATED WORK
- For one-step QAOA on MAXCUT, analytical parameters are available for k-regular triangle-free graphs and one-dimensional antiferromagnetic rings, while grid discretization requires N^O(p) evaluations.The grid approach is described as impractical even for small p, motivating further parameter-search methods.Source: §III · pp. 2–3
- The figure compares queried (β, γ) points from one COBYLA run with APOSMM coordinating multiple COBYLA instances, with 200 function evaluations allotted to each method.White indicates higher objective values; the caption does not state which method performs better in this example.Source: Figure 1 · p. 3
- The paper frames finding good QAOA parameters as a continuing challenge despite analytical results for particular problem classes and the grid-based proposal.The grid proposal’s evaluation requirement is N^O(p).Source: §III · p. 3
A. Parameter optimization in hybrid algorithms
Prior work examines derivative-free optimization, parameter schedules, and periodicity in QAOA. It also motivates reusing parameters across similar problem instances and refining them locally.
A. Parameter optimization in hybrid algorithms
- Derivative-free black-box methods remain common because quantum-circuit gradients may be unavailable or expensive to approximate, and gradient methods can be noise-sensitive.Methods used include Nelder–Mead, Bayesian methods, Powell’s method, and interior-point minimization.Source: A. Parameter optimization in hybrid… · p. 3
- Optimal QAOA parameters have been connected to adiabatic schedules, with small variation reported between similar instances and reused parameters refined by local optimization.The paper reports confirming this parameter similarity for a different graph problem.Source: A. Parameter optimization in hybrid… · p. 3
- Prior work proposed reusing optimal parameters between problems from the same distribution and refining them locally; this paper applies that strategy to modularity clustering.The paper notes this problem’s clause count per variable grows with n.Source: A. Parameter optimization in hybrid… · p. 3
- Because periodicity results are problem-specific, the paper restricts β_i to [0, π] and γ_i to [0, 2π], following [10].It distinguishes this choice from [21], which did not constrain β and γ.Source: A. Parameter optimization in hybrid… · p. 3
B. Derivative-free optimization methods
Derivative-free optimization (DFO) methods optimize using objective-function observations rather than gradients, which are unavailable on real quantum computers. Multistart strategies seek better local optima while avoiding redundant evaluations.
B. Derivative-free optimization methods
- DFO methods use objective-function observations without gradients; BOBYQA builds quadratic objective models and optimizes them over a trust region to propose candidate points.The paper notes that modern DFO methods can reduce the number of function evaluations required.Source: B. Derivative-free optimization methods · p. 4
- Starting local optimizations from different initial conditions may find better optima, but can require unnecessary objective-function evaluations.With finitely many local optima, the ideal would identify each with one local run.Source: B. Derivative-free optimization methods · p. 4
- MLSL samples the domain and starts runs at points without a better neighbor within a radius; APOSMM generalizes it by also considering points generated by local runs.The cited favorable MLSL radius-update results are asymptotic.Source: B. Derivative-free optimization methods · p. 4
IV. DIFFICULTY OF OPTIMIZING QAOA PARAMETERS
On six small synthetic community-detection graphs, APOSMM outperformed single-start local methods and remained stronger than restarted methods under a shared evaluation budget. Optimization became harder as QAOA depth increased.
IV. DIFFICULTY OF OPTIMIZING QAOA PARAMETERS
- The comparison used noiseless Qiskit Aer simulations, six derivative-free local methods, and APOSMM with BOBYQA on six 10–12-vertex synthetic graphs.The graphs were three connected-caveman and three random-partition instances; each method had a 1,000-evaluation limit, estimated at about 16 minutes under the stated assumptions.Source: §IV · p. 4
- APOSMM found higher objective values than single-run local solvers, which could converge before using the 1,000-evaluation budget.Figure 2 compares objective-value ratios across 60 runs; its 1.0 reference is the maximum observed for each problem and p.Source: §IV · p. 4, Figure 2 · p. 5
- With matched tolerances and random restarts after convergence, APOSMM still solved more problems within the same function-evaluation budget.Figure 3 data profiles track the fraction solved to level τ against evaluations; the figure compares seven methods at τ = 0.01.Source: §IV · p. 4, Figure 3 · p. 5
- 60% and 40% of problems were solved by APOSMM for p = 2 and p = 4, respectively, within 1,000 evaluations; direct parameter optimization remained difficult at p = 4.For p = 1, BOBYQA and APOSMM solved most problems within the same budget.Source: §IV · p. 5, Figure 3 · p. 5
V. REUSING OPTIMAL QAOA PARAMETERS
The paper reuses optimal QAOA parameters from one graph as initial points for similar edge-removed graphs. Reused points let optimization methods find higher-quality solutions within the same evaluation budget, including in worst-case changes.
V. REUSING OPTIMAL QAOA PARAMETERS
- Optimal parameters found by exhaustive search seed local solvers on similar graphs formed by removing an edge.The authors frame this as a way to amortize the cost of finding good parameters for changing graphs, such as social networks with added or removed connections.Source: §V · pp. 5–6
- Reusing precomputed optimal points yields higher objective values within the same evaluation budget, across random edge removals and worst-case edge changes.Figure 4 compares the best-performing local method and APOSMM with reused versus random initial points; its left panel summarizes 300 runs, while the right uses one worst-case edge removal per problem.Source: Figure 4 · p. 6, §V · p. 6
- For worst-case tests, the removed edge is the one producing the greatest change in the graph Laplacian eigenvectors.The change is measured by Euclidean distance between the Laplacian eigenvectors before and after removal.Source: §V · p. 6
VI. DISCUSSION
The discussion reports that multistart methods use a fixed evaluation budget more efficiently, while QAOA parameter optimization becomes harder as its step count and domain dimension increase. Reusing parameters can partially address that challenge, though hardware connectivity remains a constraint for modularity maximization.
VI. DISCUSSION
- Multistart methods such as APOSMM use a fixed number of function evaluations more efficiently by interleaving local runs and considering all generated parameter points.The discussion also notes that optimizing QAOA parameters becomes harder as the number of steps and the corresponding domain dimension increase.Source: §VI · p. 6
- QAOA must run in no more than a minute to compete with state-of-the-art classical solvers on problems with fewer than 200 variables, and near-term hardware adds noise.The discussion identifies both runtime and hardware noise as challenges for improving QAOA performance.Source: §VI · p. 6
- Reusing similar-problem parameters can partially address the optimization challenge; a p = 1 example reduces amortized cost from approximately 16 minutes to approximately 1 second.The example uses BOBYQA or APOSMM over 1,000 dynamic-graph changes, with 10–30 local-refinement iterations at each change.Source: §VI · p. 6
- Modularity maximization requires all-to-all qubit connectivity, while many superconducting implementations provide only nearest-neighbor connectivity.The paper notes that a SWAP network can address the limitation with O(N) overhead; ion-trap architectures allow gates between any pair of qubits.Source: §VI · p. 6
- The authors say QAOA has the potential to outperform classical state-of-the-art solvers as hardware and parameter-optimization techniques improve.This is presented as a future possibility, not a demonstrated outcome.Source: §VI · p. 6