Quantum annealing initialization of the quantum approximate optimization algorithm

Stefan H. Sack; Maksym Serbyn

Source-linked AI summary

Quantum annealing initialization of the quantum approximate optimization algorithm

Stefan H. Sack, Maksym Serbyn

arXiv:2101.05742v3Jan 14, 2021quant-phcond-mat.dis-nncond-mat.stat-mechphysics.comp-ph

TL;DR

QAOA’s classical parameter optimization can become a bottleneck because random initialization often converges to sub-optimal local minima. The paper introduces TQA-based parameter initialization and finds comparable performance to exponentially many random starts, while linking the optimal time step to Trotter-error proliferation. These results support practical initialization procedures for QAOA on NISQ devices, although validation with noise and real hardware remains open.

Problem
QAOA’s external parameter optimization can become a bottleneck because higher-depth landscapes contain many sub-optimal local minima.
Method
The paper constructs a one-parameter family of QAOA initializations by Trotterizing quantum annealing, with the time step equivalently determining total evolution time at fixed depth.
Results
TQA initialization reaches solutions close to global optima over a broad time-step range, matching the best outcome of 2^p random initializations with one optimization run.
Takeaways & Limitations
The identified time-step heuristic and two-step NISQ procedure provide a practical route for initializing QAOA and connect intermediate-p QAOA with short-time quantum annealing.
Takeaways & Limitations
The reported performance is based on idealized simulations that neglect noise, gate errors, and other imperfections; real-device performance remains open.

Abstract

from arXiv · show

The quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm due to its modest circuit depth and promising benchmarks. However, an external parameter optimization required in QAOA could become a performance bottleneck. This motivates studies of the optimization landscape and search for heuristic ways of parameter initialization. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs, demonstrating that random initialization of the QAOA is prone to converging to local minima with sub-optimal performance. We introduce the initialization of QAOA parameters based on the Trotterized quantum annealing (TQA) protocol, parameterized by the Trotter time step. We find that the TQA initialization allows to circumvent the issue of false minima for a broad range of time steps, yielding the same performance as the best result out of an exponentially scaling number of random initializations. Moreover, we demonstrate that the optimal value of the time step coincides with the point of proliferation of Trotter errors in quantum annealing. Our results suggest practical ways of initializing QAOA protocols on near-term quantum devices and reveals new connections between QAOA and quantum annealing.

1 Introduction

QAOA’s increasing depth can make classical parameter optimization difficult because random starts often reach sub-optimal local minima. The paper proposes TQA-based initialization as a heuristic alternative tied to quantum annealing.

Motivation: Higher QAOA depth produces a more complex optimization landscape with many sub-optimal local minima, making convergence a potential performance bottleneck.Finding a nearly optimal minimum usually requires an exponentially scaling number of random initializations.
Related approaches: Existing initialization heuristics include recursively reusing parameters, transferring parameters between similar graphs, relaxed-problem states, and machine-learning predictions.
Proposed approach: The paper introduces a one-parameter family of Trotterized quantum annealing initializations controlled by the annealing time step or total evolution time.Trotterization of quantum-annealing evolution provides a particular QAOA parameter choice.
Main result: TQA initialization reaches performance comparable to the best result from an exponentially scaling number of random initializations.It converges to a nearly optimal minimum over a certain range of time steps.
Connection to quantum annealing: The study connects intermediate-p QAOA with short-time quantum annealing using coarse discretization compatible with realistic circuit depth.The optimal TQA time step is reported to correspond closely to the onset of proliferating Trotter errors.

2 Optimization landscape of QAOA

The paper studies QAOA optimization for MaxCut on random graph ensembles by examining local minima in approximation ratio and parameter space. Random starts commonly reach inferior minima, motivating annealing-inspired initialization.

