DEV Community

Malcolm Low
Malcolm Low

Posted on Originally published at malcolmlow.com

The Deutsch-Jozsa Algorithm Explained: Quantum Complexity & Qiskit

#quantum #python #qiskit #algorithms

Part of the Quantum Computing: A Complete Learning Path series on malcolmlow.com. Following our earlier analyses of the single-qubit Deutsch Algorithm and Phase Kickback, this guide scales the formulation to multi-qubit registers with the Deutsch-Jozsa Algorithm.

In 1985, David Deutsch proposed the first quantum algorithm that demonstrated a computational speedup over any classical counterpart, proving that quantum mechanics could evaluate a global property of a function faster than classical boolean logic. In 1992, together with Richard Jozsa, this was generalized into the Deutsch-Jozsa Algorithm: the very first algorithm to exhibit an exponential query separation between deterministic classical computation and exact quantum computing.

While Deutsch's original prototype applied to single-bit inputs ($n=1$, yielding a factor-of-2 speedup), Deutsch-Jozsa scales to arbitrary $n$-bit registers ($n \ge 1$). In this guide, we break down the mathematical problem, detail the four canonical oracle implementations, derive how phase kickback and Hadamard interference eliminate the exponential query barrier, and demonstrate working code in modern Qiskit 2.x with circuit diagrams.

Quick Answer & Key Insight

Can the Deutsch-Jozsa algorithm determine if an arbitrary Boolean function is constant or balanced in a single evaluation?

Yes, Deutsch-Jozsa solves the promise problem in exactly 1 query ($O(1)$). Classically, a deterministic computer must evaluate $2^{n-1} + 1$ states in the worst case—an exponential barrier that becomes intractable for even moderate register sizes ($n=30$ requires over 536 million queries). Quantum interference extracts the global function property in a single shot by exploiting phase kickback and destructive interference.

1. The Problem: Constant vs. Balanced Boolean Functions

We are given a black-box oracle that computes an unknown Boolean function taking an $n$-bit string and returning a single bit:

f: {0, 1}ⁿ → {0, 1}
Enter fullscreen mode Exit fullscreen mode

We are promised that $f$ belongs strictly to one of two categories:

  • Constant: The function returns the exact same value for all possible inputs ($f(x) = 0$ for all $x$, or $f(x) = 1$ for all $x$).
  • Balanced: The function returns 0 for exactly half of the $2^n$ inputs ($2^{n-1}$ states) and 1 for the remaining half ($2^{n-1}$ states).

The Objective: Determine with 100% mathematical certainty whether $f$ is constant or balanced using the absolute minimum number of oracle evaluations.

2. Complexity Comparison: Exponential Separation

Classically, if you query the oracle with an input $x_1$ and receive $f(x_1) = 0$, you learn nothing definitive. If your next query $x_2$ yields $f(x_2) = 1$, you immediately know $f$ is balanced (best-case: 2 queries). However, in the worst-case scenario, every input you test continues to return 0.

Because a balanced function has exactly $2^{n-1}$ zeros, observing $2^{n-1}$ zeros in a row still leaves the possibility that the remaining $2^{n-1}$ inputs are all ones (balanced) or all zeros (constant). To be 100% deterministic, a classical computer must evaluate:

Classical Deterministic Queries (Worst-Case) = 2ⁿ⁻¹ + 1
Enter fullscreen mode Exit fullscreen mode

Quantum computing solves this in exactly 1 query ($O(1)$) with 100% certainty:

Input Bits ($n$) Search Space ($2^n$) Classical Deterministic ($2^{n-1}+1$) Quantum ($O(1)$) Speedup Ratio
n = 1 (Deutsch) 2 2 queries 1 query 2×
n = 3 8 5 queries 1 query 5×
n = 10 1,024 513 queries 1 query 513×
n = 30 ~1.07 × 10⁹ 536,870,913 queries 1 query > 5 × 10⁸×

3. The Mathematical Engine: Phase Kickback

To compute $f(x)$ reversibly, quantum computers use a unitary oracle $U_f$ operating on an input register $|x\rangle$ and an auxiliary target qubit $|y\rangle$:

U_f |x⟩ |y⟩ = |x⟩ |y ⊕ f(x)⟩
Enter fullscreen mode Exit fullscreen mode

Rather than preparing the target qubit in $|0\rangle$, we prepare it in the anti-symmetric superposition state $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$ using an $X$ gate followed by a Hadamard $H$:

U_f |x⟩ |-⟩ = U_f |x⟩ [ (|0⟩ - |1⟩) / √2 ]
            = [ |x⟩ |0 ⊕ f(x)⟩ - |x⟩ |1 ⊕ f(x)⟩ ] / √2

