PaperlayerView exact revision on arXiv

Source-linked AI summary

The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem

Mikhail Mints, Eric R. Anschuetz

arXiv:2609.10838v1quant-phcs.CC

TL;DR

Average-case hardness for Quantum Hypergraph Max-Cut is difficult to study because quantum algorithms produce state witnesses without a direct classical overlap landscape. The paper uses QOGP to prove hardness results for stable and local algorithms and derives constant-depth QAOA lower bounds. Its weak-hardness proof also faces a limitation from the extra degrees of freedom introduced by classical shadows.

  • Problem

    Quantum algorithms produce state witnesses rather than bit strings, leaving no direct classical overlap landscape for studying average-case approximation hardness.

    Source: §1 · p. 2

  • Method

    The paper applies QOGP by converting a quantum optimization problem to a classical one with a classical shadows estimator and using OGP structure to establish hardness for stable or local algorithms.

    Source: §2.4 · p. 11

  • Results

    QAOA of constant depth ℓ cannot be (γ, p_f)-optimal for Quantum Hypergraph Max-Cut on even k ≥ 14·2^10, for sufficiently small ℓ-dependent p_f ≥ 0.

    Source: §5.1 · p. 46

  • Takeaways & Limitations

    The QOGP framework extends hardness analysis for classical combinatorial optimization to limitations of quantum optimization algorithms under specific conditions.

    Source: §5.3 · p. 48

    In the weak-hardness result, classical shadows introduce extraneous degrees of freedom that make proving the nonexistence of forbidden configurations harder than in the classical case.

    Source: §5.2 · p. 48

Abstract

from arXiv · show

In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on $k$-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where $k$ is independent of $L$, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order $\infty$. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.

1 Introduction

Average-case complexity asks how well algorithms approximate typical random instances, while quantum ground-state problems lack the classical overlap landscape needed to apply OGP directly. The paper applies QOGP to Quantum Hypergraph Max-Cut, proving weak hardness for stable algorithms and stronger hardness for local algorithms, then deriving QAOA depth bounds.

1 Introduction

  • Average-case complexity asks how well efficient algorithms approximate typical instances drawn from a natural distribution, unlike worst-case hardness results.The introduction motivates this question by noting that practically and scientifically important problems are often modeled by random instances.Source: §1 · p. 2
  • Quantum algorithms produce state witnesses rather than bit strings, so their optimization landscapes lack a direct classical analogue for applying OGP.The paper uses the Quantum Overlap Gap Property framework to study average-case hardness for a k-local generalization of Quantum Max-Cut, a ground-state problem with little prior average-case analysis beyond heuristic physics arguments.Source: §1 · pp. 2–3, §1.1 · p. 3

1.1 Main Results

  • For every approximation ratio 0 < γ ≤ 1 and Lipschitz constant L > 0, some k makes γ-optimal Quantum Hypergraph Max-Cut solutions unattainable by L-stable algorithms.The selected k depends on L; the proof resamples a small fraction of hyperedges rather than constructing a full interpolation path.Source: §1.1 · p. 3
  • For every 0 < γ ≤ 1, some fixed k makes γ-optimal Quantum Hypergraph Max-Cut solutions unattainable by local algorithms, regardless of their Lipschitz constant.This stronger result uses a more restrictive stability notion defined with quantum Wasserstein distance of order ∞.Source: §1.1 · p. 3
  • The strong-hardness proof uses Ramsey theory to derive near-optimal solution configurations that form a forbidden configuration, with local stability providing more control over their structure.The proof adapts an m-OGP argument to quantum states.Source: §1.1 · p. 4
  • For sufficiently large k, QAOA with depth C log n, where C is bounded by a universal constant, fails to optimize Quantum Hypergraph Max-Cut.The strong hardness result also shows that this algorithm fails at any constant depth for some smaller k.Source: §1.1 · p. 4

2 Preliminaries

This section introduces the classical OGP and Quantum Hypergraph Max-Cut model, develops the maximal-energy, Wasserstein-stability, and classical-shadows tools used in the QOGP analysis, and provides notation for the problem, algorithms, and estimators.

2.1 The Overlap Gap Property

  • OGP requires near-optimal solutions to be either close or far apart, while ensemble OGP applies this gap across paired instances; clique interpolation illustrates the resulting obstruction to stable algorithms [Gam21; GS13].For clique sizes above the stated threshold, a stable algorithm would have to pass through a forbidden overlap range; multi-OGP extends the example to a broader regime.Source: §2.1 · pp. 4–5

2.2 Problem Setup

  • Quantum Hypergraph Max-Cut extends the Quantum Max-Cut Hamiltonian to sparse k-uniform hypergraphs, with the objective of finding a state that approximately maximizes its expected energy.For typical instances, the model uses randomly sampled interactions with Bernoulli inclusion and independent Rademacher signs.Source: §2.2 · p. 6

