we-solve (beta)

CS-116 · computer science · mathematics · Quantum computing

Analytical Performance Theory for QAOA and RQAOA

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
Develop an analytical account of the performance and limitations of QAOA and RQAOA in the resource-limited NISQ regime.

Formulation references: [S1], [S2].

Short English statement

Develop an analytical account of the performance and limitations of QAOA and RQAOA in the resource-limited NISQ regime.

Sources

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

CS-116-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-116

The theorem determines the limiting optimal QAOA energy for the Gaussian zero-field SK model when n tends to infinity before depth p. This supplies an analytical performance result for that model and order of limits, but not a general account of QAOA/RQAOA in the resource-limited NISQ regime. This entry records partial support; complete coverage of the question is not established by this catalogue.

Analytical Performance Theory for QAOA and RQAOA

OpenAI's claim

OpenAI presents a mathematical result relevant to this question in the selected manuscript. QAOA is claimed to approach the SK ground-energy density when system size goes to infinity before depth, using deterministic disorder-independent angles but no effective depth bound.

Mathematical statement of the claimed result

Result 1.
For independent standard Gaussian $J_{ij}$, set $C_{n,J}=n^{-1/2}\sum_{i<j}J_{ij}Z_iZ_j$ and $B_n=\sum_iX_i$, with Pauli operators. A depth-$p$ QAOA state is \[ \psi_{n,p,J}=e^{-i\beta_pB_n}e^{-i\gamma_pC_{n,J}}\cdots e^{-i\beta_1B_n}e^{-i\gamma_1C_{n,J}}|+\rangle^{\otimes n}. \] For deterministic parameters, put $v_p(\gamma,\beta)=\lim_n n^{-1}\mathbb E\langle\psi,C_{n,J}\psi\rangle$ and $Q_p=\sup_{\gamma,\beta\in\mathbb R^p}v_p$. The claim is \[ \lim_{p\to\infty}Q_p=P_*,\qquad P_*=\lim_n n^{-1}\mathbb E\max_{\sigma\in\{\pm1\}^n} n^{-1/2}\sum_{i<j}J_{ij}\sigma_i\sigma_j. \] For each accuracy $\varepsilon>0$, one finite depth and parameter vector, independent of both instance and size, achieves $v_p\ge P_*-\varepsilon$. The size limit is taken first.

Outline of the argument

Fixed circuit words have an exact limiting tree calculus. A nearly optimal bounded classical formula is compiled with seeded controls, then longitudinal seeds are removed; the ordinary cost-and-mixer word retains the limiting expected energy in the thermodynamic-first order.

Formal verification

For family 281, the selected value identities express the SK ground energy through an admissible Parisi minimizer and diffusion, without asserting QAOA circuit convergence. A distinct full-support statement covers integrable zero-temperature minimizers. The listed Comparator files are SKFullSupport.lean, SKValue.lean. The inventory does not supply a named declaration for these Comparator entries. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

Go to contribution →