First time studying this topic?

Launch the interactive walkthrough to discover each component, including the 3D Q-Sphere Lab & Python in Colab.

Topic 7.3

The Deutsch-Jozsa Algorithm: First Proof of Quantum Speedup

Master the historic algorithm that first proved an exponential separation between classical and quantum computing.

Learning Objectives

✓Define Constant vs Balanced Boolean functions
✓Examine the classical complexity barrier: 2^(n-1) + 1 queries in worst-case
✓Trace the Deutsch-Jozsa circuit: solving the problem in EXACTLY ONE quantum query

📖Let's Begin with a Story

In 1992, David Deutsch and Richard Jozsa designed a mathematical puzzle specifically engineered to demonstrate that quantum computers are fundamentally more powerful than classical computers. Imagine a black-box function

f(x)

that accepts an

n

-bit binary string and outputs 0 or 1. You are promised that the function is either: 1. Constant: It outputs the exact same answer (all 0s, or all 1s) for every single input. 2. Balanced: It outputs 0 for exactly half of all inputs, and 1 for the other half. Your mission: find out whether the function is Constant or Balanced. On a classical computer, you check

f(000)

f(001)

f(010)

... In the worst case, you must check more than half of all inputs:

2^{n-1} + 1 \text{ queries!}

For

n = 30

, that is over 500 million queries! Deutsch and Jozsa proved that a quantum computer can determine the answer with 100% certainty in EXACTLY ONE QUERY!

Why Should You Learn The Deutsch-Jozsa Algorithm: First Proof of Quantum Speedup?

🎯 Practical & Engineering Stakes

The historic proof of quantum advantage

Deutsch-Jozsa was the first deterministic quantum algorithm to achieve an exponential separation over classical deterministic Turing machines, inspiring Shor and Grover.

What Is It?

Simple Explanation

The Deutsch-Jozsa test: Is a coin two-headed/two-tailed (Constant) or does it have one Head and one Tail (Balanced)? - Classical: You might have to flip the coin hundreds of times. - Quantum: You send the coin through a quantum circuit once. - If measurement yields 00...0, the function is CONSTANT. - If measurement yields ANY OTHER NUMBER, the function is BALANCED! Solved in a single shot!

Technical Explanation

Deutsch-Jozsa evaluates

f: \{0, 1\}^n \rightarrow \{0, 1\}

promised to be constant or balanced. Classical deterministic query complexity is

\Omega(2^{n-1}+1)

. The quantum circuit applies

H^{\otimes n}

|0\rangle^{\otimes n}

, queries oracle

U_f

with ancilla

|-\rangle

, and applies

H^{\otimes n}

to the input register. The final state amplitude of

|0\rangle^{\otimes n}

\frac{1}{2^n} \sum_{x} (-1)^{f(x)}

. For constant

f

, this equals

\pm 1

(

P(|0\rangle^{\otimes n}) = 1

); for balanced

f

, the terms cancel to 0 (

P(|0\rangle^{\otimes n}) = 0

). Exact complexity:

\mathcal{O}(1)

quantum query.

📚 Key Terms

Constant Function

Simple: A function that outputs the exact same answer (all 0s or all 1s) for every single input.

Technical: A function where

f(x) = c \in \{0, 1\}

for all

x \in \{0, 1\}^n

Balanced Function

Simple: A function that outputs 0 for exactly 50% of inputs, and 1 for the other 50%.

Technical: A function where

|\{x : f(x) = 0\}| = |\{x : f(x) = 1\}| = 2^{n-1}

Q-Sphere Lab: The Deutsch-Jozsa Algorithm: First Proof of Quantum Speedup

IBM Q-Sphere Model

Interactive 3D state vector exploration, unitary transformation gates, and Born rule collapse for Topic 7.3

Azimuth: 45°Elevation: 25°(Click & drag sphere to orbit)

Q-Sphere Phase Color:

0 π/2 π 3π/2

Quantum Statevector

dim(H) = 2

|ψ⟩ = (1.000 + 0.000i)|0⟩
+ (0.000 + 0.000i)|1⟩

Polar Angle (θ):0.0° (0.000π rad)

Phase Angle (ϕ):0.0° (0.000π rad)

Born Rule Probabilities: P(x) = |⟨x|ψ⟩|²Σ P = 1.00

P(|0⟩) = |α|²100.0%

P(|1⟩) = |β|²0.0%

Quantum Measurement

Apply Single-Qubit Unitary Gates