• If f(x) = 0: [ |x⟩|0⟩ - |x⟩|1⟩ ] / √2 = (+1) |x⟩ |-⟩
• If f(x) = 1: [ |x⟩|1⟩ - |x⟩|0⟩ ] / √2 = (-1) |x⟩ |-⟩
Enter fullscreen mode Exit fullscreen mode

In both cases, we can write the result compactly:

U_f |x⟩ |-⟩ = (-1)^{f(x)} |x⟩ |-⟩
Enter fullscreen mode Exit fullscreen mode

The bit $f(x)$ is not written to the target qubit at all—it is kicked back as an eigenvalue phase factor $(-1)^{f(x)}$ directly onto the input register state!

4. Implementing All 4 Types of Oracles in Qiskit

To understand how oracles are physically constructed, let us take a 3-qubit input register ($q_0, q_1, q_2$) with an auxiliary target qubit ($q_3$). Any Boolean function falls into one of four canonical implementations:

Oracle 1: Constant-0 ($f(x) = 0$ everywhere)

Because $y \oplus 0 = y$, the target qubit is left completely untouched. The circuit is an empty identity wire:

Oracle 1: Constant-0 Identity Circuit
Oracle 1: Identity wire — target qubit q3 remains unchanged.

Oracle 2: Constant-1 ($f(x) = 1$ everywhere)

Because $y \oplus 1 = \bar{y}$, the target qubit must flip unconditionally for all inputs. We apply a single NOT ($X$) gate to $q_3$:

Oracle 2: Constant-1 Inversion Circuit
Oracle 2: Unconditional X gate on q3 — imparts an unobservable global minus sign.

Oracle 3: Balanced Direct ($f(x) = x_0 \oplus x_2$)

To create a balanced function, we can compute an inner product or parity check. In this example, CNOTs are placed on $q_0$ and $q_2$ targeting $q_3$, leaving $q_1$ unattached:

Oracle 3: Balanced Direct Parity Circuit
Oracle 3: CNOT controls on q0 and q2 — evaluates f(x) = x0 ⊕ x2.

Oracle 4: Balanced Inverted ($f(x) = \neg(x_0 \oplus x_2)$)

This is the complement of Oracle 3 (inverting all outputs). We place CNOTs on $q_0$ and $q_2$, followed by an $X$ gate on target $q_3$:

Oracle 4: Balanced Inverted Circuit
Oracle 4: CNOT controls on q0 and q2 followed by NOT on q3.

Oracle Comparison Matrix

Oracle Type Logic Equation Gates on Target ($q_3$) Measurement Verdict
1. Constant-0 f(x) = 0 None (Wire) 000 (100%) CONSTANT
2. Constant-1 f(x) = 1 X 000 (100%) CONSTANT
3. Balanced Direct f(x) = x₀ ⊕ x₂ CX(q0) + CX(q2) 101 (100%) BALANCED
4. Balanced Inverted f(x) = ¬(x₀ ⊕ x₂) CX(q0) + CX(q2) + X 101 (100%) BALANCED

5. Full Circuit & Quantum Interference Derivation

Here is the complete end-to-end Deutsch-Jozsa circuit for our 3-qubit balanced function ($f(x) = x_0 \oplus x_2$):

Complete Deutsch-Jozsa Quantum Circuit
Complete Deutsch-Jozsa Circuit in Qiskit: State prep, superposition, oracle, interference Hadamards, and measurement.

The Mathematical Interference:

Before the final Hadamard transform, the input register is in the state:

$$\frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{f(x)} |x\rangle$$

Applying the Walsh-Hadamard transform $H^{\otimes n}$ maps each basis state $|x\rangle$ to $\frac{1}{\sqrt{2^n}} \sum_{z} (-1)^{x \cdot z} |z\rangle$. The total state becomes:

$$|\psi_{\text{final}}\rangle = \sum_{z} \left[ \frac{1}{2^n} \sum_{x} (-1)^{f(x) + x \cdot z} \right] |z\rangle$$

When we measure, consider the probability amplitude of measuring the all-zero state $|00\dots 0\rangle$ (where $z = 00\dots 0 \implies x \cdot z = 0$):

$$\alpha_{00\dots 0} = \frac{1}{2^n} \sum_{x \in {0, 1}^n} (-1)^{f(x)}$$

  • If $f$ is Constant: All $(-1)^{f(x)}$ have the same sign ($\pm 1$). The sum adds constructively: $\alpha_{00\dots 0} = \frac{1}{2^n} (\pm 2^n) = \pm 1$. The measurement probability is $|\pm 1|^2 = \mathbf{100\%}$. You will measure 00...0 every single time.
  • If $f$ is Balanced: Exactly $2^{n-1}$ inputs yield $+1$ and $2^{n-1}$ yield $-1$. The sum cancels out completely: $\alpha_{00\dots 0} = \frac{1}{2^n} (2^{n-1} - 2^{n-1}) = \mathbf{0}$. The probability of measuring all zeros is strictly 0%! Any non-zero bitstring confirms $f$ is balanced.

