Q The Query Complexity Zoo
\(S_{\mathrm{YZ}}\)

Yamakawa-Zhandry problem

Verifiable exponential quantum advantage for an NP search problem relative to a random oracle.

relation relational arity: random oracle

Description

Find a codeword of a fixed error-correcting code all of whose symbols land in a random oracle's preimage set. Quantum: $\mathrm{poly}$ queries; classical: exponentially many, and solutions are efficiently verifiable.

Measure values

MeasureValueNotes
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\mathrm{poly}(n)\) YamakawaZhandry22
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(2^{\Omega(n)}\) YamakawaZhandry22
\(\mathrm{D}(f)\) Deterministic query complexity \(2^{\Omega(n)}\) At least $\mathrm{R}$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(2^{\Omega(n)}\) At least $\mathrm{R}$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(2^{\Omega(n)}\) $\bar{\mathrm{R}} = \Theta(\mathrm{R})$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(2^{\Omega(n)}\) At least $\mathrm{R}$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(2^{\Omega(n)}\) At least $\mathrm{D}$.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Omega(n)}\) A tree of depth $d$ has more than $d$ leaves, so $\mathrm{DTsize} > \mathrm{D} = 2^{\Omega(n)}$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(2^{\Omega(n)}\) At least $\mathrm{R} = 2^{\Omega(n)}$, since $\mathrm{R} \le \mathrm{psD}$. Pseudo-determinism costs nothing extra here in any interesting sense -- the point is the contrast with $\mathrm{Q} = \mathrm{poly}(n)$, which makes this the strongest form of quantum advantage on record for a search problem: exponential, verifiable, and against the pseudo-deterministic classical model.
\(\mathrm{C}(f)\) Certificate complexity \(n\) putative A solution is a codeword $y \in \mathcal{C} \subseteq \Sigma^n$ with $H(i, y_i) = 1$ for all $i$; exhibiting those $n$ oracle bits certifies it, and fewer will not, since any unfixed coordinate could fail. So $\mathrm{C} = n$ against $\mathrm{D} = 2^{\Omega(n)}$ -- the problem is in the query analogue of $\mathrm{NP}$, which is exactly what makes the quantum advantage verifiable.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n\) putative Every input has the same $n$-bit certificate shape, so the minimum over inputs equals the maximum.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(n\) The search problem is total -- every oracle admits a codeword all of whose symbols are preimages -- so there is no "no" side and $\mathrm{C}^1 = \mathrm{C} = n$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\mathrm{poly}(n)\) putative Verifiability makes the quantum advantage zero-error: run the $\mathrm{poly}(n)$-query algorithm, spend $n$ more queries checking $H(i,y_i)=1$ for all $i$, and repeat on failure. So $\mathrm{Q}_0 = O(\mathrm{Q} + n) = \mathrm{poly}(n)$ against $\mathrm{R}_0 = 2^{\Omega(n)}$. Contrast \(\mathrm{SEARCH}_n\), where $\mathrm{Q}_0 = n$ because the all-zero input has no witness to verify; here totality is on the quantum side too.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\mathrm{poly}(n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \mathrm{poly}(n)$; the interest is entirely that this is exponentially below $\mathrm{R}$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\mathrm{poly}(n)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both $\mathrm{poly}(n)$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\mathrm{poly}(n)\) $\gamma_2 = \Theta(\mathrm{Q}) = \mathrm{poly}(n)$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\mathrm{poly}(n)\) A lower bound on $\mathrm{Q} = \mathrm{poly}(n)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(2^{\Omega(n)}\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = 2^{\Omega(n)}$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(2^{\Omega(n)}\) The classical lower bound is proved against a uniformly random oracle, which is a product distribution, so the hardness needs no correlated hard distribution at all: $\mathrm{D}^{\mathrm{prod}} = 2^{\Omega(n)}$. YamakawaZhandry22
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(2^{\Omega(n)}\) At least $\mathrm{R} = 2^{\Omega(n)}$; noise cannot help.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\mathrm{poly}(n)\) At most $\mathrm{Q}\log\mathrm{Q} = \mathrm{poly}(n)$ by generic robustification, at least $\mathrm{Q}$. So even a noisy quantum oracle keeps the exponential advantage.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(2^{\Omega(n)}\) Squeezed from below by $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0$, and both $\mathrm{R}$ and $\mathrm{R}_0$ are already $2^{\Omega(n)}$.
\(\mathrm{rank}(f)\) Decision tree rank \(\Omega(n)\) A tree of rank $r$ has a leaf at depth $\le r$, so $\mathrm{rank} \ge \mathrm{C}_{\min} = n$. Nothing better follows from the recorded values, since only a lower bound on $\mathrm{D}$ is known.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\mathrm{poly}(n)\) At most $\mathrm{Q} = \mathrm{poly}(n)$: postselection can only help, so the exponential quantum advantage survives in this model too.

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 7 in total.

Separations it witnesses