Presets:

Continuous Polar Angle θ (0° = |0⟩, 180° = |1⟩):0.0°

Continuous Phase Angle ϕ (0° to 360°):0.0°

Recent Operations Log:

#1Initial state: |0⟩

📐 Mathematical Foundation

LaTeX KaTeX

|\psi_{\text{final}}\rangle = \sum_{z=0}^{2^n-1} \left( \frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x) + x \cdot z} \right) |z\rangle, \quad P(|00\dots0\rangle) = \left| \frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \right|^2

What does it mean?

The Deutsch-Jozsa Global Property Equation: Determines with 100% certainty whether an n-qubit function f(x) is Constant (outputs the same bit for all inputs) or Balanced (outputs 0 for half and 1 for the other half) in a SINGLE query! Measuring the all-zero state

|00...0\rangle

yields 100% if constant, and exactly 0% if balanced.

Understanding the Symbols

Symbol / Term	Meaning	Beginner Interpretation
$x$	Input query bitstring	Runs across all $2^n$ possible inputs simultaneously
$z$	Output measurement state	Measured bitstring after applying final Hadamard interference gates
$x \cdot z$	Bitwise dot product	Modulo-2 sum of matching bits ( $x_1 z_1 \oplus \dots \oplus x_n z_n$ )
$P(\|00\dots0\rangle)$	All-zero outcome probability	1.0 (100%) if f is Constant; exactly 0.0 (0%) if f is Balanced

📊 Numerical Example

Running Deutsch-Jozsa on a 2-qubit balanced function with 4 inputs where f(00)=0, f(01)=0, f(10)=1, f(11)=1:

Inputs: 2 qubits → 2^2 = 4 inputs (N = 4) Classical requirement: Must check N/2 + 1 = 3 inputs in worst-case. Quantum calculation of amplitude for

|00\rangle

: Amplitude = (1/4) × [ (-1)^{f(00)} + (-1)^{f(01)} + (-1)^{f(10)} + (-1)^{f(11)} ] = (1/4) × [ (-1)^0 + (-1)^0 + (-1)^1 + (-1)^1 ] = (1/4) × [ (+1) + (+1) + (-1) + (-1) ] = (1/4) × [ 0 ] = 0.0 Measurement probability of

|00\rangle

: P(

|00\rangle

) = |0.0|^2 = 0.00 (0% chance!)

Result: Because P( $|00\rangle$ ) = 0, we measure a non-zero state and conclude the function is Balanced with 100% certainty in ONE single query!

⚙️ How Does It Work?

Register Initialization

Initialize n input qubits to |0> and 1 target ancilla to |1>.

Hadamard Wall

Apply Hadamard to all n+1 qubits, setting target to |->.

Single Oracle Query

Pass through U_f; phase kickback writes (-1)^f(x) onto input superposition.

Final Hadamard & Measurement

Apply Hadamard to all n input qubits. If measurement is 00...0, output CONSTANT; otherwise output BALANCED.

🌍 Where Is It Used?

Global Function Property Testing

Problem: Determining global structural symmetries of massive cryptographic black boxes.

Solution: Deutsch-Jozsa proves exponential speedup for global property testing over local evaluation.

🎯 Try It Yourself

In the Deutsch-Jozsa algorithm on 4 qubits, the final measurement returns "0000". What does this prove about the function f(x)?

Interactive activity component

🐍 Python Hands-On: Implementing the Full Deutsch-Jozsa Algorithm in Qiskit

Construct the full Deutsch-Jozsa algorithm for a 3-qubit input register and determine whether a function is constant or balanced in 1 query.

Open Colab

1Install Required Packages

For Google Colab or Jupyter notebooks, run this shell command to install the required dependencies:

Terminal / Notebook Install Commandbash

!pip install qiskit qiskit-aer

Packages:

qiskitqiskit-aer

2Import Libraries

Import Statementspython

1 from qiskit import QuantumCircuit
2 from qiskit_aer import AerSimulator

from qiskit import QuantumCircuit → Circuit module

from qiskit_aer import AerSimulator → Simulator module

3Demonstration Code & Logic

Python Execution Codepython

