Bernstein–Vazirani: read a hidden string

Same circuit shape, more useful result: recover an n-bit secret with one query.

Intermediate10 min read4 sections · 2 questions+45

By the end you will be able to

01Build the oracle for a given secret s.
02Explain why the output register reads s exactly.

f_{s} (x) = s \cdot x mod 2, H^{\otimes n} (\frac{1}{2 ^{n}} x \sum (- 1)^{s \cdot x} ∣ x ⟩) = ∣ s ⟩

The oracle is one CNOT from each input bit where s has a 1 onto the target. After the final Hadamards the register is exactly |s⟩, deterministically.

Hands-on

Secret s = 101

Simulate: every shot reads 101. Change which CNOTs are present to encode another secret and watch the histogram follow.

OpenQASM 3

OPENQASM 3.0;
include "stdgates.inc";
qubit[4] q;
bit[3] c;
x q[3];
h q[0];
h q[1];
h q[2];
h q[3];
barrier q;
cx q[0], q[3];
cx q[2], q[3];
barrier q;
h q[0];
h q[1];
h q[2];
c[0] = measure q[0];
c[1] = measure q[1];
c[2] = measure q[2];

Open in the IDE Open in the Playground

Classically you need n queries (one per bit: query with x = 0…010…0). Quantumly one. Unlike Deutsch–Jozsa the gap holds even against randomised classical algorithms, which is why Bernstein–Vazirani is the first 'real' separation in the oracle model.

Knowledge check

2 questions · one try each counts

Question 1

With secret s = 011 (s0 = 1, s1 = 1, s2 = 0), which CNOTs form the oracle?

Question 2

A secret s has 50 bits. How many oracle queries does each side need to learn all of s for certain?

OPENQASM 3.0; include "stdgates.inc"; qubit[4] q; bit[3] c; x q[3]; h q[0]; h q[1]; h q[2]; h q[3]; barrier q; cx q[0], q[3]; cx q[2], q[3]; barrier q; h q[0]; h q[1]; h q[2]; c[0] = measure q[0]; c[1] = measure q[1]; c[2] = measure q[2];