Your objective
Explain the Deutsch‑Jozsa problem, understand how a quantum circuit can decide if a function is constant or balanced with a single query, and implement the algorithm in a quantum circuit.
5.1 Problem Statement
Define constant and balanced functions and discuss classical query complexity.
Classical worst‑case: 2ⁿ queries Quantum: 1 query
5.2 Quantum Idea
Prepare an equal superposition of all inputs, evaluate f coherently, then apply a Hadamard transform to interfere the amplitudes and reveal the answer.
|0…0⟩ → H^{⊗n} → |+⟩^{⊗n}
Apply controlled‑f → H^{⊗n} → Measure5.3 Circuit Overview
The circuit consists of n Hadamard gates on the input qubits, a single oracle query, another layer of Hadamard gates, and measurement of the first qubit (or all qubits).
Circuit diagram showing H⊗n → Oracle → H⊗n → Measure
Put it together
Worked example
For n=2, suppose f is constant (f(x)=0). After the algorithm the measurement of the input register yields 00 with certainty. If f is balanced (e.g., f(00)=0, f(01)=1, f(10)=0, f(11)=1) the measurement yields 11 with certainty.
Key takeaways
• The algorithm decides constant vs. balanced with a single query. • Interference of amplitudes is the key mechanism. • It solves a total‑function problem exponentially faster than any classical algorithm.
Knowledge check / 3 questions