Bernstein-Vazirani: a hidden string in one query
25 min
The problem
The oracle hides an n-bit string s and computes f(x) = s · x mod 2, the parity of the bits of x where s has a 1. Classically, one call reveals one bit of s (query x with a single 1), so learning s takes n calls.
The circuit
It is the Deutsch-Jozsa circuit. After the oracle the phase on each input is (−1)s·x, and the final Hadamards turn that pattern into |s⟩. One call, and the inputs read s.
The lab
We write s as s0 s1 s2, in the order the bits m[0], m[1], m[2] are read. For s = 101 the oracle is one CNOT from each input where s has a 1: cx x[0], y and cx x[2], y. Our run read m[0] = 1, m[1] = 0, m[2] = 1 on all 1,000 shots. Change the CNOTs to hide another string and check that the program reads it back.
A link to the last lesson
The Deutsch-Jozsa oracle x0 xor x1 xor x2 is s · x with s = 111, which is why that lab read 111.
HiQ lab 1
Bernstein-Vazirani for s = 101
Recover the hidden string s from the oracle f(x) = s · x mod 2 with one call.
// Bernstein-Vazirani: recover the hidden string s = 101 with one oracle call.// The bits read m[0] = 1, m[1] = 0, m[2] = 1 on every shot.program bernstein_vaziraniqubits x[3], ybits m[3]x yh yrepeat i in 0..3 { h x[i]}// Oracle for s = 101: y ^= x0 xor x2.cx x[0], ycx x[2], yrepeat i in 0..3 { h x[i] measure x[i] -> m[i]}- What you should see
- m[0] = 1, m[1] = 0, m[2] = 1 on every shot: the hidden string, read in one query.
- What we measured
- m[0] = 1, m[1] = 0, m[2] = 1 on all 1,000 shots. QCOS checked this program and ran it on a Softquantus Cloud simulator, 1,000 shots, 13 November 2026.
Check it yourself
Save the program as bernstein-vazirani.qcos, set QCOS_API_KEY to a key from your workspace on the Softquantus Research Platform, and ask QCOS to check it. Change a line, check again, and see what the checker says.
pip install softqcossoftqcos lang check bernstein-vazirani.qcos