2.1 QAOA for MaxCut problems: MaxCut seeks a vertex partition that maximizes edges crossing between the two groups and can be formulated as minimizing a classical spin Hamiltonian.The binary variables z_i = ±1 encode the partition assignment of each vertex.
2.1 QAOA for MaxCut problems: QAOA prepares a parameterized quantum state with 2p angles using alternating cost-Hamiltonian and mixing-Hamiltonian unitaries.The variational parameters are optimized by minimizing the measured expectation value of the cost Hamiltonian.
2.1 QAOA for MaxCut problems: The analysis benchmarks QAOA mainly on random 3-regular graph ensembles and also examines weighted 3-regular and Erdős-Rényi graphs.
2.2 Visualizing optimization landscape: For QAOA at p = 5, random initialization typically reaches local minima far from the best solution in both approximation ratio and parameter space.The analysis uses numerical optimization from random parameter starts and compares the resulting minima using two distance measures.
2.2 Visualizing optimization landscape: TQA initialization avoids the commonly reached inferior minima and converges near the global minimum in approximation ratio for the illustrated instance.Figure 2 averages results over 50 unweighted 3-regular graphs with N = 12 vertices.

3 Trotterized quantum annealing as initialization

Trotterized quantum annealing supplies QAOA parameters controlled by a time step, balancing improved annealing performance against discretization errors. Across the studied MaxCut instances, an optimal time step guides QAOA toward high-quality solutions and matches the scale where Trotter errors proliferate.

TQA construction: TQA discretizes annealing into p steps of size Δt = T/p, producing a depth-p QAOA circuit and a one-parameter initialization family.The resulting angles are controlled by the time step Δt at fixed circuit depth p.
Optimal TQA time: At fixed p, increasing total annealing time initially improves approximation ratio but eventually causes a sharp downturn from larger Trotter errors.For small Δt, Trotter errors scale as O(Δt^2), creating a trade-off between annealing efficiency and discretization accuracy.
Optimal TQA time: T* scales linearly with p, defining an approximately size-independent optimal time step δt for the studied graph families.For unweighted 3-regular graphs, the optimal value approaches δt ≈ 0.75, while the numerical value depends on the graph ensemble.
TQA initialization of QAOA: Using Δt = 0.75 avoids typical local minima and brings QAOA convergence close to the global minimum in approximation ratio.This initialization was demonstrated for QAOA and motivated systematic analysis over initialization times.
TQA initialization of QAOA: A broad interval Δt ∈ [0.16, 0.92] yields optimized-QAOA performance, while Δt = δt = 0.75 minimizes the initialization-to-converged-angle distance.The relevant characteristic times scale approximately linearly with circuit depth p, and the distance minimum nearly coincides with optimal TQA performance.
TQA initialization of QAOA: One TQA-initialized optimization run matches the best result from 2^p random initializations across the considered system sizes.The comparison includes QAOA depths comparable to problem size, while fixed-p performance decreases with N and constant performance requires p to grow at least as log N.

4 Summary and discussion

The paper establishes TQA-based QAOA initialization as a one-parameter strategy that reaches near-global minima with one optimization run, while outlining practical implementation and scope boundaries.

Summary and discussion: TQA initialization approaches the best outcome of 2^p random initializations with a single optimization run across a broad range of Δt.The initialization is parameterized by the Trotter time step.
Summary and discussion: The optimal Δt can be identified heuristically from the performance of the TQA protocol.This supplies the parameter-selection step for the proposed practical procedure.
Summary and discussion: The proposed two-step NISQ procedure first estimates the TQA time step and then runs QAOA optimization from the corresponding variational parameters.The TQA portion is described as executable on current NISQ devices.
Summary and discussion: The numerical evidence is restricted to idealized simulations without noise, gate errors, or other imperfections.Performance on real NISQ devices remains an open question.
Summary and discussion: The study covers MaxCut on three random graph ensembles, while behavior beyond MaxCut and at sizes N > 12 remains for future work.The authors connect broader applicability to concentration of the QAOA landscape.
Summary and discussion: The results reveal a connection between relatively shallow QAOA and quantum annealing through quantum-annealing-inspired initializations.The initializations lie in a basin of attraction of a high-quality QAOA minimum.
Summary and discussion: The mechanism by which subsequent QAOA optimization improves TQA initialization remains an outstanding challenge.The paper raises possible parallels with diabatic pumps, shortcuts to adiabaticity, and counterdiabatic driving.
Summary and discussion: The authors suggest that TQA initialization may support more time-efficient practical QAOA implementations on NISQ devices.They present this as a prospective consequence rather than an experimentally established result.