6. Complete Qiskit 2.x Python Implementation

The script below builds, executes, and verifies all 4 oracles using modern Qiskit 2.x primitives (StatevectorSampler):

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

def create_oracle(oracle_type: str) -> QuantumCircuit:
    """Builds one of the 4 canonical oracles on 4 qubits (q0, q1, q2 input; q3 target)."""
    oracle = QuantumCircuit(4, name=oracle_type)

    if oracle_type == "constant_0":
        # Type 1: f(x) = 0 (Identity wire)
        pass
    elif oracle_type == "constant_1":
        # Type 2: f(x) = 1 (Unconditional target flip)
        oracle.x(3)
    elif oracle_type == "balanced_direct":
        # Type 3: f(x) = x0 ^ x2 (CNOT parity on q0 and q2)
        oracle.cx(0, 3)
        oracle.cx(2, 3)
    elif oracle_type == "balanced_inverted":
        # Type 4: f(x) = ~(x0 ^ x2) (CNOT parity + NOT gate)
        oracle.cx(0, 3)
        oracle.cx(2, 3)
        oracle.x(3)
    else:
        raise ValueError(f"Unknown oracle type: {oracle_type}")

    return oracle

def run_deutsch_jozsa(oracle_circuit: QuantumCircuit):
    """Wraps an oracle inside the full Deutsch-Jozsa algorithm and measures."""
    qc = QuantumCircuit(4, 3)

    # 1. State preparation: target qubit to |->
    qc.x(3)
    qc.h(range(4))
    qc.barrier()

    # 2. Insert the oracle
    qc.compose(oracle_circuit, inplace=True)
    qc.barrier()

    # 3. Interference decoding
    qc.h(range(3))

    # 4. Measure input register
    qc.measure([0, 1, 2], [0, 1, 2])

    # Execute on StatevectorSampler
    sampler = StatevectorSampler()
    result = sampler.run([qc], shots=100).result()
    counts = result[0].data.c.get_counts()
    verdict = "CONSTANT" if list(counts.keys()) == ['000'] else "BALANCED"

    return qc, counts, verdict

# Execute and compare all 4 canonical oracles
oracles = ["constant_0", "constant_1", "balanced_direct", "balanced_inverted"]

print(f"{'Oracle Type':<20} | {'Measurement':<12} | {'Decision':<10}")
print("-" * 50)
for o_name in oracles:
    oracle_qc = create_oracle(o_name)
    full_qc, counts, verdict = run_deutsch_jozsa(oracle_qc)
    print(f"{o_name:<20} | {str(counts):<12} | {verdict:<10}")
Enter fullscreen mode Exit fullscreen mode

Execution Output: 

Oracle Type          | Measurement  | Decision  
--------------------------------------------------
constant_0           | {'000': 100} | CONSTANT  
constant_1           | {'000': 100} | CONSTANT  
balanced_direct      | {'101': 100} | BALANCED  
balanced_inverted    | {'101': 100} | BALANCED
Enter fullscreen mode Exit fullscreen mode

7. Key Insights & Takeaways

  1. Global Property vs. Local Evaluation: The algorithm never tells you which inputs produce 0 or 1. It extracts only the collective structural property (constant vs. balanced) by harnessing destructive interference.
  2. Phase Kickback Converts Values to Geometry: Setting the ancilla to $|-\rangle$ turns modular arithmetic ($y \oplus f(x)$) into spatial eigenvalue phase shifts ($(-1)^{f(x)}$).
  3. The Stepping Stone to Modern Quantum Algorithms: Deutsch-Jozsa laid the direct mathematical groundwork for the Bernstein-Vazirani algorithm (finding the hidden bitstring $s$), Simon’s algorithm, and ultimately Shor’s algorithm for integer factorization.

Frequently Asked Questions

Why does classical computing require 2^(n-1) + 1 evaluations for Deutsch-Jozsa?

In the worst-case scenario, a balanced function might return the same value (e.g., 0) for the first $2^{n-1}$ inputs tested. Only on the $(2^{n-1} + 1)$-th query can a classical deterministic algorithm guarantee whether the remaining values are identical (constant) or inverted (balanced).

How does the Deutsch-Jozsa algorithm achieve 100% determinism?

Through quantum phase kickback and Hadamard interference, all balanced states produce completely destructive interference at the $|00\dots 0\rangle$ basis state (amplitude = 0), while constant states produce completely constructive interference (amplitude = 1). Thus, observing all zeros confirms constant, while any non-zero measurement confirms balanced in a single shot.

Originally published at malcolmlow.com.

Top comments (0)