Years 11–12 · Week 10 of 12
Deutsch–Jozsa and Bernstein–Vazirani
Learning goals
By the end, you can…
- State the promised Deutsch–Jozsa problem and the Bernstein–Vazirani problem.
- Explain the role of a reversible oracle and an ancilla prepared in |−⟩.
- Trace phase kickback and the final Hadamard layer conceptually.
- Interpret the ideal measurement without overstating practical speed-up.
What you already know
Connect to a familiar idea
Quantum circuits can encode relative phase and then use interference to convert it into measurement probabilities. These algorithms provide small, precise examples of that pattern.
- Hadamard gates and interference
- Multi-qubit basis strings
- CNOT and reversible circuit ideas
Opening story
Start with something familiar
Imagine a sealed function box. You may choose inputs but cannot inspect its internal rule directly. An oracle model counts how many times an algorithm queries that box, allowing different strategies to be compared under a clearly stated problem promise.
Plain-English explanation
Build the idea carefully
Problem definitions and reversible oracles
Deutsch–Jozsa assumes a promised Boolean function f:{0,1}ⁿ→{0,1} that is either constant on every input or balanced, meaning half its outputs are 0 and half are 1. The task is to identify which case holds. Bernstein–Vazirani uses fₛ(x) = s·x mod 2 for an unknown n-bit string s. The dot denotes the parity of the bitwise products. The task is to determine s under this specific oracle promise.
Phase kickback, interference and interpretation
A standard reversible oracle acts as |x,y⟩→|x,y⊕f(x)⟩. Preparing the target ancilla in |−⟩ turns this conditional bit flip into the relative phase (−1)^f(x) on the |x⟩ component; this is phase kickback. A final Hadamard layer makes the phase-labelled amplitudes interfere. In ideal Bernstein–Vazirani, measuring the input register gives s. These oracle-query demonstrations clarify quantum interference; they do not show that every practical problem receives an exponential speed-up.
Try the model
Bernstein–Vazirani and Deutsch–Jozsa lab
Select a two- or three-bit hidden string or a promised constant/balanced function, construct its oracle, and step through the circuit.
Qubit 0 is the least-significant state-vector bit. Displayed basis labels read q(n−1)…q0.
Ready. Adjust a control, then run the model.
What this model shows: This is an ideal educational oracle simulation. Circuit construction cost and hardware noise are not hidden behind claims of general speed-up.
Text alternative for this interactive
Text alternative: each input basis amplitude gains phase (−1)^(s·x); the final Hadamard transform cancels amplitudes for every output string except s.
Expected observation: For a valid Bernstein–Vazirani oracle, the ideal final measurement equals the selected hidden string with probability one.
Guided activity
Recover a hidden string
- Choose s = 101 and calculate s·x mod 2 for all three-bit x.
- Mark the phase factor (−1)^(s·x) for every basis component.
- Build and run the corresponding oracle circuit.
- Compare the predicted ideal output with the simulated histogram and state the problem promise.
Evidence to collect: A complete parity and phase table, a valid oracle circuit, an ideal output of 101 and a written statement limiting the conclusion to the specified promised-oracle problem.
Glossary
Words to know
- oracle
- A reversible circuit that provides access to a specified function.
- promise problem
- A problem whose inputs are guaranteed to satisfy stated conditions.
- balanced function
- A Boolean function returning 0 on half its inputs and 1 on half.
- hidden string
- The unknown bit string defining the Bernstein–Vazirani function.
- phase kickback
- The transfer of a controlled operation's effect into relative phase.
- ancilla
- An additional qubit used to support a computation.
- query
- One use of an oracle in an algorithmic cost model.
Short recap
Keep these ideas
- Deutsch–Jozsa and Bernstein–Vazirani solve explicitly promised oracle problems.
- A reversible oracle can encode f(x) into phase using a |−⟩ ancilla.
- Final Hadamards turn phase structure into measurable interference.
- Small oracle demonstrations do not imply a general practical speed-up.
Knowledge check
7 clear questions
Choose an answer for immediate feedback. You may retry, and your best submitted score is kept.
Mathematical Extension Optional extension for Year 12
Use the identity H^{⊗n}|x⟩ = 2^(−n/2)Σ_z(−1)^(x·z)|z⟩, where the sum is over every n-bit string z in {0,1}ⁿ. For Bernstein–Vazirani, combine this with phase (−1)^(s·x) and show that the amplitude sum cancels for z ≠ s and reinforces for z = s.
Try this
Carry out the sign-sum calculation for n = 2 and s = 10. List the four contributions to each possible output amplitude.
Adult support Teacher and parent notes
Discuss
- What promise makes each problem well-defined?
- Where is function information stored before the final Hadamards?
- Why is oracle-query complexity not the same as full implementation cost?
Answer guidance
Require the correct parity definition of s·x, a reversible oracle and qualified claims. Do not accept 'reads all answers' as an explanation.
Offline activity
Create plus/minus phase tables on paper for two-bit hidden strings. Students combine columns to see which output pattern reinforces.
Safety
The activity is mathematical and simulated. Avoid linking the demonstration to unsupported claims about current commercial performance.
Sources and further reading
Checked references for this lesson
These sources support the lesson’s main scientific claims. Links open on the source organisation’s site.
- The Deutsch-Jozsa algorithm IBM Quantum Learning · official learning module · checked 2026-08-02
- Understanding quantum oracles Microsoft Learn · official documentation · checked 2026-08-02
- Circuits IBM Quantum Learning · official learning module · checked 2026-08-02
- Quantum Computation and Quantum Information Cambridge University Press · textbook publisher page · checked 2026-08-02
Content review: Reviewed on 2026-08-02.