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
- \(\mathrm{ndeg}(f)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2 \rceil$ deWolf03
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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |