ExperimentIntermediateInteractive experiment

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

  1. Enter $s=1011$.
  2. Run the circuit.
  3. Compare the result with $s$.
  4. Try a longer string such as 100110.
Loading the simulator…
What theory predicts

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

  1. Ethan Bernstein; Umesh Vazirani (1997). Quantum Complexity Theory. SIAM J. Comput. 26(5):1411–1473 doi:10.1137/S0097539796300921
  2. 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.