Q The Query Complexity Zoo
\(\mathrm{NQ}(f)\)

Nondeterministic quantum query complexity

Quantum algorithm with nonzero acceptance probability exactly on 1-inputs.

Definition

The algorithm must accept with some positive probability iff $f(x)=1$. de Wolf showed $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ where $\mathrm{ndeg}$ is the nondeterministic degree.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{NQ}(f)\). “\(\mathrm{NQ}(f)\) in terms of it” is the pair with \(\mathrm{NQ}(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{NQ}(f)\) in terms of it It in terms of \(\mathrm{NQ}(f)\)
\(\mathrm{ndeg}(f)\) Nondeterministic degree total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{C}^1(f)\) 1-certificate complexity total1,1 partial1,1 derived open pair → total2,? partial2,? derived open pair →
\(\mathrm{rdeg}(f)\) Rational degree total1,1 partial1,1 derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity total1,1 partial1,1 derived open pair → total∞ partial∞ derived open pair →

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

Known values

FunctionValueNotes
OR total \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg}(\mathrm{OR})=1$. deWolf03
AND total \(\lceil n/2 \rceil\) $\mathrm{ndeg}(\mathrm{AND})=n$. deWolf03
PARITY total \(\lceil n/2 \rceil\) $\mathrm{ndeg}(\oplus_n)=n$. deWolf03
MAJORITY total \(\lceil (n+1)/4 \rceil\) Exactly, from $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf00] and the $\mathrm{ndeg} = (n+1)/2$ recorded above. Nondeterminism buys only a factor $2$ over $\mathrm{Q} = \Theta(n)$ here, unlike at \(\mathrm{OR}_n\) where $\mathrm{NQ} = 1$. deWolf00
Threshold total \(\Theta(k)\) putative Exactly $\lceil k/2 \rceil$, by de Wolf's $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = k$. Note this is not below $\mathrm{Q}$: at $k = n$ (\(\mathrm{AND}_n\)) nondeterministic quantum costs $n/2$ while bounded-error quantum costs $\Theta(\sqrt n)$, because the nondeterministic model is one-sided. deWolf00
Symmetric functions (general) total \(\Theta(\#\{j \,:\, f_j = 0\})\) putative de Wolf's $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ applied to the \(\mathrm{ndeg}(f)\) line above. Nondeterministic quantum query complexity of a symmetric function is governed by the number of $0$-slices, not by where they sit -- in sharp contrast with $\mathrm{Q}$, which sees only the distance $\Gamma(f)$ of the nearest jump to the middle layer. deWolf00
EXACT-HALF total \(\lceil n/4 \rceil\) $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ [deWolf00] applied to the $\mathrm{ndeg} = n/2$ line above. For the negation the same formula gives $\mathrm{NQ}(\overline{\mathrm{EH}}_n) = 1$: one nondeterministic query certifies inequality to $n/2$, while $n/4$ are needed to certify equality. deWolf00
ODD-MAX-BIT total \(\lceil (\lfloor n/2 \rfloor + 1)/2 \rceil\) Exactly, from $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ [deWolf00] and the \(\mathrm{ndeg}(f)\) line. So $\mathrm{NQ} = \Theta(n)$ while $\mathrm{Q} = \Theta(\sqrt n)$: nondeterminism is quadratically worse than bounded error here, the same phenomenon as at \(\mathrm{AND}_n\). deWolf00
ADDRESS / multiplexer total \(\Theta(k)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2 \rceil$ [deWolf00], and $\mathrm{ndeg} = \Theta(k)$ above. Together with $\hat L_1 = 2^k$ this is the zoo's only family separating spectral norm from either nondeterministic measure -- and the gap is exponential, not polynomial. deWolf00
Binary tree navigation total \(\Theta(k)\) $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ and $\mathrm{ndeg}(f) = \Theta(k)$ here. deWolf00
TRIBES total \(\Theta(\log n)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$, and $\mathrm{ndeg}(f) = w = \Theta(\log n)$ here. deWolf03
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\) De Wolf's exact characterisation $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ applied to the \(\mathrm{ndeg}(f)\) entry. Nondeterministic quantum queries are thus quadratically cheaper than $\mathrm{D} = N$ and match $\mathrm{Q}$.
NAND tree (balanced AND-OR formula) total \(2^{\lfloor d/2\rfloor - 1} = \Theta(\sqrt N)\) putative $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf03], and $\mathrm{ndeg}(f_d) = 2^{\lfloor d/2\rfloor}$ from the \(\mathrm{ndeg}(f)\) entry. Nondeterministic quantum queries therefore buy nothing over bounded-error quantum queries on the NAND tree, both being $\Theta(\sqrt N)$. deWolf03
Recursive MAJORITY-of-3 total \(\Omega(1.732^{\,d}),\ O(2^{d-1})\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ [deWolf03], with the \(\mathrm{ndeg}(f)\) window $[\Omega(1.732^{\,d}),\,2^d]$. Nondeterministic quantum queries are thus within a $1.155^{\,d}$ factor of the bounded-error $\mathrm{Q} = \Theta(2^d)$. deWolf03
Kushilevitz's function (iterated) total \(O(N^{0.6131})\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil \le 3^k/2$ [deWolf03], from the \(\mathrm{ndeg}(f)\) entry. deWolf03
Rubinstein's function total \(\le \lceil n/2\rceil\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil \le \lceil n/2\rceil$ [deWolf03], i.e. $O(\sqrt N)$ -- matching $\mathrm{Q} = \Theta(\sqrt N)$ up to constants, so nondeterminism buys nothing quantumly here. deWolf03
Ambainis-Sun function total \(O(k) = O(\sqrt N)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil \le \lceil (3k+2)/2\rceil$ [deWolf03], from the \(\mathrm{ndeg}(f)\) entry. deWolf03
AND composed with NOT-EXACT-HALF total \(\Theta(n) = \Theta(\sqrt N)\) De Wolf's exact characterisation $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ applied to the \(\mathrm{ndeg}(f)\) entry. Nondeterministic quantum queries cost $\sqrt N$ while bounded-error ones cost $N^{3/4}$ and $\mathrm{D} = N$. IJKKKSWW23
Meiburg's tournament-subcube function total \(\le 3962^{\,d}\) putative $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ [deWolf03] with $\mathrm{ndeg} \le 7923.9^{\,d}$ from the \(\mathrm{ndeg}(f)\) entry. deWolf03
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $f_{2m,m}$: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil$, so the $\mathrm{ndeg}$ line transfers verbatim.
Cheat-sheet functions total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(\sqrt n)$. Nondeterministic quantum query complexity is quadratically below $\mathrm{Q}$ here.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(n)$.
Gilmer-Saks-Srinivasan functions total \(O(n)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=O(n)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil=\widetilde O(n^{1/3})$.
Ambainis' exact-quantum function total \(O(2^d)\) Squeeze: $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil\le 2^{d-1}$ (de Wolf), and $\mathrm{ndeg}\le\deg=2^d$.
FORRELATION partial \(O(n)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = O(n)$. deWolf03
k-FORRELATION partial \(O(kn)\) $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil$ and $\mathrm{ndeg} = O(kn)$. deWolf03
Simon's problem partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = 1$: one nondeterministic quantum query guesses a colliding pair. Against $\mathrm{R} = \Theta(2^{n/2})$.
Deutsch-Jozsa partial \(1\) $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil = 1$, from $\mathrm{ndeg} = 1$ below.
Unique search partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03
Two-or-none search partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03
Marked bit partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03
Dense marked bit partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$. deWolf03
Gap-Majority partial \(\Theta(n)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = \Theta(n)$: nondeterministic quantum queries do not see the promise gap either.
Gap-Majority at constant gap partial \(\Theta(n)\) $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil$.
Parity-labelled FIND-1 partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil = 1$.
Approximate index partial \(\Theta(1)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = \Theta(1)$.
Collision problem partial \(1\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil = 1$: one nondeterministic quantum query, against $\mathrm{Q} = \Theta(n^{1/3})$ and $\mathrm{R} = \Theta(\sqrt n)$. Guessing a colliding pair is free; finding one is not.
Element distinctness total \(\Theta(n)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil$ and $\mathrm{ndeg} = \Theta(n)$. Certifying distinctness nondeterministically is as hard as it gets, even though the other side needs only a single colliding pair.
Ambainis-Belovs function partial \(O(1)\) $\mathrm{NQ} = \lceil \mathrm{ndeg}/2 \rceil \le 5$.
Triangle finding total \(2\) $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil$ [deWolf03] and $\mathrm{ndeg}=3$. Two queries suffice for a nondeterministic quantum verifier even though $\mathrm{Q}=\Omega(m)$. deWolf03
Ordered search partial \(1\) $\mathrm{NQ}=\lceil\mathrm{ndeg}/2\rceil$ [deWolf03] and $\mathrm{ndeg}=1$. deWolf03
Inner product mod 2 total \(\Theta(n)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ (\(\mathrm{NQ}(f)\) vs \(\mathrm{ndeg}(f)\)), and $\mathrm{ndeg} = \Theta(n)$ here. Nondeterminism buys at most a factor $2$ on the bent function -- contrast \(\mathrm{MP}_m\), where $\mathrm{NQ} = \Theta(N^{1/3})$ against $\mathrm{Q} = \Theta(\sqrt N)$. deWolf03
Minsky-Papert one-in-a-box total \(\lceil m/2 \rceil = \Theta(N^{1/3})\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf03], and $\mathrm{ndeg} = m$ here. deWolf03
Sink of a tournament total \(\lceil (m-1)/2 \rceil = \Theta(\sqrt N)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ [deWolf03], and $\mathrm{ndeg} = m-1$ here. deWolf03
Scorpion graphs total \(\Theta(m)\) $\mathrm{N}\mathrm{Q}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ exactly [deWolf03], and $\mathrm{ndeg} = \Theta(m)$ here. deWolf03
Graph connectivity total \(\lceil (m-1)/2 \rceil = \Theta(\sqrt N)\) $\mathrm{N}\mathrm{Q}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ exactly [deWolf03], and $\mathrm{ndeg} = m-1$ here. Nondeterministic quantum connectivity thus costs $\Theta(\sqrt N)$, below even $\mathrm{Q} = \Theta(N^{3/4})$: guessing a spanning tree is much easier than finding one. deWolf03