In the previous post on the Deutsch algorithm, we covered the theory. Here we implement both the classical and quantum approaches in Qiskit so the quantum advantage is visible in working code: the same problem solved with fewer oracle queries than any classical method can manage.
The Challenge
Given a black-box function f: {0,1} → {0,1}, determine whether it is:
- Constant: f(0) = f(1) (always returns 0, or always returns 1)
- Balanced: f(0) ≠ f(1) (returns 0 for one input, 1 for the other)
The whole question is how many times you must query the function:
| Approach | Queries required |
|---|---|
| Classical | 2 |
| Quantum | 1 |
Complete Qiskit Implementation
Oracle functions
First, build the oracle functions representing all possible single-bit Boolean functions:
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
def create_constant_oracle(constant_value):
"""Creates a constant oracle (returns 0 or 1 for all inputs)"""
oracle = QuantumCircuit(2, name=f"Constant_{constant_value}")
if constant_value == 1:
oracle.x(1) # Flip the output qubit
return oracle
def create_balanced_oracle(balance_type):
"""Creates a balanced oracle"""
oracle = QuantumCircuit(2, name=f"Balanced_{balance_type}")
if balance_type == 'identity':
# f(x) = x
oracle.cx(0, 1)
elif balance_type == 'negation':
# f(x) = NOT x
oracle.x(0)
oracle.cx(0, 1)
oracle.x(0)
return oracle
Classical approach: two queries required
The classical algorithm must query the oracle twice, once for f(0) and once for f(1):
def classical_deutsch_query1(oracle):
"""First query: Evaluate f(0)"""
qr = QuantumRegister(2, 'q')
cr = ClassicalRegister(1, 'c')
qc = QuantumCircuit(qr, cr)
# Input: x = 0 (already initialized to |0>)
qc.barrier()
qc.compose(oracle, inplace=True)
qc.barrier()
qc.measure(1, 0) # Measure output to get f(0)
return qc
def classical_deutsch_query2(oracle):
"""Second query: Evaluate f(1)"""
qr = QuantumRegister(2, 'q')
cr = ClassicalRegister(1, 'c')
qc = QuantumCircuit(qr, cr)
qc.x(0) # Input: x = 1
qc.barrier()
qc.compose(oracle, inplace=True)
qc.barrier()
qc.measure(1, 0) # Measure output to get f(1)
return qc
Quantum approach: one query suffices
The quantum Deutsch algorithm uses superposition and interference to answer with a single oracle query:
def deutsch_algorithm(oracle):
"""Implements the Deutsch algorithm - requires only ONE query"""
qr = QuantumRegister(2, 'q')
cr = ClassicalRegister(1, 'c')
qc = QuantumCircuit(qr, cr)
# Step 1: Initialize q[1] to |1>
qc.x(1)
qc.barrier()
# Step 2: Apply Hadamard gates (create superposition)
qc.h(0)
qc.h(1)
qc.barrier()
# Step 3: Apply the oracle (SINGLE QUERY!)
qc.compose(oracle, inplace=True)
qc.barrier()
# Step 4: Apply Hadamard to input qubit
qc.h(0)
qc.barrier()
# Step 5: Measure
qc.measure(0, 0)
return qc
Running the comparison
Now test all four possible oracles with both approaches:
oracles = [
("Constant 0", create_constant_oracle(0)),
("Constant 1", create_constant_oracle(1)),
("Balanced (Identity)", create_balanced_oracle('identity')),
("Balanced (Negation)", create_balanced_oracle('negation'))
]
simulator = AerSimulator()
for name, oracle in oracles:
# Classical: 2 queries
qc1 = classical_deutsch_query1(oracle)
result1 = simulator.run(qc1, shots=1).result()
f_0 = int(list(result1.get_counts().keys())[0])
qc2 = classical_deutsch_query2(oracle)
result2 = simulator.run(qc2, shots=1).result()
f_1 = int(list(result2.get_counts().keys())[0])
classical_result = "CONSTANT" if f_0 == f_1 else "BALANCED"
# Quantum: 1 query
qc_quantum = deutsch_algorithm(oracle)
result_quantum = simulator.run(qc_quantum, shots=1000).result()
counts = result_quantum.get_counts()
quantum_result = "CONSTANT" if '0' in counts else "BALANCED"
print(f"{name}: Classical={classical_result}, Quantum={quantum_result}")
Circuit Diagrams
The full figures are rendered in the original post; the structure of each is:
- Classical Query 1, f(0): q[0] stays in |0⟩, the oracle processes the input, and q[1] is measured to read f(0).
- Classical Query 2, f(1): an X gate flips q[0] to |1⟩, the oracle processes it, and q[1] is measured to read f(1).
- Quantum Deutsch (single query): initialise |01⟩, Hadamards on both wires create superposition, a single oracle query, a final Hadamard on q[0], then measure q[0].
The key structural difference: the classical circuits measure the output qubit q[1] to read function values, while the quantum circuit measures the input qubit q[0] after interference. That is what lets a single query reveal a global property of the function.
Sample Output
======================================================================
Testing: Constant 0 Oracle
======================================================================
[CLASSICAL APPROACH - Requires 2 queries]
Query 1: f(0) = 0
Query 2: f(1) = 0
Result: Function is CONSTANT
Total queries needed: 2
[QUANTUM APPROACH - Requires only 1 query]
Measurement results: {'0': 1000}
Result: Function is CONSTANT
Total queries needed: 1
Both methods agree: True
======================================================================
Testing: Balanced (Identity) Oracle
======================================================================
[CLASSICAL APPROACH - Requires 2 queries]
Query 1: f(0) = 0
Query 2: f(1) = 1
Result: Function is BALANCED
Total queries needed: 2
[QUANTUM APPROACH - Requires only 1 query]
Measurement results: {'1': 1000}
Result: Function is BALANCED
Total queries needed: 1
Both methods agree: True
Understanding the Quantum Advantage
Classical approach: evaluate f(0), evaluate f(1), compare the two results. Two queries required; you must check both inputs individually.
Quantum approach: query with a superposition of both inputs, use interference to extract the global property, then measure. One query required; it exploits quantum parallelism.
The quantum algorithm queries the oracle with a superposition of both inputs simultaneously (|0⟩ + |1⟩), then uses interference to extract a global property of the function without evaluating it on individual inputs. The single measurement directly tells you whether the function is constant or balanced.
Measurement Interpretation
| Measurement | Function type | Explanation |
|---|---|---|
| |0⟩ | Constant | Constructive interference, f(0) ⊕ f(1) = 0 |
| |1⟩ | Balanced | Destructive interference, f(0) ⊕ f(1) = 1 |
Running the Code
Install Qiskit and Aer:
pip install qiskit qiskit-aer
Then run the comparison script; it outputs the result for all four oracle types.
Conclusion
This implementation shows the Deutsch advantage concretely: a 2x reduction in oracle queries (from 2 to 1), the first algorithm to demonstrate quantum advantage over classical, and a foundational technique introducing superposition, interference, and phase kickback. The speedup is modest for this toy problem, but the same idea (query with superposition, extract a global property through interference) scales up to Deutsch-Jozsa, Simon's algorithm, and Shor's factoring.
Part of the Quantum Series 2026. Originally published on Techucation.
