Bernstein–Vazirani: Recovering a 4-bit Secret
One query to f(x)=s·x mod 2 recovers the full secret s = 1011 with certainty.
Goal
Extract an entire secret string with a single query.
Approximate duration: 5 minutes
Steps
- Enter $s=1011$.
- Run the circuit.
- Compare the result with $s$.
- Try a longer string such as 100110.
Theory predicts $P(1011)=1$: every shot gives the same secret string.
The oracle hides a string $s$ of $n$ bits and returns $f(x)=s\cdot x$ (the dot product modulo 2). Classically $n$ queries are needed (one query per bit, with input $x=0\ldots010\ldots0$). The quantum circuit is the same as the Deutsch–Jozsa circuit: after H and the oracle the state is $\frac{1}{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}|x\rangle=H^{\otimes n}|s\rangle$, so H returns it to $|s\rangle$.
In the simulator the oracle is a set of CNOT gates from the qubits with $s_i=1$ to the ancilla qubit. The string is read in the order $q_{n-1}\dots q_0$.
Test your understanding
The quiz needs JavaScript.
Related topics
References
- Ethan Bernstein; Umesh Vazirani (1997). Quantum Complexity Theory. SIAM J. Comput. 26(5):1411–1473 doi:10.1137/S0097539796300921
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
