Introduction

In the previous post on the Deutsch algorithm, we explored the theoretical foundations of this groundbreaking quantum algorithm. Today, we’re taking it further by implementing both the quantum and classical approaches in Qiskit, allowing us to see the quantum advantage in action.

This hands-on implementation demonstrates why the Deutsch algorithm is considered the first example of quantum computational superiority—solving a problem with fewer oracle queries than any classical algorithm can achieve.

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)

Complete Qiskit Implementation

Oracle Functions

First, we create 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 determine the 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 let’s 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

Below are visual representations of the three circuit implementations. The classical approach requires two separate queries, while the quantum approach accomplishes the same task with a single query.

Classical Query 1: Evaluating f(0)

Classical Query 2: Evaluating f(1)

Quantum Deutsch Algorithm (Single Query)

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

Measurement Interpretation

Running the Code

To run this code yourself, you’ll need to install Qiskit:

pip install qiskit qiskit-aer

The complete code is available as a Python script that you can run directly. It will output the comparison for all four oracle types and display the results.

Conclusion

This implementation demonstrates the Deutsch algorithm’s quantum advantage in concrete terms:

• Quantum speedup: 2x reduction in oracle queries (from 2 to 1)
• First proof of concept: First algorithm to show quantum advantage over classical
• Foundational technique: Introduces key quantum concepts (superposition, interference, phase kickback)

While the speedup may seem modest for this toy problem, the techniques demonstrated here—querying a function with superposition and extracting global properties through interference—scale to more complex algorithms like Deutsch-Jozsa, Simon’s algorithm, and ultimately Shor’s algorithm for factoring.