Bernstein-Vazirani Algorithm

What You'll Learn: How to extract a hidden bit string from a black-box function using a single quantum query — reducing n classical queries to just one, using the same phase kickback trick as Deutsch-Jozsa.

Level: Beginner | Time: 15 minutes | Qubits: 4 | Framework: Qiskit

Prerequisites: Deutsch-Jozsa

The Idea

You're given a black box that computes f(x) = s·x (mod 2) — the bitwise dot product of your input x with a secret string s. Your goal: figure out what s is.

Classically, you'd query the oracle n times, once with each standard basis vector (100...0, 010...0, ..., 000...1), and each query reveals one bit of s. With n = 1000, that's 1000 queries.

The Bernstein-Vazirani algorithm finds the entire string in one query by evaluating f on a superposition of all inputs and using phase kickback to encode s directly into the quantum state.

This is a natural extension of Deutsch-Jozsa: instead of asking a yes/no question about f, we extract the full description of f in one shot.

How It Works

The Circuit (secret = "101")

CODECopy
     ┌───┐     ┌──────────┐     ┌───┐
q_0: ┤ H ├─────┤          ├─────┤ H ├─── M
     ├───┤     │          │     ├───┤
q_1: ┤ H ├─────┤  Oracle  ├─────┤ H ├─── M
     ├───┤     │  s="101" │     ├───┤
q_2: ┤ H ├─────┤          ├─────┤ H ├─── M
     ├───┤┌───┐│          │     └───┘
q_3: ┤ X ├┤ H ├┤          ├──────────
     └───┘└───┘└──────────┘

Step 1: Prepare

PYTHONCopy
qc.x(n)      # Ancilla → |1⟩
qc.h(n)      # Ancilla → |−⟩ (enables phase kickback)
for i in range(n):
    qc.h(i)  # Input qubits → superposition of all n-bit strings

Step 2: Oracle

PYTHONCopy
# For secret "101": CNOT from qubit 0 and qubit 2 to ancilla
for i, bit in enumerate(reversed(secret)):
    if bit == "1":
        qc.cx(i, n)  # Phase kickback: |x⟩ → (−1)^(x_i · s_i) |x⟩

The oracle applies CX from input qubit i to the ancilla only when s[i] = 1. Due to the ancilla being in |−⟩, each CX introduces a (−1)^x_i phase on the input register. The combined effect: |x⟩ → (−1)^(s·x) |x⟩.

Step 3: Decode

PYTHONCopy
for i in range(n):
    qc.h(i)          # Hadamard decodes the phase pattern
qc.measure(...)       # Result IS the secret string

The final Hadamard layer converts the phase encoding (−1)^(s·x) directly into the computational basis state |s⟩. This works because H^⊗n is its own inverse and maps phase patterns to bit patterns.

The Math

State Evolution

1. After H^⊗n on inputs: |ψ₁⟩ = (1/√2^n) Σ_x |x⟩

2. After oracle: |ψ₂⟩ = (1/√2^n) Σ_x (−1)^(s·x) |x⟩

3. After final H^⊗n: |ψ₃⟩ = |s⟩

The last step works because of the Hadamard identity: H^⊗n |s⟩ = (1/√2^n) Σ_x (−1)^(s·x) |x⟩

Applying H^⊗n to both sides (since H^⊗n is its own inverse): |s⟩ = H^⊗n [(1/√2^n) Σ_x (−1)^(s·x) |x⟩]

This is exactly our state after the oracle — so the final H^⊗n gives |s⟩.

Dot Product Examples (s = "101")

Expected Output

The algorithm is deterministic — the output is always the secret string:

One shot is enough. Multiple shots just confirm the determinism.

Running the Circuit

PYTHONCopy
from circuit import run_circuit, verify_bernstein_vazirani

# Find a 3-bit secret
counts = run_circuit(secret="101")
found = max(counts, key=counts.get)
print(f"Secret found: {found}")  # "101"

# Works for any length
counts = run_circuit(secret="11001")
found = max(counts, key=counts.get)
print(f"Secret found: {found}")  # "11001"

# Verify multiple secrets
result = verify_bernstein_vazirani()
for check in result["checks"]:
    print(f"  {check['name']}: {check['detail']}")

Try It Yourself

1. Try different secrets: Run with "111", "000", "1010". Do you always find the right answer in one shot?

2. Classical comparison: Write a classical algorithm to find s. How many queries does it need? (Exactly n — one per bit.)

3. Scale up: Try a 10-bit or 20-bit secret. The quantum algorithm still uses just 1 query. How does the circuit size scale?

4. Noisy simulation: Add depolarizing noise. How does the error rate scale with the length of the secret string?

What's Next

• Grover's Search — Quadratic speedup for unstructured search (different paradigm: amplitude amplification)
• Deutsch-Jozsa — The simpler version that asks a yes/no question
• Quantum Fourier Transform — The foundation for Shor's algorithm

Applications

References

• Bernstein, E. & Vazirani, U. (1997). "Quantum Complexity Theory." SIAM Journal on Computing 26(5), 1411-1473. DOI: 10.1137/S0097539796300921
• Nielsen, M.A. & Chuang, I.L. Quantum Computation and Quantum Information, Exercise 1.4.5.