What Is a Quantum Algorithm? How Quantum Programs Work
Understand the structure of quantum algorithms through state preparation, oracles, interference, and measurement, using Deutsch's algorithm as the clearest possible example.
A quantum algorithm is not a classical program that runs on quantum hardware. It is a fundamentally different kind of computation, one that exploits superposition, interference, and entanglement to solve problems in ways that have no classical equivalent. This tutorial explains the structure that all quantum algorithms share and illustrates it with the simplest possible example.
The Four Phases of Every Quantum Algorithm
Almost every quantum algorithm follows the same four-phase structure:
- State preparation: Initialize qubits into the starting quantum state
- Quantum oracle: Apply a black-box function that encodes the problem
- Interference: Amplify correct answers, suppress wrong ones
- Measurement: Read out the result with high probability
Understanding each phase is the key to understanding quantum computing beyond the hype.
Phase 1: State Preparation
Quantum computers initialize all qubits in the |0⟩ state. State preparation transforms this default state into the starting superposition the algorithm needs.
The most common preparation step is applying Hadamard gates to all input qubits. This creates an equal superposition of all possible inputs:
H⊗n|0...0⟩ = (1/√2ⁿ) Σ|x⟩ for all x from 0 to 2ⁿ-1
In plain terms: after applying H to n qubits all starting in |0⟩, the system is simultaneously in all 2ⁿ computational basis states with equal probability amplitude.
from qiskit import QuantumCircuit
# 3 qubits: equal superposition of all 8 states (000 through 111)
qc = QuantumCircuit(3)
qc.h([0, 1, 2])
# The state is now (|000⟩ + |001⟩ + |010⟩ + ... + |111⟩) / √8
This is where the “quantum parallelism” story comes from. But as we will see, creating superposition is not the payoff; using interference after the oracle is the payoff.
Phase 2: The Quantum Oracle
An oracle is a quantum circuit that encodes a function f(x) without revealing the answer directly. The oracle acts on a superposition of all inputs simultaneously.
The standard oracle model uses a phase-kickback trick. For a Boolean function f(x) that outputs 0 or 1, the oracle applies:
|x⟩ --> (-1)^f(x) |x⟩
States where f(x) = 0 are unchanged. States where f(x) = 1 get a phase flip (multiplied by -1). This phase difference is invisible to a single measurement, but it becomes visible after the interference step.
The oracle is called a “black box” because the algorithm treats it as an unspecified component. The same algorithm structure works for any function that can be implemented as a quantum oracle. This generality is what makes quantum algorithms powerful; you prove the speedup for all possible oracles, not just specific functions.
Phase 3: Interference
After the oracle has marked the correct answer(s) with a phase flip, the interference step amplifies those states and suppresses the others.
The specific mechanism varies by algorithm:
- In Grover’s search, it is the diffusion operator (inversion about the mean)
- In Shor’s algorithm, it is the Quantum Fourier Transform
- In Deutsch’s algorithm (below), it is a second Hadamard gate
The mathematical result is the same in all cases: probability amplitude concentrates on the states corresponding to correct answers.
Phase 4: Measurement
Once interference has amplified the correct answer, measurement extracts it. Because the amplitude is concentrated on the right answer, you get it with high probability, often near certainty after enough iterations.
Measurement is irreversible. After measurement, the quantum state collapses to a single classical outcome. The algorithm must be designed so that this outcome is useful.
Deutsch’s Algorithm: The Clearest Example
Deutsch’s algorithm (1985) solves a simple but illuminating problem. It was the first quantum algorithm to provably outperform any classical algorithm for the same problem.
The problem: You have a black-box function f that takes one bit (0 or 1) and outputs one bit. There are four possible functions:
Constant functions: f(0) = 0, f(1) = 0 (always 0)
f(0) = 1, f(1) = 1 (always 1)
Balanced functions: f(0) = 0, f(1) = 1 (identity)
f(0) = 1, f(1) = 0 (NOT)
The question: Is f constant (both outputs the same) or balanced (outputs differ)?
Classical solution: Query f(0), then query f(1), compare the results. That requires 2 queries.
Deutsch’s quantum solution: Determine the answer in exactly 1 query.
This is a genuine quantum advantage, not just a speedup, but a reduction in the number of oracle calls from 2 to 1.
Why This Matters
The query complexity reduction from 2 to 1 might seem trivial. But it establishes a principle: quantum computers can extract global properties of functions (constant vs balanced) with fewer queries than classical computers. Grover’s and Shor’s algorithms scale this principle to exponentially larger speedups.
Deutsch’s Algorithm Step by Step
Start with 2 qubits: one input qubit (q0) and one ancilla qubit (q1) used by the oracle.
Initial state: |0⟩|0⟩
Step 1: Prepare ancilla in |−⟩ = (|0⟩ - |1⟩)/√2
Apply X to q1: |0⟩|1⟩
Apply H to q1: |0⟩|−⟩
Step 2: Apply H to input qubit
Apply H to q0: |+⟩|−⟩ = (|0⟩ + |1⟩)/√2 ⊗ (|0⟩ - |1⟩)/√2
Step 3: Apply oracle Uf
(phase kickback marks f's global structure)
Step 4: Apply H to input qubit again
Step 5: Measure input qubit
Result 0 --> f is constant
Result 1 --> f is balanced
The ancilla qubit in state |−⟩ is what enables phase kickback. When the oracle flips the ancilla, the phase ends up on the input qubit instead; this is a standard trick used across many quantum algorithms.
Qiskit Implementation
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
def deutsch_circuit(oracle_type):
"""
oracle_type: 'constant_0', 'constant_1', 'balanced_id', 'balanced_not'
"""
qc = QuantumCircuit(2, 1)
# Step 1: Prepare ancilla in |−⟩
qc.x(1) # |0⟩|0⟩ -> |0⟩|1⟩
qc.h(1) # |0⟩|1⟩ -> |0⟩|−⟩
qc.barrier()
# Step 2: Put input in superposition
qc.h(0) # |0⟩|−⟩ -> |+⟩|−⟩
qc.barrier()
# Step 3: Apply oracle
if oracle_type == 'constant_0':
pass # f(x) = 0 for all x: identity (do nothing)
elif oracle_type == 'constant_1':
qc.x(1) # f(x) = 1 for all x: flip ancilla, producing global phase kickback
elif oracle_type == 'balanced_id':
qc.cx(0, 1) # CNOT: f(x) = x (identity)
elif oracle_type == 'balanced_not':
qc.cx(0, 1) # CNOT
qc.x(1) # NOT: f(x) = 1-x
qc.barrier()
# Step 4: Interfere
qc.h(0)
qc.barrier()
# Step 5: Measure input qubit only
qc.measure(0, 0)
return qc
Let’s test each oracle:
simulator = AerSimulator()
for oracle in ['constant_0', 'constant_1', 'balanced_id', 'balanced_not']:
qc = deutsch_circuit(oracle)
compiled = transpile(qc, simulator)
result = simulator.run(compiled, shots=100).result()
counts = result.get_counts()
measured = '0' if '0' in counts and counts.get('0', 0) > 50 else '1'
verdict = "CONSTANT" if measured == '0' else "BALANCED"
print(f"{oracle}: measured={counts}, verdict={verdict}")
Expected output:
constant_0: measured={'0': 100}, verdict=CONSTANT
constant_1: measured={'0': 100}, verdict=CONSTANT
balanced_id: measured={'1': 100}, verdict=BALANCED
balanced_not: measured={'1': 100}, verdict=BALANCED
The measurement is deterministic; you always get the right answer in a single run. No repetition needed.
Cleaner Version of Deutsch’s Algorithm
Here is a simpler, directly correct implementation:
def deutsch_simple(is_balanced):
"""Simple correct Deutsch circuit."""
qc = QuantumCircuit(2, 1)
# Prepare: X on ancilla, H on both
qc.x(1)
qc.h([0, 1])
# Oracle
if is_balanced:
qc.cx(0, 1) # Balanced: CNOT
# Interference
qc.h(0)
# Measure
qc.measure(0, 0)
return qc
for balanced in [False, True]:
qc = deutsch_simple(balanced)
compiled = transpile(qc, simulator)
counts = simulator.run(compiled, shots=100).result().get_counts()
print(f"balanced={balanced}: {counts}")
# balanced=False: {'0': 100} (constant)
# balanced=True: {'1': 100} (balanced)
Why the Algorithm Works: The Math
After state preparation, the input qubit is in state |+⟩ = (|0⟩ + |1⟩)/√2 and the ancilla is in |−⟩ = (|0⟩ - |1⟩)/√2.
When the balanced oracle (CNOT) acts, phase kickback transfers the function’s structure to the input qubit:
Before oracle: (|0⟩ + |1⟩)/√2 ⊗ |−⟩
After CNOT oracle (balanced):
(|0⟩⊗|0⊕0⟩ + |1⟩⊗|0⊕1⟩ - |0⟩⊗|1⊕0⟩ - |1⟩⊗|1⊕1⟩) / 2
= (|0⟩|0⟩ + |1⟩|1⟩ - |0⟩|1⟩ - |1⟩|0⟩) / 2
= (|0⟩(|0⟩-|1⟩) - |1⟩(|0⟩-|1⟩)) / 2
= (|0⟩ - |1⟩)/√2 ⊗ |−⟩
= |−⟩ ⊗ |−⟩
The input qubit is now in |−⟩. Applying H to |−⟩ gives |1⟩. So you measure 1, indicating balanced.
For the constant oracle (identity), the input qubit stays in |+⟩. Applying H to |+⟩ gives |0⟩. So you measure 0, indicating constant.
The oracle’s global structure (constant vs balanced) is encoded in the input qubit’s state after phase kickback, and H converts that into a definite 0 or 1 measurement.
From Deutsch to Real Algorithms
Deutsch’s algorithm is a toy problem. No one needs to determine if a 1-bit function is constant or balanced in practice. But it is the clearest demonstration of the algorithm template:
- Deutsch-Jozsa: generalize Deutsch to n-bit functions (n queries classically, 1 quantum)
- Bernstein-Vazirani: find a hidden string (n queries classically, 1 quantum)
- Simon’s algorithm: find a hidden period (exponential queries classically, polynomial quantum)
- Grover’s algorithm: search n items (O(n) classically, O(√n) quantum)
- Shor’s algorithm: factor integers (exponential classically, polynomial quantum)
Each is a variation on the same template: superpose, oracle, interfere, measure. Learning Deutsch’s algorithm is learning the skeleton of all quantum algorithms.
Was this tutorial helpful?