Quantum Algorithms I: Deutsch-Jozsa & Grover's Search

Deutsch-Jozsa and Grover are query algorithms: their headline advantages count calls to a coherent black-box oracle, not complete wall-clock work. Deutsch-Jozsa decides whether a promised Boolean function is constant or balanced with one quantum query; without that promise, its conclusion is invalid. The circuit prepares a uniform superposition, uses phase kickback to encode function values as signs, interferes them with Hadamards, and classifies all-zero output as constant.

Grover search assumes a phase oracle that marks M good states in a space of N candidates and a state-preparation/reflection pair that amplifies their total amplitude. The two-reflection Grover iterate rotates within a two-dimensional good/bad subspace. For known M, about pi/4 times sqrt(N/M) iterations maximize success; continuing beyond the optimum rotates amplitude away. Unknown M needs counting, randomized iteration schedules, or another justified strategy, and zero-solution behavior must be specified.

An oracle must be reversible, clean its work qubits, mark exactly the intended predicate, and include its construction cost in any practical resource claim. A database is not queried in superposition for free: data loading, arithmetic, ancillas, synthesis, connectivity, error correction, verification, and repeated shots can dominate. The quadratic Grover advantage is asymptotic query complexity, not an automatic quadratic application-speedup.

Production evaluation should retain the formal promise, oracle truth table for small cases, marked-set cardinality, preparation and inverse, iteration policy, transpiled resources, target, shots, decoding, and independent classical verification. The production invariant is oracle-accounted advantage: every correctness and speedup claim includes the coherent oracle's semantics and cost, handles promise violations and unknown solution counts, and is supported by end-to-end resource and statistical evidence.

Grover's quadratic advantage is a query-count statement, and translating it into a runtime statement is where most application claims fail. Search a space of N = 2^20 with a single marked item: the optimal schedule is about pi/4 times the square root of N, or roughly 804 iterations, against 1,048,576 classical evaluations. That ratio looks decisive until each iteration is costed. The diffusion operator contains a multi-controlled phase on 20 qubits, which with ancillas decomposes into on the order of 36 Toffoli gates, each of which is about 6 CNOTs — roughly 216 two-qubit gates per diffuser, and the oracle typically costs at least as much again, since it has to compute the predicate reversibly and uncompute its scratch. That puts the circuit near 350,000 two-qubit gates. At a physical two-qubit error rate of 0.5 percent, the probability that such a circuit runs without a fault is e to the power of about -1,750: indistinguishable from zero, which is the real reason Grover is a fault-tolerant algorithm rather than a NISQ one. The classical comparison is equally unflattering in wall-clock terms — a million predicate evaluations at a nanosecond each is a millisecond — so a defensible Grover claim states the fault-tolerant resource estimate, not the iteration count.

The promise in Deutsch-Jozsa is load-bearing, and violating it produces a confident wrong answer rather than an error. The algorithm's all-zeros outcome probability is the squared magnitude of the average of (-1) raised to f(x) over the domain, which is 1 for a constant function and 0 for a balanced one. Feed it a function that is neither — say one that returns zero on three quarters of its inputs — and that average is 0.5, so the measurement returns all zeros about 25 percent of the time and the caller reads "constant" for a function that is not. Nothing in the circuit detects this, because a promise is an input precondition, not a property the algorithm verifies. Grover has the corresponding failure at the other end: the iteration count depends on the number of marked items M, and running the schedule for M = 1 against an instance with M = 4 rotates past the optimum and lands near the minimum, so success falls rather than rises with effort. If M is unknown, the correct constructions are quantum counting first or the exponentially increasing randomized schedule, which finds a solution in expected order square root of N/M queries without knowing M in advance. The zero-solution case has to be specified separately, because an oracle that marks nothing returns a uniformly random candidate that the algorithm cannot distinguish from a real one — which is why every Grover result must be verified classically against the predicate before it is used, a check that costs one evaluation and removes the entire class of false positives.

The most common implementation bug in an oracle is an uncomputation error, and it destroys the algorithm without producing an obviously broken circuit. An oracle that computes its predicate into ancilla registers and then applies the phase must run the computation in reverse to return those ancillas to the all-zero state. Skip the uncompute and the ancillas remain entangled with the search register, which makes the branches of the superposition distinguishable and collapses the interference the diffuser depends on: amplitude amplification stops amplifying, and the measured distribution stays close to uniform for every iteration count. The failure looks like a hardware noise problem — a flat histogram — so teams often respond by adding shots, which cannot help. The test that finds it is to run the oracle alone on a small instance and assert that every ancilla returns to zero with probability one, and to check on three or four qubits that the marked amplitude actually grows with iteration count rather than staying flat. Grover generalizes to amplitude amplification over any state preparation and its inverse, which is where the technique earns real use — as a subroutine that raises a known success probability p to near one in about the reciprocal of the square root of p repetitions — and reporting it that way, with the preparation cost included, is more honest than describing it as searching a database.