First complete quantum algorithm

The problem contract

Given oracle access to $f:\{0,1\}\to\{0,1\}$, decide whether f is constant ($f(0)=f(1)$) or balanced ($f(0)\ne f(1)$). There are four possible functions. A deterministic classical solution requires two evaluations in the worst case.

Prepare and query

Start with $\lvert0\rangle\lvert1\rangle$ and apply H to both qubits. The state becomes $\lvert+\rangle\lvert-\rangle$. Apply $U_f$ once. Phase kickback produces

$$\frac{(-1)^{f(0)}\lvert0\rangle+(-1)^{f(1)}\lvert1\rangle}{\sqrt2}\otimes\lvert-\rangle.$$

Apply H to the first qubit. If f is constant, the input becomes 0 up to global phase. If f is balanced, it becomes 1 up to global phase. Measuring the input therefore answers the question with one ideal query.

Extend to more input bits

Deutsch–Jozsa uses an n-bit input under the promise that f is constant or balanced over all $2^n$ inputs. Its all-zero output has probability one for a constant function and zero for a balanced function in the ideal model.

L05 · INTERACTIVE LABRuns on your device

Deutsch–Jozsa explorer

Under the promise that f is constant or balanced, phase kickback followed by interference distinguishes the two cases with one oracle query.

Make a prediction first

For a balanced oracle, should the all-zero input-register outcome ever occur in the ideal model?

Experiment controls

The phase-kickback model shows the input register. The |−⟩ ancilla is factored out. This lab assumes the constant-or-balanced promise.

Random seed

Run measurements →Reset

Exact probability

|00⟩

0.0%

|01⟩

100.0%

|10⟩

0.0%

|11⟩

0.0%

Exact ideal-model predictions · run a measurement experiment to compare.

MODEL · Ideal pure-state vector, complex double precisionORDER · q0 is the leftmost bit

Take it further

Compare constant-zero and constant-one. Why does their global phase difference not change the measured result?

Prediction: For a balanced oracle, should the all-zero input-register outcome ever occur in the ideal model? Challenge: Compare constant-zero and constant-one. Why does their global phase difference not change the measured result?

The lab shows two- or three-bit input registers after phase kickback and factors out the unchanged ancilla. The balanced preset uses the last input bit. It is one valid balanced example, not an enumeration of every possible function.

State the conclusion carefully

This is a query-model separation for a promised problem. It is not proof that a physical implementation outperforms a classical computer after oracle synthesis, noise, readout and total runtime are counted. Randomised classical comparisons also differ from the deterministic worst-case comparison above.

PAUSE & THINK

What is essential to the Deutsch–Jozsa conclusion?

Choose your answer

That f is promised constant or balancedThat every function is balancedThat a measurement reveals every f(x)

Check my answer

Your next investigation

Complete P7 and P8 in the practice studio, then compare this phase-kickback pattern with Grover amplification. Keep the input/output contract, assumptions and excluded costs in your report.

Reference: IBM Quantum — Fundamentals of quantum algorithms.