Bernstein-Vazirani Algorithm | Hidden Bitstring Extraction in O(1)
Quick Technical Answer:
The Bernstein-Vazirani algorithm discovers an unknown secret n-bit string s encoded in a function f(x) = s · x mod 2 using just a single quantum query (O(1)), whereas classical algorithms require at least n queries.
Formula / Unitary:
f(x) = s \cdot x = s_1 x_1 \oplus s_2 x_2 \oplus \dots \oplus s_n x_n \pmod 2
Simulate this in Itachi Quantum Studio
Inspect state amplitudes, 3D Bloch sphere vector, and OpenQASM code live.
Frequently Asked Questions
How does Bernstein-Vazirani retrieve all n bits in one shot?
By placing the target qubit in |-⟩ and applying the oracle, the inner product s · x is kicked back into the phase of each computational basis state. A final Hadamard transform on all input qubits decodes s directly into the measured state.