Quantum Lab Session 4 Simulation Q10
🔮 Before we begin — the first quantum algorithm
Imagine a black box — a function f(x) — that takes a single bit (0 or 1) as input and gives a single bit as output. You don't know what's inside. You only know one of two things is true: either the function always gives the same output regardless of input (constant: f(0)=f(1)), or the function gives different outputs for different inputs (balanced: f(0)≠f(1)).

Classically, to determine which kind it is, you must query the function twice — once with input 0, once with input 1. There is no way around this.

In 1985, David Deutsch showed that a quantum computer can determine the answer with just one query. The algorithm puts the input into superposition, queries both 0 and 1 simultaneously, and uses interference to collapse directly to the answer. This was the first proof that quantum computers can solve a problem faster than any classical computer.
🌀 The philosophical significance
Deutsch's algorithm is almost useless practically — the problem it solves is artificial. But historically it was everything. It proved that quantum computation is not just faster classical computation — it is a fundamentally different model of computation. Every quantum algorithm since (Grover, Shor, QFT) builds on the same principle: superposition + interference = a single query answering what would take many classical queries.
🔮 Quantum Algorithms · Session 4 · Q10

Deutsch's Oracle

The algorithm that started it all. One quantum query does what two classical queries cannot avoid. Watch superposition and interference solve the problem in a single shot.

❓ The Problem
🔮 The Oracle
⚡ The Circuit
📊 Deutsch-Jozsa
🏆 Badge
❓

The question

Is f(x) constant (always same output) or balanced (different outputs)? Classical: 2 queries. Quantum: 1 query.

🔮

The oracle

A black-box quantum gate Uf that encodes f(x) without revealing it. You can only query it — not look inside.

⚡

The trick

H → Uf → H. Superposition queries both inputs at once. Interference makes the answer appear in the measurement.

📊

Deutsch-Jozsa

Generalises to n bits. Classical needs up to 2ⁿ⁻¹+1 queries. Quantum still needs only 1. Exponential speedup.

🔮
Wizzy · Quantum Guide
There are only 4 possible functions f:{0,1}→{0,1}. Two are constant (always output 0, or always output 1). Two are balanced (output flips). Classically you must query the function twice to tell which kind it is. There's no shortcut — the first query tells you nothing alone.
🌀 Why the first query isn't enough classically
If f(0)=0, the function could be "constant 0" or "balanced (outputs 0 for 0, 1 for 1)". You can't tell without also querying f(1). So classically you always need both queries. Deutsch's trick is to query f(0) AND f(1) simultaneously with one quantum operation.

Step 1 — The 4 Possible Functions

✅ Constant functions (2 total)
f₁ — Constant 0: f(0)=0, f(1)=0
f₂ — Constant 1: f(0)=1, f(1)=1
⚖️ Balanced functions (2 total)
f₃ — Identity: f(0)=0, f(1)=1
f₄ — NOT: f(0)=1, f(1)=0
The classical challenge: You receive a mystery oracle — one of these 4 functions. To determine if it's constant or balanced, you must call it with both inputs 0 and 1. That's always 2 queries. No classical algorithm can do it in 1.
Classical minimum queries
2 queries
Always — no exception
🔮
Wizzy · Quantum Guide
A quantum oracle Uf is a reversible gate that maps |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩. It encodes the function in a phase-kickback-friendly way. Select an oracle below and see its truth table. The key: when we put |x⟩ in superposition and |y⟩ = |–⟩, the oracle's effect gets kicked back into the phase of |x⟩ — and that's detectable with one measurement.
🌀 Phase kickback — the magic ingredient
When the ancilla qubit is prepared as |–⟩ = (|0⟩-|1⟩)/√2, querying the oracle flips the phase of |x⟩ based on f(x). Constant f: no phase difference. Balanced f: opposite phases. This difference is detectable via interference — without ever directly reading f(0) or f(1).

Step 2 — Choose a Quantum Oracle

f₁ — Constant 0

Always outputs 0. Never changes the ancilla qubit.

f(0)=0f(1)=0 CONSTANT
f₂ — Constant 1

Always outputs 1. Flips ancilla qubit always.

f(0)=1f(1)=1 CONSTANT
f₃ — Identity (balanced)

Outputs what it receives. Ancilla flips iff x=1.

f(0)=0f(1)=1 BALANCED
f₄ — NOT (balanced)

Flips every input. Ancilla flips iff x=0.

