Quantum certificate complexity
Quantum analogue of certificate complexity; the square root of RC.
Definition
$\mathrm{QC}_x(f)$ is the minimum number of quantum queries needed to verify that the input is $x$ "as far as $f$ is concerned"; $\mathrm{QC}(f)=\max_x \mathrm{QC}_x(f)$.
Basic facts
- $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)}) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08].
- $\mathrm{QC}(f) \le \mathrm{Q}(f)$.
- Operational certification for $\mathrm{Q}$, quantum distinguishing complexity, the quantum adversary bound, all four quantum sabotage variants, bounded approximate degree and block-multilinear bounded approximate degree equals $\Theta(\mathrm{QC})$ [KLLPV26, Theorems 4 and 6].
- For every quantum sabotage variant, $\mathrm{QC}=O(\mathrm{QS})$ even on partial functions; Index shows the inequality need not be tight [CMP24, KLLPV26].
Equivalent / near-equivalent measures
- \(\mathrm{RC}(f)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ Aaronson08
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{QC}(f)\). “\(\mathrm{QC}(f)\) in terms of it” is the pair with \(\mathrm{QC}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 6 above are this entry’s hand-picked neighbours; the other 87 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(\sqrt n)\) | Quantum certificate complexity is $\Theta(\sqrt{\mathrm{RC}})$; for OR this is the Grover-verification bound. Aaronson08 |
| AND total | \(\Theta(\sqrt n)\) | Aaronson08 |
| PARITY total | \(\Theta(\sqrt n)\) | $\mathrm{QC}=\Theta(\sqrt{\mathrm{RC}})$ and $\mathrm{RC}=\lceil n/2\rceil$. Verification is quadratically cheaper than computation even here. Aaronson08 |
| MAJORITY total | \(\Theta(\sqrt n)\) | $\mathrm{QC}=\Theta(\sqrt{\mathrm{RC}})$. Verifying a majority is quadratically cheaper than computing it. Aaronson08 |
| Threshold total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(\max\{k,\,n-k+1\}) = \Theta(n)$ here. Verifying a threshold is quadratically cheaper than computing it, uniformly in $k$. Aaronson08 |
| Symmetric functions (general) total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. Aaronson08 |
| EXACT-HALF total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. So verifying is quadratically cheaper even though computing costs the full $\Theta(n)$ quantumly. Aaronson08 |
| ODD-MAX-BIT total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. Aaronson08 |
| ADDRESS / multiplexer total | \(\Theta(\sqrt k)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(k)$ here. Aaronson08 |
| Binary tree navigation total | \(\Theta(\sqrt k)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(k)$ here. Verifying a claimed walk is quadratically cheaper than following it. Aaronson08 |
| TRIBES total | \(\Theta(\sqrt{n/\log n})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n/\log n)$ here. Strictly below $\mathrm{Q} = \Theta(\sqrt n)$ by a $\sqrt{\log n}$ factor. Aaronson08 |
| AND-OR tree (depth 2) total | \(\Theta(\sqrt n) = \Theta(N^{1/4})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = n$ here. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(N^{1/4})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(\sqrt N)$ here. |
| Recursive MAJORITY-of-3 total | \(\Theta(2^{d/2}) = \Theta(N^{0.3155})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = 2^d$ here. |
| Kushilevitz's function (iterated) total | \(\Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = N$ here. |
| Rubinstein's function total | \(\Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here. |
| Ambainis-Sun function total | \(\Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(N)$ here. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n) = \Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} = \Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(\Omega(118.3^{\,d})\) putative | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} \ge \mathrm{bs} \ge 14011^{\,d}$. |
| Pointer functions total | \(\widetilde\Theta(n^{1/4})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| Cheat-sheet functions total | \(\widetilde\Theta(n^{1/4})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. Quantum certificate complexity is a fourth power below $\mathrm{Q}$ here. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$ with $\mathrm{fbs}=\widetilde\Omega(n)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(\sqrt n)\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(n^{1/4})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. |
| Ambainis' exact-quantum function total | \(\Theta(3^{d/2})\) | Squeeze: $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$. This is $\Theta(n^{1/2})$, well below $\mathrm{Q}=\Theta(n^{0.6845})$. |
| FORRELATION partial | \(\Theta(1)\) | An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$; and $\mathrm{QC} \ge 1$ for a non-constant $f$. This is what forces $\mathrm{fbs} = O(1)$ above, via $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$. |
| k-FORRELATION partial | \(O(k)\) | An algorithm computing $f$ also verifies its input, so $\mathrm{QC} \le \mathrm{Q} = \lceil k/2\rceil$; and $\mathrm{QC} \ge 1$. Independent of $n$. |
| Simon's problem partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$, and independently $\mathrm{QC} \le \mathrm{Q}$. Against $\mathrm{C} = \Theta(2^{n/2})$ this is an exponential quantum-certificate advantage: a constant-size quantum certificate replaces a difference-covering set. |
| Deutsch-Jozsa partial | \(\Theta(1)\) | An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$. Compare $\mathrm{C} = N/2+1$: this is the extreme case of quantum certificates beating classical ones. |
| Bernstein-Vazirani partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$, and independently $\mathrm{QC} \le \mathrm{Q} = 1$. Against $\mathrm{C} = \mathrm{C}_{\min} = n$: a constant-size quantum certificate replaces a whole basis of $\mathbb{F}_2^n$. |
| Marked bit partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{FC}}) = \Theta(1)$ [Aaronson08]. Constant quantum certificate complexity against $\mathrm{Q} = \Theta(\sqrt n)$ -- the same phenomenon Aaronson exhibits on \(\mathrm{COL}_n\), here at quadratic strength and with a two-line proof. Aaronson08 |
| Dense marked bit partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{FC}}) = \Theta(1)$ [Aaronson08]; also $\mathrm{QC} \le \mathrm{Q} = \Theta(1)$. Aaronson08 |
| Gap-Majority partial | \(\Theta(\sqrt{\min(n, 1/\delta)})\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$, with $\mathrm{fbs} = \Theta(\min(n,1/\delta))$; and independently $\mathrm{QC} \le \mathrm{Q}$. Aaronson08 |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}})$. Aaronson08 |
| Parity-labelled FIND-1 partial | \(\Theta(1)\) | At most $\mathrm{Q} = \Theta(1)$, and at least $1$. |
| Approximate index partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$: a constant-size quantum certificate, matching the constant-size classical one. Aaronson08 |
| Collision problem partial | \(\Theta(1)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = \Theta(1)$; a colliding pair is a two-query certificate and the promise makes it checkable. Aaronson08 |
| Element distinctness total | \(\Theta(\sqrt n)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{RC}})$ and $\mathrm{RC} = \Theta(n)$. Directly: at an all-distinct $x$ every adversary $y$ with $\mathrm{ED}(y) = 0$ differs from $x$ in one symbol, so distinguishing $x$ from all of them is unstructured search, $\mathrm{RC}_x = \Theta(n)$ and $\mathrm{QC}_x = \Theta(\sqrt n)$. Note $\mathrm{QC} = \Theta(\sqrt n)$ sits below $\mathrm{Q} = \Theta(n^{2/3})$: verifying is easier than deciding. Aaronson08 |
| Ambainis-Belovs function partial | \(O(\sqrt n)\) | $\mathrm{QC} = \Theta(\sqrt{\mathrm{fbs}}) = O(\sqrt n)$. The other ceiling, $\mathrm{QC} \le \mathrm{Q}$, is useless here because only a lower bound on $\mathrm{Q}$ is known. Aaronson06 |
| Surjectivity total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$ (\(\mathrm{QC}(f)\) vs \(\mathrm{FC}(f)\)), and $\mathrm{FC} = \Theta(n)$ here. |
| $k$-distinctness total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = \Theta(n)$ here. Note this is below $\mathrm{Q}$, as it must be -- quantum certificate complexity is not a lower bound on $\mathrm{Q}$ in any useful sense here. |
| Triangle finding total | \(\Theta(m)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = \Theta(m^2)$ here. |
| Ordered search partial | \(\Theta(1)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = 2$. |
| Inner product mod 2 total | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)}) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ [Aaronson08], and $\mathrm{fbs} = n$ here. So quantum certificate complexity is a full square root below $\mathrm{Q} = \Theta(n)$: verification is cheap even though computation is not. Aaronson08 |
| Minsky-Papert one-in-a-box total | \(\Theta(m) = \Theta(N^{1/3})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m^2)$ here. Curiously this coincides with $\mathrm{sdeg}$ and with $\mathrm{C}_{\min}$, all three at $N^{1/3}$. Aaronson08 |
| Sink of a tournament total | \(\Theta(\sqrt m) = \Theta(N^{1/4})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m)$ here. It coincides with $\lambda$ and with the lower end of the $\mathrm{Q}$ range. Aaronson08 |
| Scorpion graphs total | \(\Theta(\sqrt m) = \Theta(N^{1/4})\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m)$ here. So a quantum verifier checks the scorpion property with a quadratically shorter certificate than the classical $\mathrm{C} = \Theta(m)$. Aaronson08 |
| Graph connectivity total | \(\Theta(m) = \Theta(\sqrt N)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ [Aaronson08], and $\mathrm{fbs} = \Theta(m^2)$ here. The $1$-side already has a classical certificate of size $m-1$ (a spanning tree); what the quantum verifier compresses is the $\Theta(m^2)$-edge cut on the $0$-side. Aaronson08 |
| AND of complemented EXACT-ONE functions total | \(\Theta(m)\) | QC=Θ(√fbs). Aaronson08 KLLPV26 |