Oracle Algorithms

Bernstein-Vazirani Algorithm

Finding a Hidden String with a Single Query

The Bernstein-Vazirani algorithm finds an unknown n-bit binary string hidden inside a black-box oracle using just one quantum query. Classically, n queries are necessary in the worst case, giving the algorithm a provable linear speedup that generalizes the ideas of Deutsch-Jozsa to a natural learning problem.

The Hidden String Problem

Imagine you are given a black-box function f_s: {0,1}^n → {0,1} defined by f_s(x) = s · x (mod 2), where s ∈ {0,1}^n is a secret binary string and the dot product is computed modulo 2. Your goal is to determine s. You can query the function on any input x, and the oracle returns the single bit f_s(x).

Classically, each query reveals one linear equation in the unknown bits of s. Since the equations are linearly independent only when queried on inputs that form a basis, you need at least n queries to solve for all n bits of s. In fact, n queries are both necessary and sufficient classically: query x = 100...0 to learn s1, x = 010...0 to learn s2, and so on.

f_s(x) = s \cdot x \mod 2 = \bigoplus_{i=1}^{n} s_i x_i

Oracle

\text{Given oracle access to } f_s, \text{ find } s \in \{0,1\}^n

Goal

•Oracle Definition: The oracle computes f_s(x) = s · x mod 2, where s is the hidden string.
•Classical Query Complexity: Exactly n queries are required in the worst case to determine s with certainty.
•Quantum Query Complexity: The Bernstein-Vazirani algorithm determines s using only 1 quantum query.
•Relation to DJ: Deutsch-Jozsa is the special case n = 1, where s = 0 means constant and s = 1 means balanced.

Quantum Algorithm

The quantum algorithm follows the same pattern as Deutsch-Jozsa. We initialize n+1 qubits, apply Hadamard gates to create superposition, query the oracle, apply Hadamard gates again, and measure. The magic lies in what happens during the oracle query when combined with the final Hadamard transform.

After the first layer of Hadamards, the input register is in a uniform superposition over all x. The oracle encodes the phase (-1)^(s·x) onto each component |x⟩. When we apply the second Hadamard layer, the quantum Fourier transform over the Boolean cube converts these phase factors back into amplitudes concentrated at the single basis state |s⟩. This is because the n-fold Hadamard gate is its own inverse, and its action on a phase vector precisely reveals the secret string.

Measuring the input register after the second Hadamard layer yields the secret string s with probability 1. The entire process requires just one call to the oracle, achieving an n-fold reduction in query complexity compared to any classical algorithm.

|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}

After first Hadamards

|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{s \cdot x} |x\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}

After oracle

|\psi_3\rangle = |s\rangle \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}

After second Hadamards

•Initialization: Start with |0⟩^⊗n|1⟩, apply H^⊗(n+1) to create superposition.
•Oracle Query: The oracle U_{f_s} imparts phases (-1)^(s·x) on each basis state |x⟩.
•Inverse Hadamard: Applying H^⊗n performs a Boolean Fourier transform, concentrating amplitude at |s⟩.
•Measurement: The measurement outcome is the hidden string s with certainty.

Applications and Generalizations

The Bernstein-Vazirani algorithm can be viewed as a quantum learning algorithm for the class of parity functions. It shows that quantum computers can learn certain concept classes with far fewer queries than classical learners. This has implications for computational learning theory and for understanding the power of quantum memory.

More broadly, the algorithm demonstrates that quantum computers can extract n bits of information from a single bit-valued oracle. This is not a violation of information theory because the oracle itself is a quantum operation acting on n+1 qubits — it contains the hidden string in its internal structure. The quantum query accesses this structure in a way that classical queries cannot.

•Learning Parity: BV is an optimal quantum learner for the class of linear Boolean functions.
•Cryptographic Relevance: Parity functions appear in stream ciphers and pseudorandom generators.
•Generalizations: Extensions learn polynomial functions and other structured classes with quantum speedups.

Code in Action

Runnable implementations you can copy and experiment with.

Bernstein-Vazirani with Qiskit

A complete BV circuit that discovers the hidden string s = "101" using a single oracle query.

bernstein_vazirani_qiskit.py

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n = 3
s = '101'  # hidden string

circuit = QuantumCircuit(n + 1, n)

# Initialize ancilla to |1>
circuit.x(n)
circuit.h(range(n + 1))

# Oracle: apply CNOT from qubit i to ancilla if s[i] == '1'
for i in range(n):
    if s[i] == '1':
        circuit.cx(i, n)

# Apply Hadamard to input register
circuit.h(range(n))

# Measure input register
circuit.measure(range(n), range(n))

# Execute
simulator = AerSimulator()
job = simulator.run(circuit, shots=1)
counts = job.result().get_counts()
measured = list(counts.keys())[0]
print(f"Hidden string: {measured[::-1]}")
# Expected output: 101

Bernstein-Vazirani with PennyLane

PennyLane implementation of BV that samples the hidden string in a single shot.

bernstein_vazirani_pennylane.py

import pennylane as qml

n = 3
s = '101'
dev = qml.device("default.qubit", wires=n + 1)

def bv_oracle():
    for i in range(n):
        if s[i] == '1':
            qml.CNOT(wires=[i, n])

@qml.qnode(dev)
def bernstein_vazirani():
    qml.PauliX(wires=n)
    for i in range(n + 1):
        qml.Hadamard(wires=i)
    bv_oracle()
    for i in range(n):
        qml.Hadamard(wires=i)
    return qml.sample(wires=range(n))

result = bernstein_vazirani()
hidden = ''.join(str(b) for b in result)
print(f"Hidden string: {hidden}")
# Expected output: 101

Explore next

Deutsch-Jozsa Algorithm

Explore next

Simon's Algorithm

from qiskit import QuantumCircuit from qiskit_aer import AerSimulator n = 3 s = '101' # hidden string circuit = QuantumCircuit(n + 1, n) # Initialize ancilla to |1> circuit.x(n) circuit.h(range(n + 1)) # Oracle: apply CNOT from qubit i to ancilla if s[i] == '1' for i in range(n): if s[i] == '1': circuit.cx(i, n) # Apply Hadamard to input register circuit.h(range(n)) # Measure input register circuit.measure(range(n), range(n)) # Execute simulator = AerSimulator() job = simulator.run(circuit, shots=1) counts = job.result().get_counts() measured = list(counts.keys())[0] print(f"Hidden string: {measured[::-1]}") # Expected output: 101

import pennylane as qml n = 3 s = '101' dev = qml.device("default.qubit", wires=n + 1) def bv_oracle(): for i in range(n): if s[i] == '1': qml.CNOT(wires=[i, n]) @qml.qnode(dev) def bernstein_vazirani(): qml.PauliX(wires=n) for i in range(n + 1): qml.Hadamard(wires=i) bv_oracle() for i in range(n): qml.Hadamard(wires=i) return qml.sample(wires=range(n)) result = bernstein_vazirani() hidden = ''.join(str(b) for b in result) print(f"Hidden string: {hidden}") # Expected output: 101