PaperlayerView exact revision on arXiv

Source-linked AI summary

Transferability of optimal QAOA parameters between random graphs

Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, Ilya Safro

arXiv:2106.07531v1quant-ph

TL;DR

Finding good QAOA parameters is challenging, and existing global-optimizer approaches can be inefficient on hard instances. This paper analyzes local graph substructures to predict transferability between optimized MaxCut parameters, reporting reuse from 6-node to 64-node random graphs with a small approximation-ratio loss. The authors present parameter reuse as a way to accelerate optimization for some QAOA instances.

  • Problem

    Finding good QAOA parameters is challenging, and global-optimizer exploration can be inefficient on hard instances with complex energy landscapes.

    Source: A. QAOA background · p. 2, §IV · p. 8

  • Method

    The paper predicts MaxCut parameter transferability from the transferability of relevant graph substructures and their edge-local QAOA contributions.

    Source: §I · p. 1, C. Tensor network QAOA simulator · p. 3

  • Results

    A 6-node random graph’s optimized parameters were reused for a 64-node random graph with a 1–2% approximation ratio loss in all three cases.

    Source: §IV · p. 9

  • Takeaways & Limitations

    The authors say parameter reuse could make finding optimized parameters quicker for some QAOA instances and may eliminate optimization in some cases.

    Source: §IV · p. 9

Abstract

from arXiv · show

The Quantum approximate optimization algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage through quantum-enhanced combinatorial optimization. In a typical QAOA setup, a set of quantum circuit parameters is optimized to prepare a quantum state used to find the optimal solution of a combinatorial optimization problem. Several empirical observations about optimal parameter concentration effects for special QAOA MaxCut problem instances have been made in recent literature, however, a rigorous study of the subject is still lacking. We show that convergence of the optimal QAOA parameters around specific values and, consequently, successful transferability of parameters between different QAOA instances can be explained and predicted based on the local properties of the graphs, specifically the types of subgraphs (lightcones) from which the graphs are composed. We apply this approach to random regular and general random graphs. For example, we demonstrate how optimized parameters calculated for a 6-node random graph can be successfully used without modification as nearly optimal parameters for a 64-node random graph, with less than 1% reduction in approximation ratio as a result. This work presents a pathway to identifying classes of combinatorial optimization instances for which such variational quantum algorithms as QAOA can be substantially accelerated.

I. INTRODUCTION

The paper studies whether optimized QAOA parameters can transfer between MaxCut graph instances, using subgraph properties to predict transferability. It reports transfer within odd- and even-regular graph classes and demonstrates reuse from small to larger general random graphs.

I. INTRODUCTION

  • The approach predicts parameter transfer by analyzing subgraph distributions and the transferability between relevant subgraph pairs.For random regular graphs, the paper says graph-level transferability is determined by transferability across all possible permutations of relevant subgraph pairs.Source: §I · p. 1
  • The analysis focuses on QAOA depth p = 1, while the authors describe extension to larger p as future work.The paper also outlines regular-graph analysis up to dmax = 8 and general random-graph analysis up to dmax = 6.Source: §I · pp. 1–2
  • A 6-node random graph’s optimized parameters transfer to a 64-node random graph with a 0.8% reduction in approximation ratio.The general-random-graph analysis is bounded by maximum node connectivity dmax = 6.Source: §I · p. 1
  • Transferability is good within odd-regular and even-regular random-graph classes, but poor between the two classes in either direction.The paper relates these patterns to transferability between the graphs’ relevant subgraphs.Source: §I · p. 1

II. QAOA

QAOA combines parameterized quantum evolution with a classical outer-loop optimizer to approximately solve binary optimization problems. This paper focuses on depth p = 1, motivated by practical circuit-depth constraints.

II. QAOA

  • QAOA is a hybrid quantum-classical algorithm that combines parameterized quantum evolution with a classical outer-loop optimizer for binary optimization.Source: §II · p. 2
  • QAOA has p layers of alternating operator pairs, and each added layer can improve solution quality under perfect noiseless circuit execution.Source: §II · p. 2
  • The paper studies p = 1 because noise and limited coherence constrain practical implementations to p ≤ 3 on current processors without quantum error correction.Source: §II · p. 2

A. QAOA background

QAOA encodes a combinatorial objective in a quantum operator and prepares a parameterized state through alternating operators. A classical outer loop uses measurements to select the schedule, while finding good parameters can be challenging.

A. QAOA background

  • QAOA encodes the binary-string objective C(z) as an operator C diagonal in the computational basis.Source: A. QAOA background · p. 2
  • The QAOA ansatz alternates phase and mixing operators on an easy-to-prepare initial state, with the number of operator pairs defining depth p.Source: A. QAOA background · p. 2
  • Repeated state preparation and measurement supply output for a classical outer-loop algorithm to select the schedule β⃗, γ⃗.Source: A. QAOA background · p. 2
  • Finding good QAOA parameters is challenging, and prior acceleration approaches include warm- and multi-start optimization, problem decomposition, instance-structure analysis, and parameter learning.The passage notes complex energy landscapes for hard instances as one challenge for global-optimizer exploration.Source: A. QAOA background · p. 2

