Algorithms · Quantum query algorithm
Bernstein–Vazirani hidden-string circuit
A query circuit that recovers the hidden bit string in f(x) = s · x.
Strong empiricalUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
Bernstein-Vazirani recovers a secret string
4 input qubits, secret string 1011, recovered in a single query.
Step 1 of 6 · X
Probability of each outcome after this step
- 10000100%
Sets the ancilla to |1⟩, so the next step can put it into |−⟩.
The whole state moves from 00000 to 10000 — one certain outcome before, one certain outcome after, no superposition either side.
Hadamards everything: the ancilla becomes |−⟩, and the four input qubits spread into an equal superposition.
Probability spreads from 1 outcome to 32. All 32 are equally likely.
CXs the input qubits where the secret has a 1 (positions 0, 1 and 3) onto the ancilla, kicking back a phase that encodes the secret.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
A second Hadamard layer on the inputs turns that phase pattern directly into the secret string.
Probability gathers from 32 outcomes onto 2. 01011 goes from 3.1% to 50.0%.
Undoes the ancilla's Hadamard.
Probability gathers from 2 outcomes onto 1. 11011 goes from 50.0% to 100.0%.
Returns the ancilla to |0⟩, purely for a tidy final state.
The whole state moves from 11011 to 01011 — one certain outcome before, one certain outcome after, no superposition either side.
Readout The four input qubits read 1011, the secret, recovered exactly, in one shot. The ancilla reads 0.
Open in Studio- Steps3
- Wires4
- Qubitsn + 1
- Depthoracle-dependent
- Queries1
- Papers1
Bernstein–Vazirani is a useful companion to Deutsch–Jozsa because it returns the hidden string rather than only its promise class.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Bernstein–Vazirani recovers a hidden bit string from an oracle for the parity function . The circuit prepares the output qubit in and the input register in superposition, queries once — phase kickback writes onto — and applies to the input register, which by the Hadamard/Fourier identity collapses it exactly to the basis state : measuring returns with certainty in the ideal circuit. Classically, determining an -bit from black-box parity queries requires queries (one per standard basis vector), so the quantum circuit gives an -to- query reduction under this promise, not a general search speedup. This record reviews the CX-based parity-oracle construction and its Deutsch–Jozsa-style readout; the one-query claim is scoped to this query/promise model, and oracle-construction and state-preparation costs stay visible rather than folded into the count.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Qubits
- n + 1
- Depth
- oracle-dependent
- Queries
- 1
- Function
- f(x) = s · x mod 2
- Quantum queries
- 1
- Classical queries
- n
Hon x[0], x[1], x[2], outU_son x[0], x[1], x[2], outMon x[0], x[1], x[2]
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
from qiskit import QuantumCircuit
secret = '101'
qc = QuantumCircuit(len(secret) + 1, len(secret))
qc.x(len(secret))
qc.h(range(len(secret) + 1))
for index, bit in enumerate(reversed(secret)):
if bit == '1':
qc.cx(index, len(secret))
qc.h(range(len(secret)))
qc.measure(range(len(secret)), range(len(secret)))
FINAL_CIRCUIT = qcRelated entries
- Deutsch–Jozsa query circuit
Algorithms
References
- Quantum Computation and Quantum Information: 10th Anniversary Edition
Michael A. Nielsen and Isaac L. Chuang · 2010
Standard graduate textbook covering the single- and two-qubit gate definitions, matrix identities, and circuit primitives this record states.