1 # 3 input qubits + 1 ancilla qubit = 4 qubits total
2 n = 3
3 dj_circuit = QuantumCircuit(n + 1, n)
4  
5 # Step 1: Initialize ancilla to |1> and apply Hadamards to all qubits
6 dj_circuit.x(n)       # Ancilla to |1>
7 dj_circuit.h(range(n + 1))  # All qubits to superposition
8 dj_circuit.barrier()
9  
10 # Step 2: Balanced Oracle (f(x) = x0 XOR x1 XOR x2)
11 for q in range(n):
12     dj_circuit.cx(q, n)  # XOR into ancilla
13 dj_circuit.barrier()
14  
15 # Step 3: Interference on input qubits
16 dj_circuit.h(range(n))
17 dj_circuit.measure(range(n), range(n))
18 print('Deutsch-Jozsa Circuit Diagram:')
19 print(dj_circuit.draw('text'))
20  
21 # Simulate with AerSimulator
22 sim = AerSimulator()
23 counts = sim.run(dj_circuit, shots=1000).result().get_counts()
24 print('\nMeasurement Result (1000 shots):', counts)
25 measured_bitstring = list(counts.keys())[0]
26 if measured_bitstring == '0' * n:
27     print('Verdict: Function is CONSTANT (measured 000)')
28 else:
29     print(f'Verdict: Function is BALANCED (measured {measured_bitstring} != 000) in 1 query!')

Step-by-Step Code Breakdown:

# 3 input qubits + 1 ancilla qubit = 4 qubits total

Setup

n = 3

Input size

dj_circuit = QuantumCircuit(n + 1, n)

Circuit with 4 qubits and 3 classical bits

# Step 1: Initialize ancilla to |1> and apply Hadamards to all qubits

Init

dj_circuit.x(n) # Ancilla to |1>

Ancilla flip

dj_circuit.h(range(n + 1)) # All qubits to superposition

H on all wires

dj_circuit.barrier()

Visual barrier

# Step 2: Balanced Oracle (f(x) = x0 XOR x1 XOR x2)

Balanced oracle

for q in range(n):

Attach CNOTs

dj_circuit.cx(q, n) # XOR into ancilla

CNOT from each input

dj_circuit.barrier()

Visual barrier

# Step 3: Interference on input qubits

Interference

dj_circuit.h(range(n))

H on input register

dj_circuit.measure(range(n), range(n))

Measure input qubits

print('Deutsch-Jozsa Circuit Diagram:')

Diagram label

print(dj_circuit.draw('text'))

Print circuit

# Simulate with AerSimulator

Simulation

sim = AerSimulator()

Backend

counts = sim.run(dj_circuit, shots=1000).result().get_counts()

Run 1000 shots

print('\nMeasurement Result (1000 shots):', counts)

Print counts

measured_bitstring = list(counts.keys())[0]

Extract measured bitstring

if measured_bitstring == '0' * n:

Check constant

print('Verdict: Function is CONSTANT (measured 000)')

Constant

else:

Check balanced

print(f'Verdict: Function is BALANCED (measured {measured_bitstring} != 000) in 1 query!')

Balanced

📋 Complete Script (All-in-One)

Click "Copy for Colab", open Google Colab, paste into a single cell, and run.

Google Colab Notebook Scriptpython

1 # =========================================================
2 # Implementing the Full Deutsch-Jozsa Algorithm in Qiskit
3 # Prepared for Google Colab (Run with Shift + Enter)
4 # =========================================================
5  
6 # Step 1: Install required packages
7 !pip install qiskit qiskit-aer
8  
9 # Step 2: Import libraries
10 from qiskit import QuantumCircuit
11 from qiskit_aer import AerSimulator
12  
13 # Step 3: Run Demonstration
14 # 3 input qubits + 1 ancilla qubit = 4 qubits total
15 n = 3
16 dj_circuit = QuantumCircuit(n + 1, n)
17  
18 # Step 1: Initialize ancilla to |1> and apply Hadamards to all qubits
19 dj_circuit.x(n)       # Ancilla to |1>
20 dj_circuit.h(range(n + 1))  # All qubits to superposition
21 dj_circuit.barrier()
22  
23 # Step 2: Balanced Oracle (f(x) = x0 XOR x1 XOR x2)
24 for q in range(n):
25     dj_circuit.cx(q, n)  # XOR into ancilla
26 dj_circuit.barrier()
27  
28 # Step 3: Interference on input qubits
29 dj_circuit.h(range(n))
30 dj_circuit.measure(range(n), range(n))
31 print('Deutsch-Jozsa Circuit Diagram:')
32 print(dj_circuit.draw('text'))
33  
34 # Simulate with AerSimulator
35 sim = AerSimulator()
36 counts = sim.run(dj_circuit, shots=1000).result().get_counts()
37 print('\nMeasurement Result (1000 shots):', counts)
38 measured_bitstring = list(counts.keys())[0]
39 if measured_bitstring == '0' * n:
40     print('Verdict: Function is CONSTANT (measured 000)')
41 else:
42     print(f'Verdict: Function is BALANCED (measured {measured_bitstring} != 000) in 1 query!')