2.3 Maximal Energy Lower Bound

  • The maximal-energy lower bound is obtained by maximizing over computational-basis states, reducing that calculation to MAX-k-XORSAT with a penalty for each violated clause [AGL25].The proof also replaces the interaction coefficients by mean-zero Gaussian variables with matching variance [AGK25].Source: §2.3 · p. 7

2.4 The QOGP and Classical Shadows Estimators

  • Quantum Wasserstein distance motivates stability beyond trace distance: W2 defines stability, while the stronger W∞-based locality condition supports stronger hardness results [Ans26].The QOGP approach converts a quantum optimization problem to a classical one using a classical-shadows estimator and then applies an OGP obstruction [Ans26].Source: §2.4 · pp. 10–11
  • For local Hamiltonians, the Pauli shadows estimator is a valid efficient local shadows estimator, and the Quantum Hypergraph Max-Cut model exhibits self-averaging [HKP20].Its construction chooses an X, Y, or Z measurement basis uniformly at random; self-averaging helps establish the estimator’s constant estimation parameter.Source: §2.4 · pp. 12–13

2.5 Notation Reference

  • The notation reference defines symbols for the system, hypergraph instances and solutions, Hamiltonian, classical value, and limiting maximal energy.It also specifies notation for mixed states, the shadows channel, estimator error, and binary entropy.Source: §2.5 · p. 14
  • It also standardizes symbols for approximation and stability parameters, replica and estimator counts, norms, failure probabilities, and instance distributions.The reference includes Hamming distance, quantum Wasserstein norms, operator and trace norms, and distributions used for resampling and interpolation.Source: §2.5 · pp. 15–16

3 Weak Hardness for Stable Algorithms

This section establishes weak hardness for stable quantum algorithms, using stability to derive forbidden solution configurations whose nonexistence yields a contradiction. For any fixed Lipschitz constant and target optimality, sufficiently large uniformity rules out stable near-optimal algorithms under the theorem’s stated conditions.

3 Weak Hardness for Stable Algorithms

  • The weak-hardness locality k depends on the algorithm’s Lipschitz constant L, so this result does not establish one k that is hard for every stable algorithm.The section frames its proof around stable algorithms failing to find near-optimal solutions on average-case Quantum Hypergraph Max-Cut instances.Source: §3 · p. 16

3.1.1 Reduction to Weakly Stable Algorithms with Classical Outputs

  • The proof first derandomizes a stable near-optimal quantum algorithm, then uses Pauli shadows to produce classical outputs with weaker stability.The shadows-based output is described as close to 1/3-optimal with high probability and stable in expectation.Source: §3.1 · p. 16, §3.1.1 · p. 18

3.1.2 Constructing Collectively Stable Solution Configurations

  • Sampling independent outputs yields collectively stable solution configurations, while the proof uses only one interpolation step because a full path does not strengthen its result.The configurations obey the Lipschitz property on average; the single step resamples hyperedges adjacent to a small fraction F of qubits.Source: §3.1.2 · pp. 19, 21, 22

3.1.3 Taking Many Correlated Problem Instances

  • The argument extends these configurations to m correlated instances by resampling weights on hyperedges intersecting the first F fraction of qubits.The stated results provide bit-string configurations across the correlated instances, with conditions applying across replica indices.Source: §3.1.3 · pp. 22–23

3.1.4 Lower Bound on the Probability of Bounded Degree.

  • The correlated-instance analysis conditions on bounded maximum degree and lower-bounds its probability for instances where each vertex has expected degree p.The supplied passage states this probability-bound task but does not provide its resulting bound.Source: §3.1.3 · p. 25

3.2 Non-Existence of Forbidden Configurations

  • The QOGP argument seeks a contradiction by showing forbidden configurations are absent with high probability despite their existence under a stable algorithm.This is presented as the route to the weak-hardness result.Source: §3.2 · p. 26

3.2.3 Completing the Proof.

  • The proof’s completion sets δ = γ/2 and chooses R, m, F, and k to satisfy the stated conditions.The supplied passages do not include the conditions or the resulting parameter values.Source: §3.2.3 · p. 30
  • For any constants p > 0, L > 0, and 0 < γ ≤ 1, some sufficiently small F and sufficiently large k rule out the stated stable, γ-optimal algorithms for Quantum Hypergraph Max-Cut.The theorem also assumes f = o(n), sufficiently small p_st and p_f depending only on γ, and a lower bound on the dimension parameter 𝔡.Source: §3.2.3 · p. 31
  • When γ = 1, the proof gives p_st = p_f = 1 × 10^-6 and allows F = 3.97 × 10^-15.The preceding parameter choice takes R = 500 and k = 12/F.Source: §3.2.3 · p. 31

