OpenAI’s nearly quartic randomized–quantum family
Settles the optimal total-function $\mathrm{R}$-versus-$\mathrm{Q}$ exponent at $4$.
total composed arity: A winner-column construction on $m$ columns, with address and certificate arrays; $k\ge2$ is fixed and $m$ ranges over sufficiently large powers of four.
Description
Each column contains an $m$-bit string and an address-indexed certificate array. A unique winner has an all-one string and a valid certificate pointing to a zero in every other column. Addresses are computed by instances of the Bansal–Sinha partial-function separation. A quantum tournament finds a short list containing the winner; a randomized algorithm must find an erased zero or the correctly addressed filled cell [OpenAI26QuarticRQ, Sections 2–4].
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\widetilde O(\sqrt m)\) | For each fixed k, Q≤C_k sqrt(m)(log m)^{b_k}. Constants and the log exponent may depend on k. OpenAI26QuarticRQ |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Omega(m^{2-1/k}/\log^2m)\) | Theorem 1.1, for each fixed k≥2. OpenAI26QuarticRQ |
Separations it witnesses
-
For every $\alpha<4$, there is a fixed $k$ for which $\mathrm{R}(F_{k,m})/(1+\mathrm{Q}(F_{k,m}))^\alpha\to\infty$.
Cited as a witness by
-
\(\forall\alpha<4\ \exists k:\ \frac{\mathrm{R}(F_{k,m})}{(1+\mathrm{Q}(F_{k,m}))^\alpha}\longrightarrow\infty\)
Notes
The fixed-k separation exponent is $4-2/k$ up to polylogarithmic factors. Varying k proves that the optimal universal power is 4; the paper does not state a fixed-k $\widetilde\Omega(\mathrm{Q}^4)$ lower bound. The general upper bound is $\mathrm{R}\le\mathrm{D}=O(\mathrm{Q}^4)$ [ABKRT21]. Will Cook provides a great exposition and a Lean proof, with instructions for reproducing the formal checks.