⚡ How to Run in Google Colab (3 Quick Steps)

Click "Copy for Google Colab" above.
Click Open New Google Colab Notebook (opens in a new tab).
Click on the first empty code cell, press Ctrl + V (or Cmd + V) to paste, then press Shift + Enter to execute!

Launch Blank Colab Notebook

🔄 Algorithmic Execution Flow

Prepare Superposition & Ancilla

Place 3 input qubits into |+> and ancilla qubit into |->.

→

Query Balanced Oracle

Apply CNOT from each input qubit to the ancilla, kicking back negative phases.

→

Apply Final Hadamards & Measure

Destructive interference cancels '000', resulting in 100% detection of balanced function in 1 step vs 2^(n-1)+1 classical queries.

📥 Input / Initial State

Deutsch-Jozsa circuit with 3 input qubits and balanced parity oracle.

📤 Expected Output

Measurement counts: {'111': 1000}
Verdict: Function is BALANCED in 1 query (Classically requires 5 queries).

💡 What Does This Demonstration Show?

Classically, proving a 3-input function is balanced requires testing 5 inputs in the worst case (2^(n-1)+1). Deutsch-Jozsa solves it in exactly ONE quantum query with zero error, establishing definitive quantum speedup.

Course Learning Resource • Slide DeckLesson 910 Slides

Lesson 9: Grover Search and Amplitude Amplification

Oracle, diffusion operator, interference, and quadratic search speedup.

Author: Dr. Syed Muzamil Basha• FDP Approved Curriculum

Open in New Tab

📝 Learning Check

Test your understanding with these questions. Remember, this is for learning, not examination!

Question 1: How many oracle queries does a classical deterministic computer require in the worst case to determine if an n-bit function is constant or balanced?

Question 2: What problem does Deutsch-Jozsa algorithm solve?

Question 3: What is the Deutsch-Jozsa circuit structure?

Question 4: What is a quantum oracle?

Question 5: Is Deutsch-Jozsa practical for real-world problems?

Previous: Quantum Parallelism & The Quantum Oracle Next: Grover’s Search Algorithm: Quadratic Speedup

1	from qiskit import QuantumCircuit
2	from qiskit_aer import AerSimulator

1	# =========================================================
2	# Implementing the Full Deutsch-Jozsa Algorithm in Qiskit
3	# Prepared for Google Colab (Run with Shift + Enter)
4	# =========================================================
5
6	# Step 1: Install required packages
7	!pip install qiskit qiskit-aer
8
9	# Step 2: Import libraries
10	from qiskit import QuantumCircuit
11	from qiskit_aer import AerSimulator
12
13	# Step 3: Run Demonstration
14	# 3 input qubits + 1 ancilla qubit = 4 qubits total
15	n = 3
16	dj_circuit = QuantumCircuit(n + 1, n)
17
18	# Step 1: Initialize ancilla to \|1> and apply Hadamards to all qubits
19	dj_circuit.x(n) # Ancilla to \|1>
20	dj_circuit.h(range(n + 1)) # All qubits to superposition
21	dj_circuit.barrier()
22
23	# Step 2: Balanced Oracle (f(x) = x0 XOR x1 XOR x2)
24	for q in range(n):
25	dj_circuit.cx(q, n) # XOR into ancilla
26	dj_circuit.barrier()
27
28	# Step 3: Interference on input qubits
29	dj_circuit.h(range(n))
30	dj_circuit.measure(range(n), range(n))
31	print('Deutsch-Jozsa Circuit Diagram:')
32	print(dj_circuit.draw('text'))
33
34	# Simulate with AerSimulator
35	sim = AerSimulator()
36	counts = sim.run(dj_circuit, shots=1000).result().get_counts()
37	print('\nMeasurement Result (1000 shots):', counts)
38	measured_bitstring = list(counts.keys())[0]
39	if measured_bitstring == '0' * n:
40	print('Verdict: Function is CONSTANT (measured 000)')
41	else:
42	print(f'Verdict: Function is BALANCED (measured {measured_bitstring} != 000) in 1 query!')