Deutsch-Jozsa & Bernstein-Vazirani

The first quantum speedups

The Deutsch-Jozsa and Bernstein-Vazirani algorithms were among the first to demonstrate quantum speedup. Though their practical applications are limited, they beautifully illustrate the power of quantum parallelism and interference.

Deutsch-Jozsa Algorithm

Given a function f: {0,1}ⁿ → {0,1} that is promised to be either constant (same output for all inputs) or balanced (outputs 0 for half the inputs, 1 for the other half), determine which it is.

Classically, you might need up to 2ⁿ⁻¹ + 1 queries in the worst case. The quantum algorithm solves it in a single query.

f \text{ is constant OR balanced}

Problem promise

\text{Classical: } O(2^n) \text{ queries} \quad \text{Quantum: } 1 \text{ query}

Quantum speedup

Bernstein-Vazirani Algorithm

Given a function f(x) = s · x (mod 2) where s is a hidden n-bit string, determine s. Classically, this requires n queries. The quantum algorithm finds s in a single query.

This algorithm demonstrates phase kickback: the hidden string is encoded into the phases of a superposition, then extracted via interference.

f(x) = s \cdot x = s_1 x_1 \oplus s_2 x_2 \oplus \cdots \oplus s_n x_n

Function

\text{Classical: } n \text{ queries} \quad \text{Quantum: } 1 \text{ query}

Speedup

Key Insights

Both algorithms illustrate two core quantum computing techniques: quantum parallelism (evaluating the function on all inputs at once) and interference (amplifying the answer while canceling wrong paths).

While these algorithms are primarily of theoretical interest, they are excellent pedagogical tools for understanding how quantum computers work.

•Quantum parallelism: Evaluate the function on a superposition of all inputs simultaneously.
•Phase kickback: Encode the answer into the phase of a superposition.
•Interference: Use Hadamard gates to convert phase information into measurable amplitude differences.

Try It Yourself

Run this code in your own environment to experiment with the concepts.

PennyLane: Bernstein-Vazirani

Find a hidden bitstring in one query.

bernstein_vazirani.py

import pennylane as qml
from pennylane import numpy as np

n = 4
dev = qml.device('default.qubit', wires=n+1)

@qml.qnode(dev)
def bernstein_vazirani(s_bits):
    # Initialize ancilla to |1>
    qml.PauliX(wires=n)
    # Apply Hadamard to all qubits
    for i in range(n+1):
        qml.Hadamard(wires=i)
    # Oracle: apply CNOT for each bit of s that is 1
    for i, bit in enumerate(s_bits):
        if bit == 1:
            qml.CNOT(wires=[i, n])
    # Apply Hadamard again
    for i in range(n):
        qml.Hadamard(wires=i)
    return qml.sample(wires=range(n))

s = [1, 0, 1, 1]
result = bernstein_vazirani(s)
print(f'Hidden string: {result}')

Self-Check Quiz

1. How many queries does Deutsch-Jozsa need classically in the worst case?

2. What technique does Bernstein-Vazirani use to encode the hidden string?

3. How many queries does Bernstein-Vazirani need quantumly?

The Algorithm Landscape

Grover's Search Algorithm

import pennylane as qml from pennylane import numpy as np n = 4 dev = qml.device('default.qubit', wires=n+1) @qml.qnode(dev) def bernstein_vazirani(s_bits): # Initialize ancilla to |1> qml.PauliX(wires=n) # Apply Hadamard to all qubits for i in range(n+1): qml.Hadamard(wires=i) # Oracle: apply CNOT for each bit of s that is 1 for i, bit in enumerate(s_bits): if bit == 1: qml.CNOT(wires=[i, n]) # Apply Hadamard again for i in range(n): qml.Hadamard(wires=i) return qml.sample(wires=range(n)) s = [1, 0, 1, 1] result = bernstein_vazirani(s) print(f'Hidden string: {result}')