Exact Oracle Algorithms — Examples

The Deutsch truth tables give $(f(0),f(1))=00,11⟹\text{constant},(f(0),f(1))=01,10⟹\text{balanced}\mathrm{.}$ The exact Deutsch theorem [F4] therefore outputs $0$ on the first two tables and $1$ on the latter two.

For the two-bit Deutsch–Jozsa function $f(x)=x_0$, the table is $00\mapsto 0$, $01\mapsto 0$, $10\mapsto 1$, $11\mapsto 1$, so it is balanced by [F2]. Its final address amplitude is ${\alpha }_y=\frac{1}{4}{\sum }_{x\in \{0,1{\}}^2}(-1{)}^{x_0+x\cdot y}\mathrm{.}$ For $y=00,01,10,11$, these sums are respectively $0,0,4,0$, so the measured output is $10$. The classical exact bound is $N\mathrm{/}2+1=3$ queries, and the three-distinct-sample experiment is exact for $N=4$ because any three of four addresses include both output values.

For $a=10$, the two-bit Bernstein–Vazirani amplitude at $y$ is ${\alpha }_y=\frac{1}{4}{\sum }_{x\in \{0,1{\}}^2}(-1{)}^{x\cdot (10\oplus y)}\mathrm{.}$ The sums for $y=00,01,10,11$ are $0,0,4,0$, respectively; hence the exact output is $10$. By [F5], classical bounded-error recovery needs at least two queries and the two basis queries suffice.

For Deutsch, the deterministic exact classical query count is two while one randomized query has worst-case success at most $1\mathrm{/}2$ by [F5]. For two-bit Deutsch–Jozsa the exact deterministic count is three, while the without-replacement three-sample experiment succeeds with probability one on this finite domain. The finite fair-bit algorithm with replacement has success at least $3\mathrm{/}4$ by [F5]. For two-bit Bernstein–Vazirani two classical queries recover both secret bits. These are query counts; none is a classical bit-time claim.