Deutsch, and Deutsch–Jozsa

David Deutsch's 1985 paper, Quantum theory, the Church–Turing principle and the universal quantum computer, is the one that asked what quantum mechanics does to the Church–Turing thesis, and it contained the first problem a quantum computer solves in fewer queries than a classical one. Take a box computing f : {0,1} → {0,1}. The question is whether f(0) = f(1), that is, whether f is constant or balanced. Classically that takes two queries. Quantumly it takes one: query the box in superposition, interfere, and measure. The form taught today, which answers with certainty, is a later refinement of the original.

Deutsch and Jozsa (1992) extended it to n bits under a promise: the box computes f : {0,1}ⁿ → {0,1}, and f is promised to be either constant or balanced (equal to 1 on exactly half the inputs). A deterministic classical algorithm needs 2ⁿ⁻¹ + 1 queries in the worst case, and a quantum one needs a constant number. Who got it to one query, with certainty, is a matter of record worth getting right. Deutsch's original algorithm worked only probabilistically; Deutsch and Jozsa made it deterministic, but their method used two function evaluations; the one-evaluation version taught today is due to Cleve, Ekert, Macchiavello and Mosca (1998), and independently to Tapp in unpublished work. The circuit simulated below is that improved one. The names Deutsch and Deutsch–Jozsa stay on it, as Nielsen and Chuang put it, for the first demonstration that a quantum computer could do something faster, and for the first gap in how the time scales.

Bernstein–Vazirani: one query for n bits

Ethan Bernstein and Umesh Vazirani's 1993 paper, Quantum complexity theory, gives the next problem. A box computes f(x) = s·x mod 2 for a hidden string s of n bits, and the task is to find s. Each classical query returns one bit about s, so n queries are needed and n suffice. The quantum algorithm, in the one-query form Cleve, Ekert, Macchiavello and Mosca gave, is the Deutsch–Jozsa circuit unchanged: Hadamards, one phase query (−1)^s·x, Hadamards. (Bernstein and Vazirani's own version used two evaluations, as Deutsch and Jozsa's did; Cleve et al. note that one network solves both problems.) The state that comes out is |s〉 exactly, and measuring it gives s with certainty. That is n against 1, a linear gap, and the chapter does not call it more. The same paper's recursive version of the problem is where the structure gives a super-polynomial separation, relative to an oracle. The speedup lives in the promise that f is linear.

Grover: a rotation in a two-dimensional plane

Take N = 2ⁿ items, M of them marked, and a box that says whether a given item is marked. Classically, finding one costs about N/2 queries on average. Grover's algorithm starts in the uniform superposition and repeats two steps: flip the sign of the marked amplitudes (the oracle), then reflect every amplitude about the mean (diffusion). Each pair rotates the state by 2θ in the plane spanned by “marked” and “unmarked”, where θ = arcsin√(M/N), so after k iterations the chance of measuring a marked item is

P(k)  =  sin^2( (2k + 1) theta )

The optimal k is about (π/4)√(N/M): a quadratic speedup, not an exponential one. For N = 4 with one marked item it is exact after one iteration. The case of more than one marked item is Boyer, Brassard, Høyer and Tapp's (1998), and the one the M = 2, 3 runs below test.

All four, run on explicit vectors

ch-quantum-oracles-verify.py does not use closed forms to produce its numbers. It builds the amplitude vector and applies the operations.

Deutsch        all 4 functions {0,1}->{0,1}: one query separates constant
               from balanced with certainty
Deutsch-Jozsa  n = 1..4: every constant and every balanced function enumerated
               (2 + C(2^n, 2^(n-1)): 4, 8, 72, 12872 functions);
               P(0...0) is exactly 1 for constant, exactly 0 for balanced
               classical, against every promise function as a truth table (n = 2, 3):
               2^(n-1) queries cannot decide (76 query sets),
               2^(n-1)+1 always can (60 query sets)
               random classical: error <= 2^(1-k), exact, n = 3, 5, 8
Bernstein-     all 510 secrets, n = 1..8: P(measure s) = 1 after one query
Vazirani       any q < n classical queries leave >= 2 consistent strings:
               exhaustive over 37,062 query sets, n = 2..5
Grover         604 cases (n=2..11, M=1,2,3, every k over a full period):
               largest |simulation - sin^2((2k+1)theta)| = 4e-13
               N=4: P(1) = 1;  P >= 1 - 1/N at k_opt, n = 2..11
               n=24: k_opt = 3216 (classical mean 8,388,608); log2(k)/n = 0.485 -> 1/2
               n=10: P(k_opt = 25) = 0.9995;  P(2 k_opt) = 0.0002   (overshoot)

The overshoot line is worth reading twice: Grover is not “run it longer for a better answer”. At twice the optimal count the success probability is two in ten thousand, because the state has rotated past the target.

The controls each have to fail, and do. Without the oracle sign flip, without the diffusion reflection, and with the wrong formula sin²(kθ), Grover misses the simulation by more than 0.01. An oracle for a non-linear function (the AND of two bits) does not return a single basis state in Bernstein–Vazirani. A function that breaks the Deutsch–Jozsa promise gives P(0…0) = 0.25, strictly between 0 and 1, so the promise is doing real work; and without the final Hadamards a balanced function does not read out as 0.

Computability is not complexity

The corpus has no other quantum-computing chapter, and the only quantum-computing claim in its research register is that braiding is universal for topological quantum computation, which nothing here touches. WP-50 says every model of computation proposed is equivalent to or weaker than a Turing machine, quantum computers included. That is a statement about what is computable, and it stands: a quantum computer computes no function a Turing machine cannot. These four algorithms are statements about how many queries it takes, a different question, and the two do not conflict. Deutsch's 1985 paper is where the two questions first met, in its own title. This chapter keeps them apart in print.