Code exampleIntermediateQuantum algorithms

Bernstein–Vazirani

Recover the secret s = 1011 with one query to f(x) = s·x.

The oracle is built with a CNOT from each qubit $i$ where $s_i=1$ to the ancilla. We loop over $s$ reversed because the last character corresponds to $q_0$ (little-endian ordering); this way the result is printed in the same order in which $s$ was written. Classically 4 queries are needed (one per bit).

Requirements: pip install qiskit qiskit-aer. The code runs on your machine or in Colab, not inside WordPress.

Code

Qiskit
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

s = "1011"
n = len(s)
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
for i, bit in enumerate(reversed(s)):
    if bit == "1":
        qc.cx(i, n)
qc.h(range(n))
qc.measure(range(n), range(n))

sim = AerSimulator()
counts = sim.run(transpile(qc, sim), shots=100, seed_simulator=2).result().get_counts()
print(counts)
print("recovered s =", max(counts, key=counts.get), "| secret =", s)

Line-by-line code explanation

LineExplanation
1-2Imports.
4The secret string.
5Its length.
6n qubits + an ancilla.
7-8The ancilla in |−⟩ and the inputs in superposition.
9Loop over the bits from q0 (the last character) upwards.
10-11CNOT to the ancilla where s_i = 1.
12H on the inputs.
13Measurement.
15-17Run and print the counts.
18Compare the output with the secret.

Expected output (from an actual run)

{'1011': 100}
recovered s = 1011 | secret = 1011

The result is deterministic; seed_simulator=2.

Try it yourself

Related topics

References

  1. Ethan Bernstein; Umesh Vazirani (1997). Quantum Complexity Theory. SIAM J. Comput. 26(5):1411–1473 doi:10.1137/S0097539796300921
  2. IBM Quantum (2025). Qiskit SDK API documentation. IBM Quantum Documentation quantum.cloud.ibm.com