DEV Community

Malcolm Low
Malcolm Low

Posted on • Originally published at malcolmlow.com

Deutsch Algorithm Revisited: Quantum vs Classical Implementation in Qiskit

#quantum #qiskit #python #algorithms

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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}")
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)