4 Strong Hardness for Local Algorithms

The section establishes strong average-case hardness for local quantum algorithms by reducing them to forbidden solution configurations along interpolation paths, then showing those configurations are unlikely to exist. This yields a fixed hypergraph size k independent of the algorithms’ Lipschitz constant, under the stronger W∞ locality condition.

4 Strong Hardness for Local Algorithms

  • The W∞ locality condition is stronger than W2 stability and supports a fixed-k hardness statement that the preceding result could not establish.The section says it cannot prove a sufficiently strong QOGP under the earlier condition.Source: §4 · p. 32

4.1.1 Reduction to Weakly Local Algorithms with Classical Outputs.

  • The proof reduces quantum algorithms to deterministic algorithms with classical outputs that satisfy a weaker locality condition.The W∞ distance allows stronger conclusions from weak locality than the W2-based stability condition.Source: §4.1 · p. 32, §4.1.1 · pp. 32–34

4.1.2 Solution Configurations over Interpolation Paths.

  • The interpolation distribution branches from one initial instance into T independent instances by resampling hyperedge weights across successive fractions of qubits.The marginal Ξ_Q^(q) describes a single interpolation step and is independent of the branch index t.Source: §4.1.2 · p. 35

4.2 Non-Existence of Forbidden Configurations

  • The argument proves that the set of forbidden configurations is empty with high probability, using a covariance bound that also applies to the same problem instance.This makes the hardness value of k independent of L.Source: §4.2 · p. 39

4.2.2 Completing the Proof.

  • For a fixed k chosen by the theorem, no W∞-local algorithm with any Lipschitz constant is γ-optimal for the specified Quantum Hypergraph Max-Cut model.The theorem fixes its parameters and requires locality along all interpolation steps.Source: §4 · p. 32, §4.2.2 · p. 43
  • The proof constructs the contradiction by combining the high-probability configuration conditions with a probability bound below 2^-n.The resulting contradiction rules out the local algorithm in the theorem’s setting.Source: §4.2.2 · pp. 43–44

5 Applications and Future Directions

This section applies the paper’s hardness results to quantum algorithms, then examines limits of the proof techniques and future directions. Its applications include a depth lower bound for QAOA, while its discussion identifies obstacles to extending strong hardness to all stable algorithms.

5.1 Hardness Results for Quantum Algorithms

  • Depth-ℓ QAOA is stable, and related lower bounds apply to quantum phase estimation, quantum annealing, and DQI under stated stability or decoder-locality conditions.The QAOA ansatz optimizes its parameters over [0, 2π].Source: §5.1 · pp. 44–45
  • There exists γ such that constant-depth QAOA cannot be (γ, p_f)-optimal on the stated even-k instances for sufficiently small ℓ-dependent p_f.The bound on p_f is independent of n; repetition can reduce error to o_n(1) when the original error is bounded away from 1.Source: §5.1 · p. 46

5.2 Limitations of Our Technique

  • The weak-hardness proof’s k depends on L because it uses resampling to separate near-optimal solutions; a strong claim would require this separation without resampling.The proof is not a “true” OGP and depends little on the optimization problem’s structure.Source: §5.2 · p. 46
  • Classical-shadows replicas create a proof obstacle: large R reduces estimator error, but collective stability poorly controls individual covariance terms unless R = 1.These extra degrees of freedom make it harder to rule out forbidden configurations than in the classical case.Source: §5.2 · p. 48

5.3 Conclusion and Future Work

  • The paper uses QOGP to establish conditional failures of stable and local algorithms for Quantum Hypergraph Max-Cut, extending classical optimization hardness tools to quantum optimization.It builds on prior QOGP work [Ans26] and classical combinatorial optimization hardness results [FGG20].Source: §5.3 · p. 48
  • Extending strong hardness to all stable algorithms remains open; the authors point to stronger QOGP formulations and possible study of Hamiltonian DQI.Hamiltonian DQI may be studied with these tools; the paper also calls for examining algorithms whose stability or locality is less evident.Source: §5.3 · pp. 48–49

6 AI Disclosure

The authors used Gemini for routine mathematical calculations and figure-generation code, but not in a way that materially affected the research methodology. They state that they verified the correctness and originality of all content, including references.

6 AI Disclosure

  • Google Gemini assisted with routine mathematical calculations and bounds in Section 3.2 and Appendix A.The authors say the tool did not materially affect the research methodology.Source: §6 · p. 49
  • Gemini was also used to generate LaTeX code for figures.Source: §6 · p. 49
  • The authors verified the correctness and originality of all content, including references.Source: §6 · p. 49

A.1 Problem Setup

