PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameter Concentration in Quantum Approximate Optimization

V. Akshay, D. Rabinovich, E. Campos, J. Biamonte

arXiv:2103.11976v1quant-ph

TL;DR

Optimizing several QAOA parameters simultaneously becomes challenging beyond low depth. The paper analyzes large-system optimal-parameter behavior, reporting p=2 predictions that match numerical optima beyond n~10 and numerical evidence through p=5, with finite-fraction training implications when parameters have a limit.

Abstract

from arXiv · show

The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. In QAOA, a quantum circuit is trained -- by repeatedly adjusting circuit parameters -- to solve a problem. Several recent findings have reported parameter concentration effects in QAOA and their presence has become one of folklore: while empirically observed, the concentrations have not been defined and analytical approaches remain scarce, focusing on limiting system and not considering parameter scaling as system size increases. We found that optimal QAOA circuit parameters concentrate as an inverse polynomial in the problem size, providing an optimistic result for improving circuit training. Our results are analytically demonstrated for variational state preparations at $p=1,2$ (corresponding to 2 and 4 tunable parameters respectively). The technique is also applicable for higher depths and the concentration effect is cross verified numerically. Parameter concentrations allow for training on a fraction $w < n$ of qubits to assert that these parameters are nearly optimal on $n$ qubits. Clearly this effect has significant practical importance.

I. INTRODUCTION

QAOA’s classical optimization becomes challenging beyond low depth, while a general analytical approach to its behavior has remained unknown. This work defines parameter concentration, analyzes optimal-parameter scaling, and describes how concentration could support training on fewer qubits.

I. INTRODUCTION

  • Exact QAOA analyses remain scarce, and prior analysis of specific instances has not supplied a general analytical approach.The passage notes that higher depth may be needed to overcome known low-depth limitations.Source: §I · p. 1
  • Beyond low depth, simultaneously optimizing several QAOA parameters makes the classical optimization step challenging.Layer-wise training can reduce optimization time, but may be suboptimal in scenarios with abrupt training transitions.Source: §I · p. 1
  • The paper defines parameter concentration and introduces an analytical approach to optimal-parameter behavior for p=1 and p=2.It also reports applying the analysis to arbitrary p≥3 and numerically verifying scaling for p=5 up to n=17.Source: §I · p. 1
  • If parameters concentrate, training p levels on w<n qubits can yield parameters nearly optimal for n qubits.The authors identify this as a practical implication of concentration.Source: §I · p. 2

II. PARAMETER CONCENTRATION DEFINITION

The section describes optimal QAOA parameters as minimizers of the problem Hamiltonian’s expectation and introduces parameter concentration through closeness between optimal parameters at neighboring system sizes.

II. PARAMETER CONCENTRATION DEFINITION

  • For an n-qubit instance, the optimal parameter set minimizes the expectation of Hz in the variational QAOA state.The passage notes that the minimizing parameter set need not be unique.Source: §II · p. 2
  • The section names parameter concentration as a formal definition for the behavior of optimal parameters across system sizes.The supplied definition passage introduces the term but does not include its displayed criterion.Source: §II · p. 2
  • For n and n+1 qubits, at least one optimal parameter set is polynomially close to an optimal set at the other size.The passage states this as the interpretation of parameter concentration.Source: §II · p. 2

III. VARIATIONAL STATE PREPARATION

Variational state preparation seeks a QAOA candidate state with high overlap with a target computational-basis state. Its overlap objective is equivalent to minimizing a problem Hamiltonian.

III. VARIATIONAL STATE PREPARATION

  • Variational state preparation seeks a candidate state with high overlap with an n-qubit target state in the computational basis.The candidate is generated by a QAOA circuit.Source: §III · p. 2
  • The QAOA mixer is a standard one-body Hamiltonian built from Pauli Xi operators applied to the respective qubits.The parameters γk and βk lie in [0, 2π) and [0, π), respectively.Source: §III · p. 2
  • Maximizing squared overlap with the target is equivalent to minimizing Hz = 1 − |t⟩⟨t|.The overlap is |⟨t|ψ(γ, β)⟩|².Source: §III · p. 2

IV. RESULTS

The results derive optimal parameters from zero-gradient conditions and find concentration for p=1 and higher-depth cases, using large-system solutions and corrections.

