Bernstein-Vazirani: Reading a Hidden String

Recover an n-bit secret string with a single oracle query where classical methods need n.

The hidden string

The oracle computes f(x) = s . x mod 2, the bitwise dot product of the input with a hidden n-bit string s. Classically you learn one bit of s per query by probing one-hot inputs, needing n queries. Bernstein-Vazirani needs one.

Circuit

It is the Deutsch-Jozsa circuit: Hadamard the register, apply the phase oracle (-1)^(s.x), Hadamard again, measure. The interference collapses the register directly to |s>.

import numpy as np
n=4; s=0b1011
N=2**n; psi=np.ones(N)/np.sqrt(N)
for x in range(N):
    psi[x]*=(-1)**(bin(x & s).count('1')%2)
H=np.array([[1,1],[1,-1]])/np.sqrt(2); Hn=np.array([1])
for _ in range(n): Hn=np.kron(Hn,H)
out=Hn@psi
print(format(int(np.argmax(out**2)),'0%db'%n))  # 1011 = s

Why it works

After the oracle the register is a product of single-qubit states, each in |+> or |-> according to the corresponding bit of s. The final Hadamard maps |+>->|0> and |->->|1>, so measurement reads s exactly, with certainty.

Takeaway

Bernstein-Vazirani shows a quantum query can extract a global linear structure in one shot. It is a stepping stone to Simon's algorithm and, from there, to the period-finding at the heart of Shor's factoring.