PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity Barriers to State Preparation in Quantum Approximate Optimization

Stuart Hadfield

arXiv:2609.31520v1quant-phcs.CC

TL;DR

Ordinary approximation ratios for MaxCut can conceal near-zero gain over a random cut, leaving gain-based worst-case barriers less represented in quantum optimization assessment. The paper applies MaxCut-Gain hardness to standard and compressed encodings and examines how relaxation tightness and energy ratios relate to operational gain recovery. The resulting barriers distinguish those measures and motivate reporting multiple performance dimensions.

  • Problem

    For MaxCut, a near-unity ordinary approximation ratio can coexist with near-zero gain over a random cut, while alternative approximation metrics have not been widely considered in quantum optimization.

    Source: §I · p. 1

  • Method

    The paper applies classical MaxCut-Gain hardness to state preparation and combines it with QRAO’s local-decoding relation between encoded energy gain and decoded mean gain.

    Source: §I · pp. 1–2

  • Results

    The preparation barrier persists under d = 2 and 3 QRAO compression, while a hard family has relative relaxation excess Θ(1/n) and a maximally mixed state with energy ratio 1−Θ(1/n) but zero encoded and decoded gain.

    Source: §I · p. 2

  • Takeaways & Limitations

    Decoded gain, ordinary approximation ratio, target-reaching probability, and end-to-end implementation costs should be assessed together in quantum optimization benchmarks.

    Source: §I · p. 3

    The nearly tight-relaxation construction is asymptotic and worst-case, not a claim about generic instances; its fixed padding factor may inherit large constants from the classical gap.

    Source: B. Nearly tight compressed relaxations · p. 10

Abstract

