Checkpoint: Query Complexity

This checkpoint consolidates the module's query-complexity thread by putting four canonical black-box problems side by side and computing, for each, the quantum and classical query counts. The point is to read off the shape of the speedup — quadratic, exponential, or none — and to see why structure in the oracle is what determines it.

The four problems

| Problem | Promise / task | Quantum queries | Classical (worst case) | Speedup | |---|---|---|---|---| | Deutsch–Jozsa | $f$ constant or balanced; decide which | $1$ | $N/2 + 1$ | exponential | | Bernstein–Vazirani | $f(x) = a\cdot x \bmod 2$ ; find $a$ | $1$ | $n$ | linear $\to$ constant | | Simon | $f(x)=f(x\oplus s)$ ; find period $s$ | $O(n)$ | $\Theta(\sqrt N)$ | exponential | | Grover | one marked item; find it | $\Theta(\sqrt N)$ | $\Theta(N)$ | quadratic |

For the exercise we fix $n = 6$ , so $N = 2^n = 64$ .

Where each number comes from

Deutsch–Jozsa. A single query to the phase oracle, sandwiched by Hadamards, maps the all-zeros input to a state that is $\ket{0\cdots0}$ iff $f$ is constant. One quantum query decides it exactly. Classically, a deterministic algorithm could see up to $N/2$ equal values and still not know (a balanced function could agree on the first half); it needs $N/2 + 1$ queries in the worst case to be certain — $33$ for $N=64$ . This is the first exponential separation, albeit only for exact (zero-error) computation; with randomness the classical gap shrinks.

Bernstein–Vazirani. Here the same one-query Hadamard sandwich returns the entire hidden string $a$ at once: the final measurement yields $a$ with certainty. Classically each query $f(e_i) = a_i$ reveals a single bit, so $n$ queries are needed and sufficient. The separation is $n$ versus $1$ — modest, but a clean illustration of extracting global information in one shot.

Simon. The exponential speedup that directly inspired Shor. Each quantum query yields a random vector $y$ orthogonal to the hidden period $s$ ; after $O(n)$ queries one has $n-1$ independent constraints and solves a linear system over $\mathbb F_2$ for $s$ . Classically, finding a collision $f(x)=f(x')$ requires probing $\Theta(\sqrt N) = 2^{n/2}$ inputs by the birthday bound — $8$ queries for $n=6$ — and this is a proven lower bound, making Simon an unconditional exponential separation in the query model.

Grover. As derived earlier, $\theta = \arcsin(1/\sqrt N)$ and the optimal iteration count is $\mathrm{round}\!\big(\pi/(4\theta) - 1/2\big)$ , which for $N=64$ is $6$ (close to $\tfrac{\pi}{4}\sqrt{64} \approx 6.28$ ). Classically a deterministic search needs $N-1 = 63$ queries in the worst case. The ratio $63$ vs $6$ reflects the $\Theta(N)$ vs $\Theta(\sqrt N)$ quadratic gap.

Try it

Fix $n=6$ ( $N=64$ ) and compute, from first principles, the quantum and classical query counts for all four problems, plus two booleans: whether Grover's speedup is quadratic (classical $\approx$ quantum $^2$ ) and whether Simon's is exponential. return the object { N, groverQ, groverC, djQ, djC, bvQ, bvC, simonQ, simonC, groverSpeedupIsQuadratic, simonSpeedupIsExponential }.

Run your code to see the quantum state.