Deutsch Algorithm Revisited: Quantum vs Classical Implementation in Qiskit

Given a black-box function f: {0,1} → {0,1}, determine whether it is constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)).

First we build the four oracle circuits. Each implements one of the four single-bit Boolean functions as a reversible quantum gate. The constant oracles ignore x; the balanced oracles use x as a control.

The classical algorithm calls the oracle twice: once with input 0 to learn f(0), and once with input 1 to learn f(1). Each query is a separate circuit run.

The quantum circuit initialises q[1] = |1⟩, applies Hadamard gates to both wires, queries the oracle exactly once, then applies a final Hadamard to q[0] before measuring it. The oracle is never called again.

The quantum circuit measures q[0], the input qubit. The classical circuits measure q[1], the output qubit. That structural difference is the entire quantum advantage: the quantum algorithm reads a global property of the function via interference, not an individual function value.

Test all four oracles with both approaches and compare query counts.

Sample output:

Classical Query 1 — Evaluate f(0)
q[0] stays in |0⟩, both wires pass through U_f, and q[1] is measured to read f(0).

Classical Query 2 — Evaluate f(1)
An X gate flips q[0] to |1⟩, both wires pass through U_f, and q[1] is measured to read f(1).

Quantum Deutsch — Single Query
H gates create superposition on both wires, one oracle query encodes f(0) ⊕ f(1) as a phase, the final H on q[0] converts phase to amplitude, and measuring q[0] gives the answer directly.

The measurement result on q[0] maps directly to the function type:

The quantum speedup is 2x here (one query instead of two). Modest for a two-input function, but the same technique scales: Deutsch-Jozsa extends this to n-bit functions, cutting 2ⁿ⁻¹+1 classical queries down to one. Simon’s algorithm extends it further. Shor’s algorithm for factoring, the most consequential quantum algorithm known, relies on the same architectural idea: query in superposition, encode information as phase, extract via interference and measurement.

What’s the difference between the classical and quantum implementation of Deutsch’s algorithm in Qiskit?

The classical version calls the oracle twice, once for each input, and measures the output qubit q[1] directly. The quantum version calls the oracle once, using superposition and phase kickback, then measures the input qubit q[0] after a final Hadamard to read a global property of the function.

Why does the quantum circuit measure q[0] instead of q[1]?

q[1] holds the output qubit and is never measured in the quantum version. The oracle imprints f(0) ⊕ f(1) onto q[0] as a phase via kickback; the final Hadamard on q[0] converts that phase into a measurable amplitude, so q[0] is where the answer ends up.

Is Deutsch’s algorithm useful in practice?

Not directly — a single-bit oracle problem has no real-world use case. Its value is pedagogical and architectural: the same query-in-superposition, encode-as-phase, extract-via-interference pattern scales up to Deutsch-Jozsa, Simon’s algorithm, and ultimately Shor’s factoring algorithm.

How many oracle queries does Deutsch’s algorithm save?

One query instead of two — a 2x reduction for this two-input case. The saving compounds for larger functions: Deutsch-Jozsa reduces 2ⁿ⁻¹+1 classical queries to a single quantum query for an n-bit function.