A Optimization landscape for different graph ensembles

The optimization landscape depends on graph symmetries and initialization intervals, with enlarged parameter ranges worsening local-optimum separation for weighted 3-regular graphs but not Erdős–Rényi graphs.

Optimization landscape for different graph ensembles: 3-regular unweighted graphs permit parameter-space reduction because integer Hamiltonian eigenvalues make γ_i periodic and β_i shifts symmetry-equivalent.These symmetries restrict the variational parameter domain.
Optimization landscape for different graph ensembles: Erdős–Rényi graphs with q = 0.5 share the symmetries of 3-regular unweighted graphs, despite connectivity increasing with system size.Their edge connectivity scales as qN.
Optimization landscape for different graph ensembles: For weighted 3-regular graphs, enlarging the initialization interval from k = 1 to k = 2 concentrates local optima farther from the global solution.The broader interval increases the spread in approximation-ratio distance Δr.
Optimization landscape for different graph ensembles: For Erdős–Rényi graphs, enlarging the interval to k = 2 leaves Δr effectively unchanged, supporting restriction to the k = 1 interval.The numerical observation confirms the symmetry-based expectation.

B Optimal time for TQA

The optimal TQA time step is linked to system-size scaling and Trotter-error behavior, but the proposed phenomenological scaling captures it only qualitatively.

Optimal time for TQA: The trace-distance bound implies δt ∝ 1/(||H_C||_F N), although the Frobenius norm grows exponentially with N.This bound therefore suggests very small time steps at large system sizes.
Optimal time for TQA: Trotterized evolution is expected to fail for local observables at a finite time step of order one.The proposed connection involves the convergence radius of the Baker–Campbell–Hausdorff expansion.
Optimal time for TQA: The study compares optimal TQA time-step dependence on system size with the phenomenological scaling s_N defined in Eq. (8).Figure 7 presents the comparison.
Optimal time for TQA: The optimal time step is largely system-size independent and scales qualitatively like s_N, with the largest value for weighted 3-regular graphs.For weighted 3-regular graphs, this is associated with the smallest expected classical-Hamiltonian norm.
Optimal time for TQA: The phenomenological scaling s_N fails quantitatively, leaving the transition from localization to quantum chaos insufficiently understood.The paper identifies a need for a better analytical description of the governing point.

C Patterns in optimized parameters

For finite p, optimized QAOA parameters remain close to their TQA initialization, with changes concentrated at the protocol’s beginning across the tested graph types.

C Patterns in optimized parameters: For finite p, converged QAOA parameters show only slight alterations from the TQA initialization.The comparison was performed at p = 10 and N = 10 over 50 random graphs of each tested type.
C Patterns in optimized parameters: The similarity between optimized and TQA parameters holds for unweighted 3-regular, weighted 3-regular, and Erdős-Rényi graphs.
C Patterns in optimized parameters: Small variation between optimal parameters across graph instances is consistent with concentration of the QAOA landscape at low p.
C Patterns in optimized parameters: QAOA optimization mainly modifies parameters at small i, while later parameters remain TQA-like.

D Random vs TQA initialization for other graph ensembles

TQA initialization matches the best random-initialization performance on weighted 3-regular graphs and surpasses it on Erdős-Rényi graphs.

D Random vs TQA initialization for other graph ensembles: TQA initialization yields the same performance as the best random initializations for weighted 3-regular graphs.
D Random vs TQA initialization for other graph ensembles: For Erdős-Rényi graphs, TQA initialization outperforms the best of 2^p random initializations.