from arXiv · show

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $\Theta(1/n)$, while the maximally mixed state has energy approximation ratio $1-\Theta(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

I. INTRODUCTION

The paper uses MaxCut gain above a random assignment to study worst-case barriers to quantum optimization, extending the standard-encoding barrier to QRAO. It distinguishes operational gain recovery from relaxation tightness and ordinary energy approximation, and calls for broader benchmarking.

I. INTRODUCTION

  • For quantum approaches to MaxCut, the study assesses achievable performance gain above random assignments, noting that classical approximation theory in terms of gain differs from ordinary approximation-ratio theory.Source: §I · p. 1

A. MaxCut and its encodings

  • The standard encoding uses one qubit per vertex, while QRAO packs d = 2 or 3 variables per qubit and uses local rounding to decode its state.For arbitrary input states, including entangled states, the decoder transfers encoded energy gain to decoded mean gain by an exact factor; a classically normalized target yields at least 1/d^2 of that target in decoded mean gain.Source: §I · pp. 1–2, A. MaxCut and its encodings · pp. 3–4

I. INTRODUCTION

  • Recovering any fixed positive fraction of optimal classical gain on every input with inverse-polynomial success under a uniformly efficient standard-encoding procedure would imply NP ⊆ BQP; the barrier also extends to d = 2 and 3 QRAO encodings.For compressed encodings, the stated energy range is C⋆ ≤ Eρ ≤ λmax(Hd), with encoded energy gain measured against the input graph’s classical optimum.Source: §I · pp. 1–2
  • Uniform polynomial-time state-preparation barriers cover quantum circuits, variational methods, annealing, open-system and measurement-based approaches, and hybrid methods across hardware regimes.The scope requires end-to-end uniform realizability to required accuracy by polynomial-size adaptive circuits.Source: §I · p. 2
  • A hard family has relative relaxation excess Θ(1/n), yet the maximally mixed state has energy within relative Θ(1/n) of the quantum optimum while its encoded and decoded gains are zero.Thus neither a nearly tight relaxation nor near-unity energy approximation certifies the encoded gain required by the theorem.Source: §I · p. 2
  • The paper recommends assessing decoded gain, ordinary approximation ratio, target-reaching probability, and end-to-end costs together rather than treating them as interchangeable scores.Relevant costs include training, readout and sampling, precision, fault-tolerance overhead, and total implementation cost.Source: §I · p. 3, §II · p. 3

B. Gain versus ordinary approximation ratio

The section distinguishes decoded gain from ordinary approximation ratio: gain measures improvement over a random cut, while an ordinary ratio includes that baseline. For compressed encodings, an encoded gain target transfers to decoded gain with a factor of 1/d^2.

B. Gain versus ordinary approximation ratio

  • An encoded target genc(ρ)/g⋆ ≥ τ guarantees decoded gain ratio Rdec(ρ) ≥ τ/d^2, but this is not the same as requiring the relaxed-optimum gain ratio Rq(ρ) ≥ τ.The latter is at least as strong because the relaxed quantum optimum gain is at least the classical optimum gain.Source: B. Gain versus ordinary approximation… · pp. 4–5
  • A decoded gain ratio of at least α also bounds the ordinary expected approximation ratio, which includes the random-cut baseline.The section contrasts this with the converse: an ordinary approximation guarantee alone can certify no positive decoded gain in some regimes.Source: B. Gain versus ordinary approximation… · p. 5
  • The Goemans–Williamson guarantee alone gives no positive decoded gain bound when c ≤ 1/(2aGW) ≈ 0.569108, although on promises c ≥ 0.6 the bound certifies Rdec(ρ) ≥ 0.2714.A stronger classical gain analysis recovers Ω(1/log(1/ε)) of available gain when c = 1/2 + ε.Source: B. Gain versus ordinary approximation… · p. 5
  • Gain complements ordinary approximation ratio because near-unity approximation can coexist with near-zero improvement over a random cut.The section also notes that MaxCut has no ordinary-ratio PTAS unless P = NP, and bounded-error randomized or quantum PTASs would imply NP ⊆ BPP or NP ⊆ BQP, respectively.Source: B. Gain versus ordinary approximation… · p. 5

III. STATE PREPARATION BARRIER FROM GAIN

The section turns the classical MaxCut-Gain hardness gap into an operational barrier for uniform quantum and hybrid state-preparation procedures. The result covers compressed QRAO settings and remains applicable even when the target energy is between the classical and relaxed optima.

III. STATE PREPARATION BARRIER FROM GAIN

  • The operational model counts preprocessing, control, state generation, and repetitions, and permits adaptive quantum circuits with polynomial-time classical control.Examples include QAOA with efficient parameter selection and finite-time quantum annealing; solution advice and conditioning on exponentially rare events are excluded.Source: §III · pp. 5–6
  • For each fixed d and target fraction τ, a uniform operational preparation reaching the stated encoded-gain target with inverse-polynomial success would imply NP ⊆ BQP.The hard instances may depend on (d, τ), and the result imposes no ansatz, optimizer, locality, or control-count restriction.Source: §III · p. 6
  • The barrier also holds for the two-to-one and three-to-one QRAO encodings, including targets T satisfying C⋆ ≤ T ≤ λmax(Hd).It remains true for restricted families of fully occupied packings in which every qubit contains exactly d variables.Source: §III · p. 6
  • Polynomial repetition of successful preparations and decoded measurements separates the NP-hard YES and NO cases, yielding a bounded-error quantum decision procedure.The reduction needs neither a success flag nor knowledge of C⋆, and uses a rational threshold inside the promise gap.Source: §III · p. 6
  • On graphs with C⋆/W ≥ 1/2 + ε, worst-case gain Ω(εW/log(1/ε)) is the optimal scale up to constants for uniform polynomial-cost methods, assuming NP̸ ⊆ BQP.Classical algorithms achieve gain Ω(εW/log(1/ε)) on this promise.Source: §III · p. 6

A. Tail probability barriers

The tail-probability barrier rules out inverse-polynomial probability of obtaining a cut above a fixed fraction of the optimal gain on every valid input, without requiring a mean-value guarantee. Its scope is worst-case rather than random-instance performance.

A. Tail probability barriers

  • Known concentration controls apply only in structured regimes, such as certain shallow-circuit observables and dense-QAOA evolutions under explicit depth and norm conditions.They do not apply to arbitrary states in the theorem, and concentration across random instances does not determine shots needed on one input.Source: A. Tail probability barriers · p. 7
  • An inverse-polynomial probability of returning a cut with gain at least αg⋆ on every valid MaxCut input would imply NP ⊆ BQP.The result requires no mean-value guarantee.Source: A. Tail probability barriers · p. 7
  • The barrier excludes inverse-polynomial upper-tail mass, not exponentially small mass, and its worst-case result does not rule out good performance over a specified random-instance ensemble.A random-instance barrier would require distributional hardness or a worst-to-average-case reduction for that ensemble.Source: A. Tail probability barriers · p. 7

IV. ALGORITHMIC SCOPE

In the standard uncompressed encoding, the objective Hamiltonian’s optimum equals the classical MaxCut optimum, and its eigenstates include efficiently preparable product states. Computational-basis readout makes encoded and decoded mean gains coincide.

IV. ALGORITHMIC SCOPE

  • For d = 1, H1 is diagonal with λmax(H1) = C⋆, and its eigenstates correspond to efficiently preparable product states |z⟩.The section identifies the target as a fraction τ of available classical gain, with τ = 1 restricted to optimal cuts.Source: §IV · p. 7
  • Under computational-basis readout for d = 1, encoded and decoded mean gains coincide: gdec(ρ) = genc(ρ).The following section specializes the discussion to compressed encodings.Source: §IV · p. 7

A. Conditional algorithmic coverage

The barrier applies to quantum and hybrid methods when their complete end-to-end implementations meet the paper’s uniform-efficiency requirements. Structured-family guarantees and supplied advice remain distinct boundaries on that claim.

A. Conditional algorithmic coverage

  • The theorem covers QAOA and hybrid guarantees only when the full procedure is uniformly efficient and meets Definition 1; for QAOA it constrains finding and implementing parameters, not their existence.The assessment includes finite-time implementation details such as precision, success probability, and repetitions.Source: A. Conditional algorithmic coverage · pp. 7–8
  • A qualifying supplied warm-start cut already meets the target, so the theorem does not exclude supplied advice; computing seeds and updates from the instance counts toward end-to-end cost.The same advice boundary applies to a cut’s QRAC product embedding for d ∈ {2, 3}.Source: A. Conditional algorithmic coverage · pp. 7–8
  • At D = 100, depth-one QAOA recovers about 6.08% of available gain for K100,100 and at least that fraction for every unweighted triangle-free 100-regular graph.The same graph class also has classical polynomial-time gain guarantees.Source: A. Conditional algorithmic coverage · p. 8
  • Positive gain bounds on structured graph families are consistent with the all-instance barrier, which does not extend unchanged to fixed-degree promise classes.The cited depth-one and depth-two results concern structured graph families rather than all-instance guarantees.Source: A. Conditional algorithmic coverage · p. 8
  • A uniform polynomial-cost DQI procedure meeting the target on every MaxCut instance would satisfy the theorem’s hypothesis, while cited DQI guarantees exploit promise structure.In the MaxCut regime with a nontrivial asymptotic DQI guarantee, the instances are exactly solvable in classical polynomial time.Source: A. Conditional algorithmic coverage · p. 8
  • Annealing, adiabatic, open-system, and measurement-based methods are covered only when their complete finite-time implementations admit the required uniform polynomial-size adaptive-circuit realization.Whether this condition holds is model dependent, and duration, controls, precision, success probability, resets, and repetitions count.Source: A. Conditional algorithmic coverage · p. 8

B. Ordinary approximation ratio can be misleading

The ordinary approximation ratio can conceal how much a cut improves on random guessing. Examples show that the same mean value and ratio can correspond to very different gains.

B. Ordinary approximation ratio can be misleading

  • For K100, the random baseline has ordinary approximation ratio 0.99 and recovers zero gain.Here W = 4950, C⋆ = 2500, and the random baseline W/2 = 2475.Source: B. Ordinary approximation ratio can be… · p. 8
  • For K50,50, a randomized output has mean cut value 2475 and ratio 0.99, yet its gain differs from that of the K100 random baseline.The output chooses the bipartition with probability 0.99 and the all-equal cut otherwise; the comparison holds mean value and ordinary ratio fixed while changing the baseline.Source: B. Ordinary approximation ratio can be… · p. 8
  • The same mean value and ordinary ratio can represent either zero improvement over random assignment or recovery of nearly all available gain.The section contrasts the K100 and K50,50 examples.Source: B. Ordinary approximation ratio can be… · p. 8
  • For graphs with maximum degree at most D, a deterministic polynomial-time algorithm finds a matching of weight at least W/(2D −1).The matching yields an expected cut satisfying the bound developed in the cited passage.Source: B. Ordinary approximation ratio can be… · p. 8

V. COMPRESSED ENCODINGS AND CLASSICAL GAIN TARGETS

QRAO compression preserves a route from encoded energy gain to decoded classical gain, while the relaxed quantum optimum may exceed the classical threshold. The conditional bounds clarify why high ordinary ratios alone do not certify gain recovery.

V. COMPRESSED ENCODINGS AND CLASSICAL GAIN TARGETS

  • For d ∈ {2, 3}, every classical assignment has a QRAC product-state embedding with the same objective value, although the quantum optimum can be larger than the maximum cut value.Thus reaching the classical threshold does not require maximizing the compressed Hamiltonian.Source: §V · p. 8
  • For PCE, a uniform polynomial-cost pipeline returning a cut with a fixed positive fraction of optimal classical gain on every input would imply NP ⊆ BQP.The encoded-state transfer result requires a size-independent transfer factor and a loss consistent with the final decoder; end-to-end accounting includes training, estimation, decoding, and repetitions.Source: §V · p. 9

A. Compressed calibration and gain accounting

  • In the two-qubit d = 3 example, the product codewords have energy 3 and the singlet has energy 6, while their rounded expected cuts are 5/3 and 2.The encoded-energy increase of 3 raises expected decoded cut by 1/3, matching the 1/d^2 transfer; entanglement can help on some instances but is unnecessary to reach the classical threshold.Source: A. Compressed calibration and gain… · p. 9
  • At the classical-threshold target Eρ ≥ C⋆, the decoded gain ratio is at least 1/d^2.More generally, an encoded-energy condition with target fraction τ yields decoded gain ratio at least τ/d^2.Source: A. Compressed calibration and gain… · p. 9
  • For d = 2 and d = 3, the uniform ordinary-ratio bounds at the threshold are respectively R ≥ 5/8 and R ≥ 5/9.The instance-dependent bound approaches one when c = C⋆/W approaches 1/2.Source: A. Compressed calibration and gain… · p. 9
  • Figure 2 contrasts conditional ordinary-ratio bounds with the random-cut baseline and Goemans-Williamson guarantee; near c = 1/2, random guessing has ratio near one despite zero gain.The solid curves are consequences of the threshold target, not guarantees achieved by known efficient algorithms.Source: Figure 2 · p. 9, A. Compressed calibration and gain… · p. 9

B. Nearly tight compressed relaxations

The preparation barrier persists even when compressed relaxations are nearly tight and the maximally mixed state is close to optimal in energy. The construction is asymptotic and requires growing graph degree for a vanishing energy deficit.

B. Nearly tight compressed relaxations

  • A fixed relative target measured against the relaxed quantum optimum also falls under the preparation barrier when it implies the encoded-energy target with τ = r.The passage states this equivalence for fixed 0 < r ≤ 1.Source: B. Nearly tight compressed relaxations · p. 10
  • For fixed d ∈ {2, 3}, hard families have relative quantum relaxation excess Θ(1/n), while the maximally mixed state’s energy is within a relative Θ(1/n) of the quantum optimum.That state nevertheless has zero encoded energy gain and zero decoded mean gain.Source: B. Nearly tight compressed relaxations · p. 10
  • The hard-family barrier holds for any uniform operational preparation procedure meeting the target on every input with inverse-polynomial success, which would imply NP ⊆ BQP.The construction packs exactly dn variables into n qubits.Source: B. Nearly tight compressed relaxations · p. 10
  • The padding construction preserves an inverse-polynomial YES–NO separation, and a mean-to-tail argument supplies inverse-polynomial probability of crossing a rational threshold.Repeating the procedure polynomially many times yields a BQP decision procedure for the NP-hard gap.Source: B. Nearly tight compressed relaxations · p. 10
  • The construction’s relative deficits are Θ(1/n), with lower bounds from the packed clique Hamiltonian and n = (1 + 2M)m for fixed M.The cited proof establishes matching asymptotic upper and lower bounds for the relevant deficits.Source: B. Nearly tight compressed relaxations · p. 10
  • The near-tight construction is asymptotic worst case, not generic, and its fixed padding factor may have constants too large for a near-term benchmark.At d = 1, the same padding preserves hardness and the mixed-state deficit, but the relaxation is exactly tight.Source: B. Nearly tight compressed relaxations · p. 10
  • A vanishing energy-approximation deficit of the stated form requires maximum degree D ≥ n/(2A), although this does not imply every hard approximation problem requires large degree.The result says linear maximum-degree growth is necessary for this near-tight phenomenon.Source: B. Nearly tight compressed relaxations · p. 10

VI. OUTLOOK

The paper argues that preparation barriers cover standard and compressed encodings, but apply to a specific implementation only when its full preparation-and-decoding pipeline meets Definition 1. It recommends broader benchmarking and identifies open problems in bounded-degree classes, higher-weight PCEs, and other constraint satisfaction problems.

VI. OUTLOOK

  • Theorem 1 and Proposition 1 cover standard and compressed encodings, but a QRAO implementation is covered only when its complete preparation-and-decoding pipeline satisfies Definition 1.The barriers apply to near-term devices and future fault-tolerant hardware.Source: §VI · p. 10
  • Fair benchmarking should report gain and classical baselines alongside ordinary approximation ratios, using common instances and matched end-to-end budgets.The listed budgets include preparation, optimization, measurement settings and shots, restarts, readout, precision, decoding or repair, and classical postprocessing [1] [68].Source: §VI · pp. 10–11
  • Extending these themes to other optimization problems requires a sampleable baseline, classical hardness for recovering a fixed fraction of advantage, and an efficient encoding and readout map.Boolean constraint satisfaction is a natural generalization, but each problem needs its own construction.Source: §VI · p. 11
  • Open problems include establishing decoded-gain barriers for bounded-degree graphs, finding a suitable decoder for weight-k > 1 PCEs, and extending the construction to other constraint satisfaction problems.Cubic-graph APX-completeness alone does not provide the gain gap used here.Source: §VI · p. 11

Appendix A: Local decoding and error tolerance

Appendix A gives the local decoding identity and error-tolerance conditions, while Appendix B constructs a gain bound for bounded-degree graphs. Together, they specify how the decoder relates measured energy to decoded gain and how the bounded-degree construction is obtained.

Appendix A: Local decoding and error tolerance

  • For every edge, the local product measurement satisfies E[z_i z_j] = Tr(ρP_iP_j)/d, proving Eq. (6) even for entangled states.The POVM outcomes have probabilities Tr(ρM_z), with positive semidefinite elements that sum to I.Source: Appendix A · p. 13
  • Preparation and readout errors are budgeted as ζ and ξ normalized by W; sufficiently small fixed implementation errors preserve Theorem 1, whereas Appendix C requires inverse-polynomial error.A trace-distance error T changes energy by at most dWT.Source: Appendix A · p. 13
  • With known uniform polynomial runtime and success bounds, truncating at 2t(N)/s(N) loses at most s(N)/2 success probability, including accounting for postselection, resets, and failed trials.The extension applies when runtime is averaged over internal classical randomness and measurement outcomes.Source: Appendix A · p. 13

Appendix B: Bounded-degree gain construction

  • For maximum degree D, greedy selection gives a matching of weight at least W/(2D −1); conditional expectation then derandomizes the construction and proves Eq. (19).Matched pairs receive opposite independent fair orientations, while unmatched vertices are assigned independently.Source: Appendix B · p. 14

Appendix C: Vanishing relative gap with hard gain recovery

Appendix C pads a source graph with a disjoint clique and packs copies to make a hard family. Its estimates show that both the relaxation excess and the maximally mixed-state deficit vanish as Θ(1/n), while a gain-recovery gap remains usable with polynomially many repetitions.

Appendix C: Vanishing relative gap with hard gain recovery

  • Padding adds a disjoint clique on k = 2Mm vertices with total weight mW; packing d copies gives n = (1 + 2M)m and W_tot = d(m + 1)W.The construction fixes d and τ, then chooses fixed ε and integer M to control the padding contribution.Source: Appendix C · p. 14
  • Both relative deficits are Θ(1/n): the relaxed quantum optimum above the classical optimum and the maximally mixed-state energy below the quantum optimum.The upper bound constant 2d²(1 + 2M) suffices for both estimates.Source: Appendix C · p. 14
  • The successful-YES and NO decoded-gain bounds are separated by a threshold that yields success probability Ω(1/m) per successful preparation, so polynomially many repetitions suffice.This also holds when preparation succeeds only with inverse-polynomial probability; sufficiently small normalized error budgets of at most c0/m preserve the gap.Source: Appendix C · p. 14
  • The padding clique contributes d²uk/4 = Θ(W) above the mixed-state baseline, establishing the second lower bound alongside the source contribution.Source and padding act on disjoint qubits, and the total classical and quantum optima are Θ(mW).Source: Appendix C · p. 14

Related papers

Loading 2609.31520v1…