The Bernstein-Vazirani Algorithm

algorithmsLab

12 min read

The Bernstein-Vazirani Algorithm

Same circuit as Deutsch-Jozsa, one query, but this time it reads out an entire hidden bitstring instead of one bit of information.

Suggested before this lesson

The Deutsch-Jozsa Algorithm

Bernstein-Vazirani uses the exact same circuit shape as Deutsch-Jozsa. What changes is the oracle, and what you get out of it.

The Problem

You're given an oracle that computes $f(x) = s \cdot x \pmod 2$ (the bitwise dot product, mod 2) for some hidden bitstring $s$ you don't know. Classically, recovering all $n$ bits of $s$ takes $n$ separate queries: query $x = 100\ldots0$ and you learn $s_0$ , query $x=010\ldots0$ and you learn $s_1$ , and so on, one bit per query. Bernstein-Vazirani recovers the entire string $s$ in a single query.

The Oracle for a Linear $f$

This is precisely the linear-oracle recipe from the oracles lesson: $CX$ from input qubit $i$ into the ancilla, for every $i$ where $s_i = 1$ . Skip the $CX$ entirely for any $i$ where $s_i = 0$ : that input never gets XORed in, exactly matching what $s \cdot x$ means.

Take the hidden string $s = (s_0, s_1) = (1, 1)$ over 2 input qubits, ancilla on qubit 2: every input bit matters, so both $CX$ s are present:

Bernstein-Vazirani: s = (1, 1)

Open the Exact State table below: exactly one row has nonzero probability for the input qubits, and its input bits match s directly, qubit by qubit.

Circuit

Step through the circuit: after gate 8 of 8

9 / 9

Measurement Probabilities

$∣000 ⟩$

0.0%

$∣001 ⟩$

0.0%

$∣010 ⟩$

0.0%

$∣011 ⟩$

50.0%

$∣100 ⟩$

0.0%

$∣101 ⟩$

0.0%

$∣110 ⟩$

0.0%

$∣111 ⟩$

50.0%

Exact State

Basis state	Re	Probability
$∣000 ⟩$	0	0.0%
$∣001 ⟩$	0	0.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0.707	50.0%
$∣100 ⟩$	0	0.0%
$∣101 ⟩$	0	0.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	-0.707	50.0%

Unlike Deutsch-Jozsa's "is it all-zero or not," here every input qubit lands on a definite, predictable value: qubit $i$ measures $s_i$ , with certainty, for every $i$ ; one query and the whole string falls out. (Reading the basis-state label itself: this course writes kets as $|q_{n-1}\ldots q_1 q_0\rangle$ , rightmost character is qubit 0, the convention from way back in the What is a Qubit? lesson's Bloch-sphere work. It's simplest to just read the per-qubit values straight off the circuit rather than the label string.)

Exercise

Build the Bernstein-Vazirani circuit for the hidden string

s = (s_0, s_1) = (0, 1)

on a 3-qubit circuit (qubits 0, 1 are the input register, qubit 2 is the ancilla): prepare the ancilla in

|-\rangle

, put the input register in superposition, apply the oracle for this

s

(

CX

only from the input qubits where the corresponding

s

bit is 1), then apply

H

to the input register again.

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

Deutsch-Jozsa and Bernstein-Vazirani use the same circuit skeleton and both need only one oracle query. What's the actual difference between what they extract?

Deutsch-Jozsa gets 1 bit of information (constant vs. balanced); Bernstein-Vazirani gets all

n

bits of the hidden string, because its oracle is restricted to the linear

f = s \cdot x

form where every input qubit's outcome directly encodes one bit of

s

They extract exactly the same information; Bernstein-Vazirani is just a renamed version of Deutsch-Jozsa.

Bernstein-Vazirani needs the ancilla and Deutsch-Jozsa doesn't.

Deutsch-Jozsa works for any n, but Bernstein-Vazirani only works for n = 1.

The Problem

You're given an oracle that computes

f(x) = s \cdot x \pmod 2

(the bitwise dot product, mod 2) for some hidden bitstring

s

you don't know. Classically, recovering all

n

bits of

s

takes

n

separate queries: query

x = 100\ldots0

and you learn

s_0

, query

x=010\ldots0

and you learn

s_1

, and so on, one bit per query. Bernstein-Vazirani recovers the entire string

s

in a single query.

The Oracle for a Linear

f

This is precisely the linear-oracle recipe from the oracles lesson:

CX

from input qubit

i

into the ancilla, for every

i

where

s_i = 1

. Skip the

CX

entirely for any

i

where

s_i = 0

: that input never gets XORed in, exactly matching what

s \cdot x

means.

Take the hidden string

s = (s_0, s_1) = (1, 1)

over 2 input qubits, ancilla on qubit 2: every input bit matters, so both

CX

s are present:

Python

Bernstein-Vazirani: s = (1, 1)

Open the Exact State table below: exactly one row has nonzero probability for the input qubits, and its input bits match s directly, qubit by qubit.

Circuit

Step through the circuit: after gate 8 of 8

9 / 9

Measurement Probabilities

$∣000 ⟩$

0.0%

$∣001 ⟩$

0.0%

$∣010 ⟩$

0.0%

$∣011 ⟩$

50.0%

$∣100 ⟩$

0.0%

$∣101 ⟩$

0.0%

$∣110 ⟩$

0.0%

$∣111 ⟩$

50.0%

Exact State

Basis state	Re	Probability
$∣000 ⟩$	0	0.0%
$∣001 ⟩$	0	0.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0.707	50.0%
$∣100 ⟩$	0	0.0%
$∣101 ⟩$	0	0.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	-0.707	50.0%

Unlike Deutsch-Jozsa's "is it all-zero or not," here every input qubit lands on a definite, predictable value: qubit

i

measures

s_i

, with certainty, for every

i

; one query and the whole string falls out. (Reading the basis-state label itself: this course writes kets as

|q_{n-1}\ldots q_1 q_0\rangle

, rightmost character is qubit 0, the convention from way back in the What is a Qubit? lesson's Bloch-sphere work. It's simplest to just read the per-qubit values straight off the circuit rather than the label string.)

Exercise

Build the Bernstein-Vazirani circuit for the hidden string

s = (s_0, s_1) = (0, 1)

on a 3-qubit circuit (qubits 0, 1 are the input register, qubit 2 is the ancilla): prepare the ancilla in

|-\rangle

, put the input register in superposition, apply the oracle for this

s

(

CX

only from the input qubits where the corresponding

s

bit is 1), then apply

H

to the input register again.

Python

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

Deutsch-Jozsa and Bernstein-Vazirani use the same circuit skeleton and both need only one oracle query. What's the actual difference between what they extract?

Deutsch-Jozsa gets 1 bit of information (constant vs. balanced); Bernstein-Vazirani gets all

n

bits of the hidden string, because its oracle is restricted to the linear

f = s \cdot x

form where every input qubit's outcome directly encodes one bit of

s

They extract exactly the same information; Bernstein-Vazirani is just a renamed version of Deutsch-Jozsa.

Bernstein-Vazirani needs the ancilla and Deutsch-Jozsa doesn't.

Deutsch-Jozsa works for any n, but Bernstein-Vazirani only works for n = 1.