Deutsch’s Algorithm

One question about two function values

Deutsch’s problem asks whether a Boolean function has equal or different outputs on its two possible inputs. The alternatives are simple: f(0) and f(1) either agree or disagree. The algorithm does not need to reveal both values. It designs a measurement whose single output answers that relationship directly.

Review phase kickback and the first complete algorithm before the algebra. The important prerequisites are H on plus and minus, the difference between a global and relative sign, and the fact that a coherent oracle acts linearly on a superposition.

WORKED DIAGRAM · A02Deutsch's balanced identity example

For f(0)=0 and f(1)=1, one joint oracle call changes the input from plus to minus. A final H makes the input result one with probability one.

The exact contract

The input is a function from one bit to one bit, supplied through a reversible oracle. Its action is to retain x and XOR f(x) into a target y. There are four possible functions: constant zero, constant one, the identity and the complemented identity. The desired output is a classical label: constant or balanced. With one input bit, “balanced” means one zero and one one in the truth table.

The ideal quantum algorithm must answer exactly using one coherent oracle call. A deterministic classical algorithm evaluating the function at an ordinary input needs two calls in the worst case for the same exact guarantee. This is a modest query separation, not an end-to-end runtime demonstration. A physical oracle implementation can involve many gates and may be noisy.

The procedure

1. Prepare an input qubit in zero and a target in one.
2. Apply H to both. The input becomes plus and the target becomes minus.
3. Invoke the reversible oracle once.
4. Apply H to the input only.
5. Measure the input in Z. Interpret zero as constant and one as balanced.

The target is not measured to obtain the answer. It provides an eigenstate of X. When the oracle conditionally flips it, the target remains minus but contributes a negative sign to that input branch. This is the entire purpose of the target preparation.

Work the balanced identity function

Let f(0) be zero and f(1) be one. After preparation, the input is plus. The zero branch leaves the target alone. The one branch applies X to minus, producing negative minus. Factoring out the unchanged target gives a minus state on the input:

$$\frac{|0\rangle+|1\rangle}{\sqrt2}|-\rangle \longmapsto \frac{|0\rangle-|1\rangle}{\sqrt2}|-\rangle.$$

The final H maps minus to one, so the measured answer is balanced. Both input branches participated coherently in the calculation, but the measurement returns one property of the truth table. It does not supply a list containing f(0) and f(1).

Now use the complemented identity. The oracle gives negative plus on the zero branch’s sign and positive on the one branch, producing negative minus overall. The final H gives negative one. Its probability is still one because the common minus is global. The two balanced functions need not produce identical printed amplitudes to produce the same answer.

Work the constant cases

Constant zero attaches no signs. The input remains plus, and H returns zero. Constant one attaches a negative sign to both components. The input is negative plus, which differs only by global phase. H returns negative zero, giving the same zero outcome. The algorithm deliberately forgets which constant function it received because the requested output does not require that distinction.

The general output amplitudes make the mechanism concise:

$$\alpha_0=\frac{(-1)^{f(0)}+(-1)^{f(1)}}2, \qquad \alpha_1=\frac{(-1)^{f(0)}-(-1)^{f(1)}}2.$$

Equal signs reinforce at zero and cancel at one. Opposite signs cancel at zero and reinforce at one. This is the correctness argument. The calculation also shows why taking squared magnitudes immediately after the oracle would lose the distinction: both intermediate states have equal Z probabilities.

What changes the algorithm?

If the target were plus instead of minus, X would contribute eigenvalue positive one and no phase distinction would appear. If you measured the input immediately after the oracle, the result would be random in every case. If you kept the correct target but omitted the final H, the phase pattern would remain inaccessible to that Z readout. Each stage solves a specific part of the task.

An intermediate physical measurement is not a harmless print statement. It changes the coherent state. A simulator can expose amplitudes because they are a classical data structure, but hardware generally cannot return them directly. Use that simulator access to understand the mechanism without counting it as an experimental resource available to the algorithm.

Complexity and limits

