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
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
| Line | Explanation |
|---|---|
| 1-2 | Imports. |
| 4 | The secret string. |
| 5 | Its length. |
| 6 | n qubits + an ancilla. |
| 7-8 | The ancilla in |−⟩ and the inputs in superposition. |
| 9 | Loop over the bits from q0 (the last character) upwards. |
| 10-11 | CNOT to the ancilla where s_i = 1. |
| 12 | H on the inputs. |
| 13 | Measurement. |
| 15-17 | Run and print the counts. |
| 18 | Compare 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
- Ethan Bernstein; Umesh Vazirani (1997). Quantum Complexity Theory. SIAM J. Comput. 26(5):1411–1473 doi:10.1137/S0097539796300921
- IBM Quantum (2025). Qiskit SDK API documentation. IBM Quantum Documentation quantum.cloud.ibm.com