IV. RESULTS

  • For p=1, zero-gradient conditions reduce the two parameter equations to a single expression in either γ or β.Because no general solution is available, the analysis uses approximate solutions at n≫1.Source: §IV · p. 2
  • For p≥2, zero-gradient equations may resist simplification, but solutions and next-order corrections can be found as n→∞.The passage reports that parameters concentrate in both the p=1 and higher-depth cases.Source: §IV · p. 2

A. Parameter concentration for p = 1

For p = 1, the authors derive optimal parameters from zero-gradient conditions and establish parameter concentration. Their analytical solutions approximate optimal parameters even for small n, with a symmetric solution also attaining the global maximum.

A. Parameter concentration for p = 1

  • The p = 1 ansatz state is used to calculate the amplitude and then the overlap that is maximized.The parameters are found by imposing zero gradients on that overlap.Source: A. Parameter concentration for p = 1 · p. 2
  • The optimality conditions relate the parameters by γ = π − 2β, while the equation for β is a degree-n polynomial without solutions in radicals.For n → ∞, the authors describe an asymptotic solution for β.Source: A. Parameter concentration for p = 1 · p. 2
  • The analytical solutions are reported to approximate optimal parameters even for small n.Figure 1 compares analytical and numerical optimal β and γ against qubit count n; its dots are numerical solutions to the maximization problem.Source: A. Parameter concentration for p = 1 · p. 3, Figure 1 · p. 3
  • A symmetric parameter solution delivers the same global maximum, while other large-n solutions of the condition yield only local maxima.The authors use the resulting behavior to establish parameter concentration for p = 1.Source: A. Parameter concentration for p = 1 · p. 3

B. Parameter concentration for p = 2

For p = 2, the authors obtain large-n parameter solutions from zero-gradient conditions and establish parameter concentration. Their analytical predictions match numerically recovered optima beyond n ∼ 10.

B. Parameter concentration for p = 2

  • The four zero-gradient equations for p = 2 have coupled variables, but the authors obtain solutions in the n → ∞ limit.They assume n ≫ 1 and corrections of next order in 1/n when searching for parameters.Source: B. Parameter concentration for p = 2 · p. 3
  • The authors report that β2 and γ2 behave as in the p = 1 case, and their analytical expressions also fall within the optimal approximation for n ∼ 1.The expressions are reported to match the analytical solution for large n.Source: B. Parameter concentration for p = 2 · p. 3
  • The analytical predictions match numerically recovered optimal parameters beyond n ∼ 10.The authors report that β1 and γ1 corrections are of next order in 1/n and do not calculate them explicitly.Source: B. Parameter concentration for p = 2 · p. 3
  • For large n, corrections to β1 and γ1 are third and second order, respectively; finite-region parameter fits use region-specific constants.The authors state that the finite-region functions approximate the parameters.Source: B. Parameter concentration for p = 2 · p. 3
  • The authors establish parameter concentration for p = 2 based on their results for parameter scaling and corrections.Source: B. Parameter concentration for p = 2 · p. 3

C. Parameter concentration for p ≥3

Numerical evidence through p=5 and 17 qubits supports the same large-n behavior for higher-depth optimal parameters. For p=5, fitting curves show parameter concentration.

C. Parameter concentration for p ≥3

V. DISCUSSION

The discussion distinguishes parameter concentration from prior instance-concentration results and relates optimal-parameter scaling to reduced training cost. It also notes a boundary on when partial training may recover optimal parameters for larger systems.

V. DISCUSSION

  • Prior instance-concentration results [14] concern vanishing objective variance, while MAX-CUT observations [23] narrowed across sizes without resolving optimal-parameter scaling.The discussion distinguishes these findings from its analysis of optimal-parameter behavior.Source: §V · p. 4
  • The analysis addresses one unique optimal set at each n; broader sensitivity of parameter distributions across instances is an expectation, not a demonstrated result.The authors say that this broader implication could reduce the cost of finding optimal parameters.Source: §V · p. 4
  • The observed concentration scaling implies optimal parameters have a limit as n →∞.This supports polynomially restricted training at a smaller system size, subject to further investigation.Source: §V · pp. 4–5
  • Training on a finite fraction w ≪ n and searching polynomially around parameters at w may recover optimal parameters for n.The authors state that further investigation is needed to fully exploit this approach.Source: §V · p. 5
  • For concentration with l ≤2, optimal parameters may not approach a limit, so partial training may not guarantee n-qubit optimality; such cases remain unobserved.Source: §V · p. 5
Loading 2103.11976v1…