\(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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) = 2^{\Omega(\mathrm{C}(f_n))}\)from \(\mathrm{D}^{\mathrm{prod}}(f) = 2^{\Omega(n)}\) against \(\mathrm{C}(f) = n\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = 2^{\Omega(n)}\) against \(\mathrm{psD}(S) = 2^{\Omega(n)}\)
-
\(\mathrm{D}^{\mathrm{prod}}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\mathrm{D}^{\mathrm{prod}}(f) = 2^{\Omega(n)}\) against \(\mathrm{psD}(S) = 2^{\Omega(n)}\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\mathrm{R}_{\varepsilon}(f) = 2^{\Omega(n)}\) against \(\mathrm{psD}(S) = 2^{\Omega(n)}\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = 2^{\Omega(n)}\) against \(\mathrm{psD}(S) = 2^{\Omega(n)}\)
-
\(\mathrm{R}_{0}(f_n) = \Omega\big(\mathrm{psD}(S)(f_n)\big)\)from \(\mathrm{R}_{0}(f) = 2^{\Omega(n)}\) against \(\mathrm{psD}(S) = 2^{\Omega(n)}\)
-
\(\mathrm{psD}(S)(f_n) = \Omega\big(\mathrm{DTsize}(f_n)\big)\)from \(\mathrm{psD}(S) = 2^{\Omega(n)}\) against \(\mathrm{DTsize}(f) = 2^{\Omega(n)}\)
Separations it witnesses
-
Exponential, with efficiently checkable solutions -- the strongest form of query-model quantum advantage for a search problem.