f(0)=1f(1)=0 BALANCED
Select an oracle. The quantum algorithm will determine if it's constant or balanced — using only 1 query.
🔮
Wizzy · Quantum Guide
The full Deutsch circuit: prepare both qubits, apply H to both, query the oracle once, apply H to the first qubit, measure. Press each step to walk through the state evolution. The key moment is after the oracle — the phase of qubit 0 encodes the answer through destructive interference.
🌀 How one query beats two
The oracle is called exactly once — but it's called with qubit 0 in superposition (|0⟩+|1⟩)/√2. This means it effectively evaluates f(0) and f(1) simultaneously. The ancilla qubit |–⟩ converts the function evaluation into a phase flip — and the final H gate on qubit 0 turns the phase difference into an observable amplitude difference.

Step 3 — Deutsch's Algorithm

Oracle: none selected
Press Step to walk through the circuit. Each press advances one gate.
🔮
Wizzy · Quantum Guide
Deutsch-Jozsa extends this to n-bit functions. For n=10, a classical computer needs up to 513 queries (2⁹+1) to be certain. Quantum still needs exactly 1 query. The speedup grows exponentially with n. Drag the slider to see the comparison.
🌀 Exponential speedup from one circuit
The same H → Uf → H structure works for n qubits. Apply H to all n input qubits simultaneously, query the oracle once on n qubits in superposition, apply H to all n qubits, measure. One oracle call. Always. The classical algorithm's query count grows as 2ⁿ⁻¹+1. Quantum stays at 1.

Step 4 — Deutsch-Jozsa: n-bit Scaling

4
Classical worst case
9
2ⁿ⁻¹ + 1 queries
Quantum (always)
1
1 query — always
With 4 bits: classical needs up to 9 queries, quantum needs 1
Real-world relevance: Deutsch-Jozsa itself is rarely used in practice — the problem is contrived. But it demonstrated the principle that launched quantum algorithm theory. Grover (Q11) and Shor (Q12) use the same fundamental mechanism for genuinely useful problems.
🔮
Wizzy · Quantum Guide
🎊 You've understood the first quantum algorithm ever devised! In 1985, Deutsch proved quantum computers are fundamentally different. Every quantum algorithm you'll learn — Grover, Shor, QFT — builds on this same foundation: superposition + phase kickback + interference = fewer queries.
🧠 What you actually learned today
  • The constant-vs-balanced problem: 4 possible functions, 2 query classical minimum, 1 query quantum solution.
  • Quantum oracles are reversible gates Uf that map |x⟩|y⟩ → |x⟩|y⊕f(x)⟩ — they encode functions without revealing them directly.
  • Phase kickback: preparing the ancilla as |–⟩ turns oracle queries into phase flips on the input qubit — detectable by interference.
  • Deutsch's circuit: H → Uf → H gives the answer in one oracle query through superposition and interference.
  • Deutsch-Jozsa generalises to n bits: classical needs 2ⁿ⁻¹+1 queries, quantum needs 1 — exponential speedup from a single circuit.
🔮

Oracle Master Badge!

You understood the algorithm that launched the quantum computing revolution!

🔮 WhizzStep Quantum Lab
This certifies that
Student Name
has mastered Deutsch's Oracle — the first quantum algorithm
Oracle Master
Phase Kickback
Deutsch-Jozsa
📖 Quantum Vocabulary
Oracle NEW

A black-box quantum gate that encodes a function f without revealing its internals. You can only query it — not inspect it. Crucial to quantum algorithms.

Like a locked vending machine — you put in an input and get an output, but can't see the mechanism inside.
Phase kickback KEY

When the ancilla qubit is |–⟩, an oracle query flips the phase of the control qubit based on f(x). This converts function evaluation into a phase — detectable by H gates.

Constant function

f(0) = f(1) — same output regardless of input. Deutsch's algorithm outputs |0⟩ when measured.

Balanced function

f(0) ≠ f(1) — different output for each input. Deutsch's algorithm outputs |1⟩ when measured. Perfect correlation — no ambiguity.

Query complexity NEW

The number of times you call an oracle to solve a problem. Quantum algorithms often achieve exponentially lower query complexity than classical ones.

Deutsch-Jozsa

The n-bit generalisation. 1 quantum query vs 2ⁿ⁻¹+1 classical queries for n-bit constant-vs-balanced testing. The first exponential quantum speedup proof.

Key Concepts from Q10

Oracles

🔮 Black-box gates

Quantum algorithms are usually analysed in terms of oracle queries — how many times must you call the black box? Reducing this count is the quantum advantage.

Phase kickback

⚡ The core mechanism

Preparing the ancilla as |–⟩ converts oracle function evaluation into phase manipulation — and phases are manipulated by H gates into probabilities. This exact trick powers Grover and Shor.

Interference

🌊 The amplifier

Constant oracle: both paths have same phase → constructive interference → measure 0. Balanced oracle: opposite phases → destructive interference → measure 1. One query, definite answer.

Deutsch-Jozsa

📊 Exponential gap

The n-bit version of Deutsch's algorithm gave the first proof of an exponential quantum speedup over classical computation. Historically crucial, even if the problem was contrived.