The appendix considers a GHZ-projector extension of the EPR Hamiltonian to k-uniform hypergraphs and analyzes its energy using a Pauli-basis classical-shadows estimator. The estimator optimizes over assignments that account for the Hamiltonian terms' multiple bases.

A.1 Problem Setup

  • The appendix extends the EPR Hamiltonian to k-uniform hypergraphs using projectors onto k-qubit GHZ states.The EPR Hamiltonian uses projectors onto |Φ+⟩, unlike the k=2 Quantum Max-Cut Hamiltonian's projectors onto |Ψ−⟩.Source: §A.1 · p. 52
  • The Pauli-basis classical-shadows estimator seeks assignments b,s that maximize the energy.Source: §A.1 · p. 52
  • Because each Hamiltonian term spans more than one basis, the estimator cannot use one common basis assignment for every vertex.Source: §A.1 · p. 52
  • For the first term, a hyperedge contributes 1 when it avoids b[3], and otherwise contributes according to whether s is constant on its intersection with b[3].If s is constant there, the contribution is 2^|A∩b[3]|−1; otherwise it is 0.Source: §A.1 · p. 53

A.2.1 Upper Bound.

The upper-bound analysis uses tail and union bounds over state configurations, with a classical-state restriction providing a comparison bound. At large k, the quantum upper bound approaches that classical bound, with its extremal parameter near 0 or 1.

A.2.1 Upper Bound.

  • The proof replaces the Rademacher disorder with Gaussian variables using a universality result, since the distributions share their first two moments and the Rademacher disorder is bounded.Source: §A.2.1 · p. 54
  • A Gaussian tail bound followed by a union bound controls the probability across choices of z and w.The state classes are indexed by configurations with fixed |b[3]|=zn and |b[3]∩s[1]|=wn.Source: §A.2.1 · pp. 54–55
  • Restricting to z=1, which considers only classical states, yields the classical-state bound.Source: §A.2.1 · p. 55
  • For large k, the upper bound α_U approaches α_U,cl because the 16(1−z)^k term is subleading, and its maximum occurs as w approaches 0 or 1.Source: §A.2.1 · p. 56

A.2.2 Lower Bound.

The lower-bound analysis uses a second-moment approach and Gaussian tail bounds, focusing on classical states with a majority of 1s. Its overlap calculation uses binary entropy to approximate the number of configurations.

A.2.2 Lower Bound.

  • The lower-bound construction considers classical states with z=1 and w>1/2, then applies Gaussian tail bounds to pairs of states.The passage introduces a bivariate Gaussian tail bound for the pairwise estimate.Source: §A.2.2 · pp. 56–57
  • The lower bound is obtained through a second-moment argument and is stated while ignoring o_n(1) terms.Source: §A.2.2 · p. 57
  • In the overlap calculation, d/du Φ(u,w)=2H(w), so the numerator is approximated by e^(2nH(w)).H is the binary entropy function; the denominator is maximized near u=w.Source: §A.2.2 · pp. 57–58

A.3 Evidence Against the QOGP

For large k, the upper and lower bounds match near w=0 or 1, yielding low-entropy near-optimal solutions; this prevents the clustering phenomenon needed for the QOGP. The authors do not formally prove that the QOGP is absent.

A.3 Evidence Against the QOGP

  • For large k, matching bounds at w near 0 or 1 imply low-entropy near-optimal solutions, preventing the clustering phenomenon required for the QOGP.The authors do not formally prove that the QOGP does not exist, and say efficient average-case quantum algorithms may exist for large k.Source: §A.3 · p. 59

B Results from Ramsey Theory

The section presents Ramsey-theory results used to construct a forbidden configuration in the strong-hardness proof. Its improved corollary converts a condition on every m-vertex subgraph into a monochromatic m-clique guarantee.

B Results from Ramsey Theory

  • The Ramsey-theory results follow an argument similar to Gamarnik and Kızıldağ [GK21], simplify it, yield a better bound, and independently strengthen prior hardness results [GK21] [Gam+22] [Gam+23] [GJK23].Source: B Results from Ramsey Theory · p. 59
  • A Ramsey number is the smallest graph size that guarantees a monochromatic clique of a specified size in some color under every Q-coloring.The section also defines R_Q(m) for the case where all target clique sizes are m.Source: B Results from Ramsey Theory · pp. 59–60
  • If every m-vertex subgraph of G contains an edge, then a Q-coloring of its edges guarantees a monochromatic m-clique.Corollary B.4 states this result for a graph with T vertices.Source: B Results from Ramsey Theory · p. 60
  • The corollary treats the absence of an edge as an extra color, then applies a Ramsey result to force a clique in one of the actual edge colors.The assumption rules out a clique entirely in the extra color.Source: B Results from Ramsey Theory · p. 60
Loading 2609.10838v1…