The quantum procedure makes one oracle call and a constant number of elementary gates outside it. The exact deterministic classical comparison needs two evaluations. If classical error is allowed, one can guess with some success, so the guarantee must be matched before declaring an advantage. Noise also changes the quantum guarantee from exactness to a statistical claim about an implementation.

The lesson is a design pattern: encode a relation as phase, then choose an interference transformation that reveals it. Larger algorithms reuse that pattern, but the tiny example does not prove that general-purpose classical workloads become faster. Building the coherent oracle and arranging reliable gates remain practical costs.

Exercises

1. Calculate the final input amplitudes for constant one. Why is negative zero physically the same result as zero?

2. Replace the minus target with plus. Predict the final input measurement for all four functions and identify the lost mechanism.

Worked answers

1. The oracle produces negative plus, and the final H produces negative zero. Its only nonzero amplitude has magnitude one. Multiplying the whole state by negative one changes no measurement probability in any basis.

2. X leaves plus unchanged, so the oracle contributes no conditional sign. The input stays plus and the final H returns zero for every function. The procedure no longer classifies balanced functions because phase kickback was removed by the target choice.

Source

IBM’s derivation of Deutsch’s algorithm gives an authoritative educational account. Its displayed wire ordering differs from this book’s leftmost-q0 convention, so compare qubit identities rather than copying bitstring positions.

Predict and test

Choose one input qubit for Deutsch’s original problem. Predict the constant-zero, constant-one and balanced cases separately. The displayed state factors out the unchanged minus target; it includes the final input-register H.

L05 · INTERACTIVE LABRuns on your device

Deutsch–Jozsa explorer

A constant-or-balanced Boolean oracle acts by phase kickback, followed by H on each input qubit. The unchanged |−⟩ ancilla is factored out. One input qubit gives Deutsch’s original case.

Experiment controls

Random seed

Predict whether the all-zero input-register outcome can occur for the selected promised oracle.

Your prediction

Reveal exact resultsRun measurements →Reset

Record a prediction to enable the results.

Results are hidden.

Prepare your experiment using the controls. Record a prediction, then reveal the statevector or run the experiment.

Changing the preparation or circuit starts a new prediction.

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

Take it further

Constant-zero and constant-one differ by a global sign before the final H gates. Explain why their measured probabilities agree.

Initial setup · reference state

Exact probability

|00⟩

0.0%

|01⟩

100.0%

|10⟩

0.0%

|11⟩

0.0%

Statevector before readout · ideal simulation

Basis	Amplitude a + bi	Magnitude	Phase (rad)	Probability
|00⟩	0 + 0i	0.000000	undefined	0.0%
|01⟩	1 + 0i	1.000000	0.000000	100.0%
|10⟩	0 + 0i	0.000000	undefined	0.0%
|11⟩	0 + 0i	0.000000	undefined	0.0%

Signs and complex phases are part of the state. Phase is undefined for a zero amplitude. A shared global phase changes no probabilities; relative phases can affect a later operation. Values are rounded to six decimal places.

Prediction to try: Predict whether the all-zero input-register outcome can occur for the selected promised oracle.

Challenge: Constant-zero and constant-one differ by a global sign before the final H gates. Explain why their measured probabilities agree.

Open the live experiment studio

Trace the circuit or amplitudes

WORKED DIAGRAM · F26Deutsch: one oracle call, then interference

The upper wire is the input and the lower is the ancilla. Prepare |0⟩|1⟩, apply H to both, call Uf once, then apply H and measure the input. Constant gives 0; balanced gives 1 in the ideal one-bit case.

Check your understanding

PAUSE & THINK

What fails if Deutsch's target is prepared in plus instead of minus?

Choose your answer

The oracle becomes irreversibleX contributes no conditional sign, so every case returns zeroThe circuit reads both function values

Check my answer

Answer: X contributes no conditional sign, so every case returns zero. Plus is an X eigenstate with eigenvalue +1. The oracle leaves the input plus for all functions, and the final H returns zero.