Quantum Complexity Classes and Oracle Separations — Examples

Let $N=2^n$ and $L=nN+n+1$, the length of the unary-header table code. For each of the $\left(\genfrac{}{}{0px}{}{N}{2}\right)$ distinct address pairs, scan the table to retrieve both $n$-bit outputs and answer NO if they coincide; answer YES if no pair collides. On a promised table this is correct, since YES functions are injective and every NO function has a collision.

One table scan and output comparison take $O(L)$ transitions, so the $\left(\genfrac{}{}{0px}{}{N}{2}\right)$ pairs take $O(N^{2}L)$ time. Since $N\le L$, this is $O(L^3)$; the explicit-table promise problem is therefore in deterministic polynomial time under [F4].

The oracle bounds in [F1] and [F2] charge calls to $f$ or $U_f$, whereas the explicit-input algorithm charges table scans and ordinary computation as required by [F5]. The deterministic $O(L^3)$ algorithm in step 2.1 contradicts the asserted absence of a polynomial-in-$L$ algorithm. Thus this oracle-query separation does not imply superpolynomial classical running time in the explicit-input length. This comparison does not refute an $\mathrm{\Omega }(2^{n\mathrm{/}2})$ time bound measured in $n$: the explicit table already has length $L=n{2}^n+n+1$.

The dot product with $s=01$ is the second coordinate, so $s^{\perp }=\{00,10\}$. Its span is itself and has rank one. Hence four NO samples cannot have rank two, and the algorithm rejects with probability one.

In $V_2$, the three one-dimensional subspaces are $\{00,10\}$, $\{00,01\}$, and $\{00,11\}$. Four vectors fail to span exactly when all four lie in one of these three subspaces. Each corresponding set of four-tuples has $2^4=16$ elements; every pairwise intersection and the triple intersection consist only of $(00,00,00,00)$. Inclusion-exclusion therefore gives $3\cdot 16-3\cdot 1+1=46$ failing tuples out of $4^4=256$.

By the independent runs in the given algorithm and the uniform YES law in [F1], each ordered four-tuple has weight $(1\mathrm{/}4{)}^4=1\mathrm{/}256$. Summing these weights by [F2], the exact failure probability is $46\mathrm{/}256=23\mathrm{/}128$. The union bound is $3\cdot 16\mathrm{/}256=3\mathrm{/}16$, agreeing with [F1] and strictly below $1\mathrm{/}4$. There are exactly four oracle runs by the algorithm's definition.