Q The Query Complexity Zoo
\(\mathrm{CG}^{*}(f)\)

Quantum certificate game complexity

Certificate game with shared entanglement.

Definition

As \(\mathrm{CG}(f)\) but the players share an entangled state.

Basic facts

  • Surprisingly $\mathrm{CG}^*$ is not below $\mathrm{Q}$: $\mathrm{CG}^*(\mathrm{OR}_n)=\Theta(n)$ while $\mathrm{Q}(\mathrm{OR}_n)=\Theta(\sqrt n)$.
  • All certificate-game models except the private-coin one collapse to the classical adversary bound for high-sensitivity functions.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{CG}^{*}(f)\). “\(\mathrm{CG}^{*}(f)\) in terms of it” is the pair with \(\mathrm{CG}^{*}(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.

Other measure \(\mathrm{CG}^{*}(f)\) in terms of it It in terms of \(\mathrm{CG}^{*}(f)\)
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) total1,1 partial1,1 derived open pair → total2,? partial∞ derived open pair →
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) total1,1 partial1,1 derived open pair → total1,? partial1,? open pair →
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity total1,? partial1,? derived open pair → total1,? partial1,? derived open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total1,1 partial1,1 derived open pair → total1,? partial1,? derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total2,2 partial2,2 open pair → total2,? partial∞ derived open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
AND total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
PARITY total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
MAJORITY total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Threshold total \(\Theta(\max\{k,\;n-k+1\})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Symmetric functions (general) total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. In particular $\mathrm{CG}^{*}$ is $\Theta(n)$ for every symmetric function, however small $\mathrm{Q}$ gets. CGLMSG23
EXACT-HALF total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
ODD-MAX-BIT total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. Note $\mathrm{CG}^{*} = \Theta(n)$ against $\mathrm{Q} = \Theta(\sqrt n)$: another instance of the entangled certificate game not being bounded by quantum query complexity. CGLMSG23
ADDRESS / multiplexer total \(\Theta(k+1)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Binary tree navigation total \(\Theta(k)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
TRIBES total \(\Theta(n/\log n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
AND-OR tree (depth 2) total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Kushilevitz's function (iterated) total \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Rubinstein's function total \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Ambainis-Sun function total \(\Theta(N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Meiburg's tournament-subcube function total \(\Theta(14011^{\,d})\) putative All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$, so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim. CGLMSG23
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$: same collapse as the $\mathrm{CG}^{\mathrm{ns}}$ line -- entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$ here. ABIKPS17
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})=\widetilde\Theta(\sqrt n)$. ABIKPS17
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\widetilde\Omega(n)$. ABIKPS17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
Gilmer-Saks-Srinivasan functions total \(\Theta(n)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(n)$. ABIKPS17
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) Same collapse: entangled certificate games are $\Theta(\mathrm{CA})=\Theta(\mathrm{fbs})$. ABIKPS17
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: the non-signaling, entangled and public-coin certificate games all collapse to $\Theta(\mathrm{CA})$.
FORRELATION partial \(\widetilde O(\sqrt n)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants; see \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\). CGLMSG23
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23
Simon's problem partial \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$.
Deutsch-Jozsa partial \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}}$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. CGLMSG23
Bernstein-Vazirani partial \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) All three of $\mathrm{CG}^{\mathrm{ns}}, \mathrm{CG}^{*}, \mathrm{CG}^{\mathrm{pub}}$ collapse to $\Theta(\mathrm{CA})$ [CGLMSG23]; only the private-coin game escapes. CGLMSG23
Gap-Majority at constant gap partial \(\Theta(1)\) All of $\mathrm{CG}^{\mathrm{ns}},\mathrm{CG}^{*},\mathrm{CG}^{\mathrm{pub}}$ collapse to $\Theta(\mathrm{CA})$. CGLMSG23
Approximate index partial \(O(\sqrt{k\log k})\) At most $\mathrm{CG}^{\mathrm{pub}}$; all three non-private variants are $\Theta(\mathrm{CA})$. CGLMSG23
Collision problem partial \(\Theta(1)\) Between $\mathrm{CG}^{\mathrm{ns}} \ge 1$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. CGLMSG23
Element distinctness total \(\Theta(n)\) Between $\mathrm{CG}^{\mathrm{ns}}$ and $\mathrm{CG}^{\mathrm{pub}}$, both $\Theta(\mathrm{CA}) = \Theta(n)$.
Ambainis-Belovs function partial \(O(n)\) Equal to $\mathrm{CG}^{\mathrm{pub}}$ up to constants. CGLMSG23
$k$-distinctness total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Triangle finding total \(\Theta(m^2) = \Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Ordered search partial \(O(\log n)\) The three non-private variants all collapse to $\Theta(\mathrm{CA})$ by LP duality, which is a partial-function statement [CGLMSG23]; see \(\mathrm{CA}(f)\). CGLMSG23
Inner product mod 2 total \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
Minsky-Papert one-in-a-box total \(\Theta(m^2) = \Theta(N^{2/3})\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)). CGLMSG23
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)). CGLMSG23
Scorpion graphs total \(\Theta(m)\) Entanglement buys nothing beyond the non-signaling value: $\mathrm{CG}^{*} = \Theta(\mathrm{CA}) = \Theta(m)$. CGLMSG23
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Entanglement buys nothing beyond the non-signaling value: $\mathrm{CG}^{*} = \Theta(\mathrm{CA}) = \Theta(m^2)$. Note the contrast with \(\mathrm{Q}_{\varepsilon}(f)\), where quantum queries do buy the factor $\sqrt m$. CGLMSG23