B. MaxCut

The paper studies parameter transfer for QAOA on MaxCut, which seeks a vertex partition maximizing edges across the two sets. Prior work gives a p = 1 approximation-ratio guarantee for 3-regular graphs.

B. MaxCut

  • MaxCut partitions an unweighted undirected graph’s vertices into two complementary sets to maximize the number of edges between them.Source: B. MaxCut · p. 2
  • In the QAOA encoding, the input graph has N vertices and m edges, and the goal is to find a bit string z that maximizes the encoded objective.Source: B. MaxCut · p. 2
  • For a 3-regular graph, QAOA with p = 1 has a previously shown approximation ratio of at least 0.6924 [4].Source: B. MaxCut · p. 2

C. Tensor network QAOA simulator

The simulator evaluates QAOA energy through tensor-network contractions, using local edge contributions that simplify to subgraphs. Its reported cost depends on contraction width, with tractable energy simulation across graph sizes for the studied depths.

C. Tensor network QAOA simulator

  • The MaxCut expected cost is a sum of |E| edge contributions, each represented by its own tensor network.The total calculation evaluates one network for each edge jk ∈ E.Source: C. Tensor network QAOA simulator · p. 3
  • For a local observable, most circuit gates cancel, leaving an edge contribution computed on a subgraph extending p − 1 edges from its endpoints.This lightcone simplification reduces simulation cost, especially for low-connectivity, shallow circuits.Source: C. Tensor network QAOA simulator · pp. 2–3
  • Contraction width w determines the largest tensor, whose size is 2^w and whose storage and contraction drive simulation cost.QTensor contracts one index at a time using bucket elimination.Source: C. Tensor network QAOA simulator · p. 3
  • At p = 1, maximum contraction width is w = 5 for any N and slowly decreases as more tree-like subgraphs occur.Fig. 2 plots contraction width against graph size for random d-regular graphs.Source: Figure 2 · p. 3, C. Tensor network QAOA simulator · p. 3
  • For p < 5, tensor-network simulation computes energy for any graph size with linear time scaling.The contraction cost is not monotonic in graph size for random 3-regular graphs; increasing tree-like structure can simplify the tensor networks.Source: C. Tensor network QAOA simulator · p. 3
  • Parameter optimization uses automatic differentiation for gradients and RMSProp to update the circuit parameters.Automatic differentiation propagates gradients through the calculation graph using the chain rule.Source: C. Tensor network QAOA simulator · p. 3

D. Classical MaxCut solver

The solver obtains optimal MaxCut solutions for evaluating approximation ratios. This reference optimization is difficult because MaxCut is NP-hard and classical solvers require exponential time to converge.

D. Classical MaxCut solver

  • Approximation-ratio calculations require the optimal solution, which the experiments obtain with Gurobi run to convergence.The solver uses default configuration parameters.Source: D. Classical MaxCut solver · pp. 3–4
  • MaxCut is NP-hard, and classical solvers require exponential time to converge to the optimal solution.The experiments use Gurobi with its default configuration and run it until convergence.Source: D. Classical MaxCut solver · p. 4

III. PARAMETER TRANSFERABILITY

The paper studies when optimized QAOA parameters from one graph can be reused for another. It frames transferability through graph subgraphs, building on prior parameter-concentration observations for special cases.

III. PARAMETER TRANSFERABILITY

  • Classical tensor-network simulation can efficiently evaluate QAOA energy during iterative optimization, while final sampling is described as impossible to simulate efficiently for sufficiently large instances on classical hardware.The energy calculation uses simplifications based on the reverse causal cone.Source: §III · p. 4
  • Successful parameter transferability means using parameters optimized on a smaller donor graph to prepare a state for the same problem on a larger acceptor graph.Parameters may be reused unchanged or used as a warm start; either option can reduce the cost of parameter optimization.Source: §III · p. 4
  • The central question is when parameters optimized for one graph also maximize the QAOA objective on another graph.Earlier concentration observations focused mainly on random 3-regular graphs [17]–[19].Source: §III · p. 4
  • Because the objective is determined by graph subgraphs, the analysis studies parameter transferability between the corresponding subgraphs.The expectation value can be expressed through contributing subgraphs of the instance graph.Source: §III · p. 4

A. Subgraph transferability analysis

The analysis connects graph-level parameter transfer to transfer among the local subgraphs contributing to QAOA cost. For random regular graphs, the observed subgraph patterns motivate parity-based transfer conjectures and sufficient conditions for general donor–acceptor pairs.

A. Subgraph transferability analysis

  • The analysis decomposes bounded-degree graphs into contributing subgraphs for a given QAOA depth, unless the subgraphs cover the whole graph.The objective is expressed as a sum over contributions from those subgraphs.Source: A. Subgraph transferability analysis · p. 4
  • The authors conjecture transfer between any two random d-regular graphs, between degrees of matching parity, and not between degrees of opposite parity.They state that rigorous study is needed to confirm these conjectures.Source: A. Subgraph transferability analysis · p. 4
  • For p = 1, maxima for 3- and 5-regular subgraphs lie near one another, while only half of 4-regular maxima match those of odd-regular subgraphs.The 4-regular subgraphs have closely positioned maxima among themselves.Source: A. Subgraph transferability analysis · p. 4, Figure 3 · p. 5
  • Confirmation of the regular-graph conjectures, generalization to p > 1, and parameter rescaling for improved cross-degree transfer are outside this paper’s scope.The authors defer these questions and methods to a separate paper.Source: A. Subgraph transferability analysis · p. 5
  • Sufficient transferability conditions require mutual transfer among donor subgraphs, mutual transfer among acceptor subgraphs, and transfer from every donor subgraph to every acceptor subgraph.These conditions are presented for general donor–acceptor graph pairs.Source: A. Subgraph transferability analysis · p. 5
  • The map compares directional transfer coefficients for all 35 subgraphs of d-regular graphs with d ≤ 8.Each donor subgraph is optimized with 200 steps and 20 random initial points; the coefficient averages acceptor energy under those donor parameters relative to the optimized acceptor energy.Source: A. Subgraph transferability analysis · pp. 5–6
  • Transferability is directional: good transfer from one subgraph to another does not guarantee transfer in reverse.The energy maxima of one landscape may all coincide with maxima of another while the reverse alignment is incomplete.Source: A. Subgraph transferability analysis · p. 6
  • The transferability map shows good transfer within odd-regular and even-regular classes, but poor transfer between the classes in both directions.The 3-regular subgraph block has high mutual transferability, consistent with transfer between arbitrary 3-regular graphs [17].Source: A. Subgraph transferability analysis · pp. 6, 8

B. General random graph transferability

For general random graphs with node degrees d ≤ 6, subgraphs are more diverse because the two nodes on a central edge can have different degrees. A map of subgraph transferability identifies degree-parity patterns and some mixed-degree pairs whose optimized parameters transfer well.

B. General random graph transferability

  • General-graph subgraphs are more diverse because the two nodes connected by the central edge can have different numbers of connected edges.The transferability map covers 50 subgraphs with node degrees d ≤ 6.Source: B. General random graph transferability · p. 8
  • Subgraphs whose central-node degrees are all odd or all even generally transfer to one another, extending the odd- and even-regular graph result.Some mixed-degree pairs also transfer well, including subgraph #20 (3, 4) → subgraph #34 (4, 5).Source: B. General random graph transferability · p. 8
  • The subgraph transferability map can identify smaller donor subgraphs with nearly optimal parameters for the original graph and estimate transfer likelihood between graphs.Source: B. General random graph transferability · p. 8

C. Parameter transferability examples

For three 6-node donor and 64-node acceptor graph pairs, transferred optimized parameters yield approximation ratios close to direct acceptor optimization. The donor and acceptor parameters were numerically optimized with 20 restarts and 200 iterations each.

C. Parameter transferability examples

IV. CONCLUSIONS AND OUTLOOK

The paper uses graph substructure to motivate reusing QAOA parameters optimized on smaller graphs. It reports successful transfer to larger random graphs, while identifying depth and graph-class boundaries.

IV. CONCLUSIONS AND OUTLOOK

  • The approach optimizes parameters for smaller graphs and reuses them, drawing on small-subgraph energy landscapes with well-defined extrema and possible similarity across structures.QAOA cost is calculated by summing subgraph contributions, whose subgraph size depends on circuit depth p.Source: §IV · p. 8
  • Good parameter transfer was observed among even-regular and odd-regular subgraphs, but transfer between even- and odd-regular graph classes was poor in both directions.The cross-class result is based on poor transfer between the corresponding graph subgraphs.Source: §IV · pp. 8–9
  • A 1–2% approximation ratio loss was observed in all three transfers from 6-node to 64-node random graphs.The transferred parameters were calculated for the smaller graphs and used for the larger ones.Source: §IV · p. 9
  • The study evaluates transferability only at p = 1; larger depths are a preliminary prospect requiring advanced subgraph exploration algorithms.The paper also identifies transfer between different-sized even-to-even and odd-to-odd degree graphs as future work.Source: §IV · p. 9
  • QTensor enabled energy calculations for most instances with p ≤ 3, d ≤ 6, and about 1,000 nodes, usually within seconds.For this work, 64-node graphs with d ≤ 5 at p = 1 took a fraction of a second per execution on a personal computer.Source: §IV · p. 9
  • For some QAOA instances, parameter reuse may make optimization quick and efficient or remove the optimization step altogether.The paper notes potential relevance to relatively slow neutral-atom and trapped-ion devices, which could then be used only to sample the output state.Source: §IV · p. 9
Loading 2106.07531v1…