Queries and Bernstein–Vazirani

1 / 14 · Learn

Before you start

Lesson 9 counted uses of an oracle: one for Deutsch–Jozsa, up to $2^{n-1}+1$ for a classical method that must be certain. This lesson makes that count a model of computation, then uses it on a new problem: finding a hidden string with a single query. You need the Hadamard formula and phase kickback from Lesson 9, and the habit from Lesson 13 of asking what an oracle leaves behind.

By the end of this lesson you can:

say what the query model counts, why it is useful, and what it leaves out;
explain why a classical algorithm needs $n$ queries to find $s$ in $f(x) = s\cdot x$ ;
run Bernstein–Vazirani by hand and explain why the last Hadamards return $s$ ;
build its oracle from CNOTs, and write and read the circuit in Qiskit;
state honestly how large the quantum advantage is.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

A black box hides a 5-bit string $s$ . Ask it about any 5-bit input $x$ and it answers with one bit, $f(x) = s\cdot x$ , the dot product mod 2. You ask about one input at a time and must be certain of $s$ at the end. How many questions do you need?

A $1$ , if it is well chosen
B $5$
C $17$
D $32$ : every input

Show the answer

Answer: B. $5$

Ask the 5 inputs with a single 1: the one with its 1 in place $k$ returns $s\cdot x = s_k$ . Fewer can’t do it: 4 one-bit answers form at most $2^{4} = 16$ patterns, but $s$ has 32 possible values, so two strings would give the same answers.

Why not the others

A. One answer is one bit, and $s$ could be any of $2^{5} = 32$ strings. A single bit splits them into at most two groups, so many strings would still fit the answer.
C. $2^{4} + 1 = 17$ is the Deutsch–Jozsa count, where many agreeing answers prove little. Here a well-chosen question gives one bit of $s$ directly: the input with a single 1 in place $k$ returns $s_k$ .
D. You never need every input. The input $10\ldots0$ returns $s_1$ , the input $010\ldots0$ returns $s_2$ , and so on: 5 questions.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

The same box, hiding a 5-bit string $s$ , is now a quantum oracle, $U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus s\cdot x}$ , which you may call on a superposition of inputs, with any gates before and after. What is the fewest calls that can find $s$ with certainty?

A $1$
BAbout $\sqrt{5}$ : a quantum computer gives a square-root saving
C $5$ : each call still answers with one bit
DNo number of calls gives certainty: quantum measurements are random

Show the answer

Answer: A. $1$

One call. Hadamards on the inputs, one call with the target in $\ket-$ , and Hadamards again leave the inputs in $\ket{s}$ , so measuring them gives all 5 bits of $s$ with certainty.

Why not the others

B. A square-root saving is what Grover’s search gives on problems with no structure to exploit. Here $f$ is linear in $x$ , and that structure lets one call reveal all of $s$ .
C. The answer bit isn’t where the information goes. With the target in $\ket-$ , one call writes the sign $(-1)^{s\cdot x}$ onto every input branch, and Hadamards turn that sign pattern into $\ket{s}$ : the 5 input qubits carry all of $s$ out.
D. A measurement is certain when the state is a basis state, as at the end of Deutsch–Jozsa for a constant $f$ . Here the circuit ends with the inputs in $\ket{s}$ , so the result is $s$ every time.

2 / 14 · Learn

The query model

In the query model a function $f$ sits inside a black box, the oracle. An algorithm may do anything it likes between calls, but it learns about $f$ only by calling the oracle, and its cost is the number of calls, or queries. Every other gate is free in this count.

Why count only that? First, lower bounds become provable: each call returns limited information, so one can show that no algorithm gets by with fewer calls. For ordinary running time such proofs are mostly out of reach. Second, the model shows where a speed-up comes from: the structure of $f$ , and interference between the branches of one call.

The catch: a real problem comes with no box. Someone has to build $U_f$ from gates, as in Lesson 13, and every call costs that whole circuit again. Lesson 18 builds real oracles.

Check yourself

Two algorithms solve the same problem with the same oracle. Algorithm A calls it 4 times and uses 60,000 other gates. Algorithm B calls it 50 times and uses 500 other gates. Built from gates, one call costs 800 gates. Which algorithm wins in the query model, and which uses fewer gates in all?

AA in the query model; B in total gates
BA on both counts: the number of calls is the whole cost
CB on both counts
DB in the query model; A in total gates

Hints

In the query model, what is counted and what is free?
For total gates, each call costs the oracle’s gates; add the other gates.

Show the answer

Answer: A. A in the query model; B in total gates

Calls: A makes 4, B makes 50, so A wins the query count. Gates: A uses 4 × 800 + 60,000 = 63,200 and B uses 50 × 800 + 500 = 40,500, so B is cheaper to run. The query model is a clean way to compare algorithms, but a real oracle is a circuit, and its gates count too.

Why not the others

B. The query count leaves out every gate outside the oracle, and treats each call as one step although it costs 800 gates. In all, A uses 4 × 800 + 60,000 = 63,200 gates and B uses 50 × 800 + 500 = 40,500.
C. In the query model only calls count, and A makes 4 against B’s 50. B wins only once every gate is counted: 40,500 against 63,200.
D. That swaps the two counts. Calls: A 4, B 50. Gates in all: A 63,200, B 40,500.

Query algorithms come in three kinds.

Deterministic: fixed rules choose each query from the answers so far, and the result must always be right.
Randomised: it may flip coins, and may be wrong with a small probability you choose, such as 1 in 1000.
Quantum: it calls $U_f$ on superpositions of inputs, with gates in between, and measures at the end.

The kind matters. For Deutsch–Jozsa on $n$ ⁠-bit inputs, Lesson 9 found that a deterministic algorithm can need $2^{n-1}+1$ queries, $k$ random queries err with probability at most $2^{1-k}$ whatever $n$ is, and the quantum algorithm needs one. An exponential gap against one kind of algorithm can shrink to a small one against another.

Check yourself

Deutsch–Jozsa with 30-bit inputs: is $f$ constant or balanced? Match each kind of algorithm with the number of queries that is enough for it, using the methods from Lesson 9.

Match each of these…

Deterministic, always right
Randomised, wrong at most 1 time in 1000
Quantum, always right

…with one of these

$1$
$30$
$2^{29}+1$
$11$

Show the answer

Deterministic, always right	$2^{29}+1$
Randomised, wrong at most 1 time in 1000	$11$
Quantum, always right	$1$

Deterministic: the first $2^{29}$ answers can agree, so $2^{29}+1$ . Randomised: the error after $k$ random queries is at most $2^{1-k}$ , and $2^{-10} = 1/1024$ is below 1 in 1000, so 11. Quantum: one call. The exponential gap holds only against the deterministic kind.

3 / 14 · Learn

The hidden-string problem

The Bernstein–Vazirani problem: a black box hides an $n$ ⁠-bit string $s = s_1s_2\ldots s_n$ and computes

f(x) = s\cdot x = s_1x_1\oplus s_2x_2\oplus\cdots\oplus s_nx_n,

the dot product mod 2 from Lesson 9. Find $s$ .

So $f(x)$ is the parity of the bits of $x$ in the places where $s$ has a 1. With $s = 101$ , $f(110) = 1\cdot1\oplus0\cdot1\oplus1\cdot0 = 1$ and $f(111) = 1\oplus0\oplus1 = 0$ .

Every such $f$ except $s = 0\ldots0$ is balanced, so it is also a valid Deutsch–Jozsa input; you saw $f(x) = x_1\oplus x_2$ there. The question is new: not “constant or balanced?” but “which $s$ ?”

Check yourself

$s = 1011$ . What is $f(1101) = s\cdot x$ ?

Hints

Multiply the two strings bit by bit, then add the products mod 2.
Both strings have a 1 in 2 places.

Show the answer

Answer: $0$

Bit by bit: $1\cdot1 = 1$ , $0\cdot1 = 0$ , $1\cdot0 = 0$ , $1\cdot1 = 1$ . The products add up to 2, and $2 \bmod 2 = 0$ , so $f(1101) = 0$ .

Common slips

$2$ : 2 is the number of places where both strings have a 1. The dot product mod 2 keeps only whether that number is odd: $2 \bmod 2 = 0$ .
$1$ : Line the strings up and multiply bit by bit: $1\cdot1 = 1$ , $0\cdot1 = 0$ , $1\cdot0 = 0$ , $1\cdot1 = 1$ . The products add up to 2, which is even, so $s\cdot x = 0$ .

4 / 14 · Explore

Finding s one bit at a time

Each answer is one bit, but a well-chosen question makes that bit a bit of $s$ . Write $e_k$ for the input with a single 1, in place $k$ . Then $f(e_k) = s_k$ : for $n = 3$ , ask $f(100)$ , $f(010)$ and $f(001)$ and read off $s_1$ , $s_2$ , $s_3$ . That is $n$ queries.

No deterministic method does better. Its answers trace a path down a tree like the one below: each one-bit answer splits the candidates into at most two groups. After $k$ queries there are at most $2^k$ groups, and certainty needs one candidate per group, so $2^k \ge 2^n$ and $k \ge n$ . This is the query model at work: a lower bound that holds for every possible algorithm.

The single-1 strategy for $n = 3$ . Each question is answered with one bit, so three answers lead to one of $2^3 = 8$ leaves, one for each $s$ . The path for $s = 101$ is highlighted: $f(100) = 1$ , $f(010) = 0$ , $f(001) = 1$ .

Check yourself

A 10-bit string $s$ is chosen at random, all $2^{10} = 1{,}024$ strings equally likely. A deterministic algorithm asks 7 questions $f(x) = s\cdot x$ , one bit each, and then names one string. What is the highest possible probability that it names $s$ ?

$P(\text{right}) = \;?$

Hints

After the answers come in, how many groups can the strings be split into?
7 one-bit answers have at most $2^{7}$ patterns; the algorithm names one string per pattern.

Show the answer

Answer: $P(\text{right}) = \frac{1}{8}$

7 one-bit answers split the 1,024 strings into at most $2^{7} = 128$ groups, and the algorithm names one string per group. So it is right for at most 128 of the 1,024 strings: probability $2^{7}/2^{10} = 1/8$ . Asking 7 single-1 inputs and guessing the other 3 bits achieves it.

Common slips

$\frac{7}{10}$ : That gives credit for each bit found, but the answer counts only if all 10 bits are right. 3 bits are still unknown, and a guess gets all of them right with probability $1/2^{3}$ .
$0$ : It can’t be certain, but it can be lucky. Asking 7 single-1 inputs fixes 7 bits, and a guess at the other 3 bits is right with probability $1/2^{3}$ . (A blind guess, with no questions asked, would be right with probability $1/1{,}024$ , close to 0.)

5 / 14 · Learn

One query

Quantumly, use the oracle in phase form. With the target in $\ket-$ , kickback (Lesson 9) gives

U_f\ket{x}\ket- = (-1)^{s\cdot x}\ket{x}\ket-,

so the target stays put and each call multiplies the input branch $\ket{x}$ by a sign. The circuit is Deutsch–Jozsa’s; only the reading of the result is new.

Start the $n$ inputs in $\ket{0\ldots0}$ and the target in $\ket1$ , and apply $H$ to every qubit.
Call the oracle once. The inputs become $\frac{1}{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}\ket{x}$ .
Apply $H$ to each input qubit again and measure the inputs in the 0/1 basis.

The claim is that the result is $s$ , every time.

Predict, then see

Bernstein–Vazirani with $n = 3$ and $s = 101$ . What will the 0/1-basis measurement of the three input qubits give?

AOne bit of $s$ per run, so three runs to see all of it
B $101$ , every time
CA random input $x$ , with $f(x)$ in the target
DEach of the eight strings, with probability $\tfrac18$

Where did the information about $s$ sit just after the call, and what did the last Hadamards do with it? A sentence or two is enough.

Show what happens

What happens: B. $101$ , every time

After the first Hadamards the inputs hold all eight strings with equal amplitude, and the target is $\ket-$ . The call gives each branch the sign $(-1)^{s\cdot x}$ . The last Hadamards make the eight branches interfere: they add up on $\ket{101}$ and cancel on every other string. So the inputs read $101 = s$ every time; the target, still $\ket-$ , gives a random bit.

Why not the others

A. One run measured all three inputs, and all three bits matched $s$ . The call wrote a sign on every branch, and the Hadamards turned the whole sign pattern into $\ket{101}$ .
C. With the target in $\ket-$ , nothing is written into it: it stays $\ket-$ and reads 0 or 1 at random. The inputs are not random at all; they read $101$ .
D. It seemed the last Hadamards would spread the amplitude evenly. Stepping through showed the eight branches recombining: they add up on $\ket{101}$ and cancel everywhere else.

6 / 14 · Learn

Why the last Hadamards return s

Lesson 9 gave the Hadamard transform of a basis state:

H^{\otimes n}\ket{s} = \frac{1}{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}\ket{x}.

That is exactly the state of the inputs after the call. The oracle has prepared $H^{\otimes n}\ket{s}$ without anyone knowing $s$ . And $H^{\otimes n}$ undoes itself, since $HH = I$ on every qubit, so the last Hadamards give $H^{\otimes n}H^{\otimes n}\ket{s} = \ket{s}$ .

Each $s$ leaves its own sign pattern on the $2^n$ inputs. The figure shows three for $n = 3$ . In the shaded columns, the inputs with a single 1, the sign is $(-1)^{s_k}$ : the classical strategy reads exactly these, one query each.

The sign $(-1)^{s\cdot x}$ on each input $x$ after the call, for three hidden strings. Every bar is an amplitude of size $1/\sqrt8$ . The pattern of $101$ is the pattern of $100$ times the pattern of $001$ , column by column.

Check yourself

Bernstein–Vazirani with $n = 3$ . Right after the call, the eight input branches $\ket{000}, \ket{001}, \ldots, \ket{111}$ carry the signs $(+,\ +,\ -,\ -,\ -,\ -,\ +,\ +)$ , in that order. Which string $s$ is hidden?

A $011$
B $110$
C $001$
D $010$

Hints

The sign on $\ket{x}$ is $(-1)^{s\cdot x}$ . Which inputs $x$ make $s\cdot x$ equal to a single bit of $s$ ?
At $x = 100$ the sign is $(-1)^{s_1}$ ; at $010$ , $(-1)^{s_2}$ ; at $001$ , $(-1)^{s_3}$ .

Show the answer

Answer: B. $110$

The signs at the inputs with a single 1 spell out $s$ : $x = 100$ has $-$ , $x = 010$ has $-$ , $x = 001$ has $+$ , so $s = 110$ . Check one more: at $x = 111$ the sign is $(-1)^{s_1\oplus s_2\oplus s_3} = +1$ , as listed.

Why not the others

A. That reads the bits from right to left. The sign at $x = 100$ is $(-1)^{s_1}$ , so it gives the first bit of $s$ ; the sign at $x = 001$ gives the last.
C. A minus sign means $s\cdot x = 1$ . At $x = 100$ the sign is $-$ , so $s_1 = 1$ : read $-$ as 1 and $+$ as 0.
D. The pattern of $010$ has the sign $+$ at $x = 100$ , but this one has $-$ there. The signs at $100$ , $010$ and $001$ give $s_1$ , $s_2$ , $s_3$ .

The same fact, seen from the end of the circuit. After the last Hadamards the amplitude of an outcome $\ket{z}$ is

\frac{1}{2^n}\sum_x(-1)^{s\cdot x}(-1)^{z\cdot x}.

Each term is $+1$ where the two sign patterns agree and $-1$ where they differ. For $z = s$ they agree everywhere, and the amplitude is 1. For any other $z$ the product of the two patterns is the pattern of $s\oplus z$ , a balanced function, so the terms cancel to 0. The last Hadamards compare the pattern with every candidate at once, and only $s$ survives.

Two comparisons for $s = 101$ . Against $z = 101$ every product is $+$ , so the amplitude is $8/8 = 1$ . Against $z = 001$ four products are $+$ and four are $-$ , so the amplitude is 0. The bars at the bottom show every outcome’s amplitude: all of it is on $101$ .

Check yourself

Bernstein–Vazirani with $n = 3$ and $s = 101$ . Just before the measurement, what is the amplitude of $\ket{011}$ in the input register?

Hints

Compare the sign patterns of $s = 101$ and $z = 011$ : where do they agree?
The product of the two patterns is the pattern of $101\oplus011 = 110$ , which is balanced.

Show the answer

Answer: $0$

The product of the two patterns is the pattern of $101\oplus011 = 110$ : four $+1$ ⁠s and four $-1$ ⁠s. Their average is 0, so $\ket{011}$ has amplitude 0. Only $\ket{101}$ survives.

Common slips

$\frac{1}{8}$ : That spreads the probability evenly over the eight strings. The patterns of $101$ and $011$ agree on four inputs and differ on four, so the eight terms cancel: $(4 - 4)/8 = 0$ .
$\frac{1}{2}$ : Half the terms are $+1$ , but the other half are $-1$ and cancel them: $(4 - 4)/8 = 0$ .
$\frac{\sqrt{2}}{4}$ : $1/\sqrt8$ is each amplitude right after the call. The last Hadamards then add up eight signed terms for each outcome, and for $011$ they cancel.

7 / 14 · Learn

Building the oracle

So far the oracle was a box. For this $f$ you can build it, and cheaply. $s\cdot x$ is the XOR of the bits $x_k$ with $s_k = 1$ , and a CNOT from $x_k$ into the target adds $x_k$ to it mod 2. So one CNOT from each such input computes

\ket{x}\ket{y}\mapsto\ket{x}\ket{y\oplus s\cdot x} = U_f\ket{x}\ket{y}.

For $s = 1011$ that is three CNOTs, from $x_1$ , $x_3$ and $x_4$ . There is no work qubit and no garbage, so nothing has to be uncomputed. The whole oracle costs at most $n$ CNOTs.

Check yourself

Build $U_f$ for $s = 101$ : the top three wires are $x_1, x_2, x_3$ and the bottom wire is the target. A control dot and an $X$ in the same column make a CNOT.

Build it in the circuit builder (gates: control, X).

Hints

Which bits does $f(x) = s\cdot x$ add up when $s = 101$ ?
Each CNOT from an input into the target adds that bit to the target, mod 2.
Every gate in a column obeys every dot in that column, so two dots in one column make a Toffoli, which adds $x_1x_3$ (AND). Give each CNOT its own column.

Show the answer

One circuit that works: CNOT q0→q3, then CNOT q2→q3.

For $s = 101$ , $f(x) = x_1\oplus x_3$ : a CNOT from $x_1$ and a CNOT from $x_3$ , in separate columns, add those two bits to the target. Their order doesn’t matter.

Compare a careless build. Lesson 13 showed that a work qubit left holding an intermediate value wrecks interference. The next question puts that to the test on this circuit.

Check yourself

A student builds the oracle for $s = 101$ with a spare work qubit that starts in $\ket0$ : CNOTs from $x_1$ and $x_3$ into the work qubit, which then holds $s\cdot x$ , and one CNOT from the work qubit into the $\ket-$ target. The work qubit is left as it is. What does the Bernstein–Vazirani measurement of $x_1x_2x_3$ give?

A $101$ every time: the target still kicks back the right sign
B $000$ every time: the work qubit takes the answer
CEach of the eight strings, with probability $\tfrac18$
D $101$ or $000$ , with probability $\tfrac12$ each

Show the answer

Answer: D. $101$ or $000$ , with probability $\tfrac12$ each

After the call the state is $\tfrac{1}{\sqrt8}\sum_x(-1)^{s\cdot x}\ket{x}\ket{s\cdot x}\ket-$ : the work qubit is entangled with the inputs. Each of its two values keeps four branches, and the last Hadamards turn each group into an even mix of $\ket{000}$ and $\ket{101}$ . Uncomputing the work qubit (running its two CNOTs again) would restore the certain answer.

Why not the others

A. The sign does land on each branch, but the work qubit now holds $s\cdot x$ , a record of which half of the inputs each branch belongs to. Branches with different records can’t interfere, so the cancellation that leaves only $\ket{s}$ fails.
B. The work qubit does hold $s\cdot x$ , but that doesn’t send every branch to $000$ . Each group of branches, with $s\cdot x = 0$ or $1$ , ends in an even mix of $\ket{000}$ and $\ket{s}$ .
C. The record splits the eight branches into two groups of four, one for each value of $s\cdot x$ . Within a group they still interfere, so most outcomes still cancel: only $000$ and $s$ survive.

8 / 14 · Worked example

Worked example: qubit by qubit

The state after the call factors into one qubit at a time, which makes Bernstein–Vazirani easy to trace by hand.

Bernstein–Vazirani for $s = 1011$ , with the oracle built from CNOTs. At slice 1 every input is $\ket+$ ; at slice 2 the inputs with $s_k = 1$ have turned into $\ket-$ ; at slice 3 each input is $\ket{s_k}$ .

Worked example

Bernstein–Vazirani for $s = 101$

The sign splits into one factor per qubit, $(-1)^{s\cdot x} = (-1)^{s_1x_1}(-1)^{s_2x_2}(-1)^{s_3x_3}$ , so the state stays a product throughout. Take $n = 3$ , $s = 101$ , and the oracle built from CNOTs.

Before the call
After the first Hadamards each input is $\ket+ = (\ket0 + \ket1)/\sqrt2$ and the target is $H\ket1 = \ket-$ . The state is $\ket+\ket+\ket+\,\ket-$ .
The call
The oracle is a CNOT from $x_1$ and a CNOT from $x_3$ into the target. A CNOT into a $\ket-$ target multiplies its control’s $\ket1$ branch by $-1$ (Lessons 6 and 7), which turns $\ket+$ into $\ket-$ . So after the call the state is $\ket-\ket+\ket-\,\ket-$ : the inputs with $s_k = 1$ are $\ket-$ , the others still $\ket+$ .
Last H
$H\ket+ = \ket0$ and $H\ket- = \ket1$ , so the inputs become $\ket1\ket0\ket1$ and the measurement reads $101 = s$ . No qubit was ever entangled with another: each carried its own bit of $s$ as a sign.
Your turn: the call
Now $s = 011$ . Start again from $\ket+\ket+\ket+\,\ket-$ .
Your turn
Which input qubits are in $\ket-$ right after the call?
Select all that apply.
1. A $x_1$
2. B $x_2$
3. C $x_3$
4. DNone of them: a CNOT never changes its control
Hint
1. Which inputs does the oracle for $s = 011$ connect to the target?
Show the answer
Answers: B. $x_2$ ; C. $x_3$
For $s = 011$ the oracle is a CNOT from $x_2$ and one from $x_3$ . Each kicks a minus sign onto its control’s $\ket1$ branch: $\ket+\ket-\ket-\,\ket-$ .
Why not the others
- A. $s_1 = 0$ , so the oracle has no CNOT from $x_1$ : nothing kicks back, and it stays $\ket+$ .
- D. That holds for controls in $\ket0$ or $\ket1$ . Here the target is $\ket-$ , and $X\ket- = -\ket-$ puts a minus sign on the control’s $\ket1$ branch, which turns $\ket+$ into $\ket-$ .
Your turn: read out
Your turn
What does the measurement of $x_1x_2x_3$ give?
1. A $100$ , every time
2. B $110$ , every time
3. C0 or 1 at random on $x_2$ and $x_3$
4. D $011$ , every time
Show the answer
Answer: D. $011$ , every time
$H\ket+ = \ket0$ and $H\ket- = \ket1$ , so $\ket+\ket-\ket-$ becomes $\ket0\ket1\ket1$ : the measurement reads $011 = s$ .
Why not the others
- A. $H\ket- = \ket1$ , not $\ket0$ : the qubits that are $\ket-$ after the call read 1.
- B. That reverses the order. $x_1$ is the first bit; it stayed $\ket+$ and reads 0.
- C. Measuring $\ket-$ directly would be a coin toss, but the last $H$ comes first, and $H\ket- = \ket1$ exactly.

One more, fully worked.

Another worked example

Another example: $s = 110$

Before the call
As always: $\ket+\ket+\ket+\,\ket-$ .
The call
For $s = 110$ the oracle is a CNOT from $x_1$ and one from $x_2$ . Each turns its control into $\ket-$ : $\ket-\ket-\ket+\,\ket-$ .
Last H
$\ket-\ket-\ket+$ becomes $\ket1\ket1\ket0$ . The measurement reads $110 = s$ .

9 / 14 · Learn

Bernstein–Vazirani in Qiskit

In Qiskit the circuit takes a few lines, with one detail to watch: Qiskit prints qubit 0 as the rightmost bit of a result (Lesson 12). Put $x_1$ on qubit 0, $x_2$ on qubit 1 and so on, as in the circuits here, and a run for $s = s_1s_2\ldots s_n$ prints $s_n\ldots s_2s_1$ , reversed.

The program below sidesteps this by writing the string s the way Qiskit prints: its last character belongs to qubit 0. That is why the loop runs over reversed(s): qubit i gets a CNOT when the i-th character from the right is 1, and the counts then show s exactly as written. Run it, then change s.

Interactive

A code editor for Python with Qiskit’s circuit methods, run in the page: edit the program below and run it to see the circuit it builds, the state it leaves and, when it measures, the counts from 1,000 shots.

from qiskit import QuantumCircuit

s = '10110'                  # the hidden string, as Qiskit will print it
n = len(s)
qc = QuantumCircuit(n + 1, n)  # n inputs, the target is qubit n

qc.x(n)                       # target in |1>
qc.h(range(n + 1))            # H on every qubit
for i, bit in enumerate(reversed(s)):
    if bit == '1':
        qc.cx(i, n)           # the oracle: one CNOT per 1 in s
qc.h(range(n))                # H on the inputs
qc.measure(range(n), range(n))

Bernstein–Vazirani for a 5-bit string. Every shot prints 10110. Try another string, or replace reversed(s) with s and see the counts come out reversed.

Open it in the app

Check yourself

A Bernstein–Vazirani program on 4 input qubits puts a CNOT from qubits 0, 1 and 3 into the target, qubit 4, and measures qubit $k$ into classical bit $k$ for $k = 0, \ldots, 3$ . It runs 1000 shots. What do Qiskit’s counts show?

A{'0100': 1000}
B{'1011': 1000}
C{'1101': 1000}
DAbout 63 shots on each of the 16 strings

Hints

Which qubits end in $\ket1$ ?
Qiskit writes qubit 0 as the last character of the string.

Show the answer

Answer: B. {'1011': 1000}

Qubits 0, 1 and 3 get a CNOT, so they read 1 and the rest read 0. In lesson order, qubit 0 first, that is $1101$ . Qiskit prints qubit 0 rightmost, so every shot shows 1011.

Why not the others

A. The qubits with a CNOT read 1, not 0. Each CNOT into the $\ket-$ target turns its control’s $\ket+$ into $\ket-$ , and $H\ket- = \ket1$ .
C. That writes qubit 0 first, as the kets in these lessons do. Qiskit prints qubit 0 as the rightmost bit, so the string comes out the other way round.
D. The last Hadamards don’t spread the shots out. They turn the sign pattern from the call into one basis state, so every shot gives the same string.

Check yourself

The program below is missing its oracle. The hidden string is s = '110100', written the way Qiskit prints results. Add the oracle so that every shot reads 110100 in the counts.

from qiskit import QuantumCircuit

s = '110100'                 # the hidden string, as Qiskit will print it
n = len(s)
qc = QuantumCircuit(n + 1, n)

qc.x(n)                       # target (qubit n) in |1>
qc.h(range(n + 1))
# the oracle: one CNOT into qubit n for each 1 in s

qc.h(range(n))
qc.measure(range(n), range(n))

Write the program in the app’s code editor (Python with Qiskit’s circuit methods), run it, and check it.

Hints

Qiskit prints qubit 0 as the rightmost bit. Which character of s belongs to qubit 0?
The last character, s[5], belongs to qubit 0, and the first, s[0], to qubit 5. Loop over enumerate(reversed(s)).
For each i, bit in enumerate(reversed(s)), add qc.cx(i, n) when bit == '1'.

Show the answer

One program that works:

from qiskit import QuantumCircuit

s = '110100'                 # the hidden string, as Qiskit will print it
n = len(s)
qc = QuantumCircuit(n + 1, n)

qc.x(n)                       # target (qubit n) in |1>
qc.h(range(n + 1))
for i, bit in enumerate(reversed(s)):
    if bit == '1':
        qc.cx(i, n)
qc.h(range(n))
qc.measure(range(n), range(n))

Qiskit writes qubit 0 as the rightmost bit, so the last character of s decides qubit 0’s CNOT. Looping over reversed(s) lines them up: CNOTs from qubits 2, 4 and 5, and the counts read 110100.

10 / 14 · Learn

How big is the gap?

Count honestly. Classically, Bernstein–Vazirani needs $n$ queries, and randomness doesn’t help much: a randomised algorithm is a mixture of deterministic ones, so with $k$ queries it is right with probability at most $2^k/2^n$ on a random $s$ . The quantum algorithm needs one query. That is $n$ against 1: a polynomial gap, not an exponential one. It survives randomness, unlike Deutsch–Jozsa’s, but it was never large.

Count gates and it shrinks further. The quantum circuit spends up to $n$ CNOTs on its one call, plus one $X$ and $2n + 1$ Hadamards. The classical method makes $n$ calls. Both cost about $n$ steps.

So why study it? It is the cleanest case of Hadamards, one call and Hadamards beating classical queries, and Lesson 15 uses the same pattern on a problem where classical algorithms need exponentially many queries.

Check yourself

Bernstein–Vazirani for the 20-bit string $s = 11\ldots1$ (all ones), with the oracle built from CNOTs. Counting every $X$ , $H$ and CNOT, how many gates does the whole circuit use?

Hints

List the layers: the target’s $X$ , the first Hadamards, the oracle, the last Hadamards.
The first Hadamards act on all 21 qubits, the last ones on the 20 inputs; the oracle is one CNOT per 1 in $s$ .

Show the answer

Answer: $62$

One $X$ , 21 Hadamards on all qubits, 20 CNOTs for the oracle, and 20 Hadamards on the inputs: $1 + 21 + 20 + 20 = 62$ . The classical method makes 20 calls; in gates the two are about the same size.

Common slips

$1$ : One is the number of calls. Built from gates, the call is 20 CNOTs, and the circuit around it has an $X$ and 41 Hadamards.
$42$ : That leaves out the oracle. For $s = 11\ldots1$ it is one CNOT from each of the 20 inputs: $42 + 20 = 62$ .
$61$ : Almost: the target also needs its $X$ , to start in $\ket1$ .
$63$ : The second layer of Hadamards acts on the 20 inputs only, not on the target: $1 + 21 + 20 + 20 = 62$ .

11 / 14 · Practice

Practice

Three items, each with new numbers when it comes back. Hints are there if you need them.

Check yourself

$s = 00011$ . What is $f(01111) = s\cdot x$ ?

Hints

Multiply the two strings bit by bit, then add the products mod 2.
Both strings have a 1 in 2 places.

Show the answer

Answer: $0$

Bit by bit: $0\cdot0 = 0$ , $0\cdot1 = 0$ , $0\cdot1 = 0$ , $1\cdot1 = 1$ , $1\cdot1 = 1$ . The products add up to 2, and $2 \bmod 2 = 0$ , so $f(01111) = 0$ .

Common slips

$2$ : 2 is the number of places where both strings have a 1. The dot product mod 2 keeps only whether that number is odd: $2 \bmod 2 = 0$ .
$1$ : Line the strings up and multiply bit by bit: $0\cdot0 = 0$ , $0\cdot1 = 0$ , $0\cdot1 = 0$ , $1\cdot1 = 1$ , $1\cdot1 = 1$ . The products add up to 2, which is even, so $s\cdot x = 0$ .

Check yourself

Bernstein–Vazirani with $n = 4$ and $s = 0100$ . Right after the call, what is the amplitude of $\ket{1001}$ in the input register?

Hints

Before the call every input has the same amplitude. What does the call change?
The call multiplies $\ket{x}$ by $(-1)^{s\cdot x}$ . Work out $0100\cdot1001$ .

Show the answer

Answer: $\frac{1}{4}$

Before the call every input has amplitude $1/\sqrt{2^{4}}$ . The call multiplies $\ket{1001}$ by $(-1)^{s\cdot x}$ with $0100\cdot1001 = 0$ , so the amplitude is $\frac{1}{4}$ .

Common slips

$-\frac{1}{4}$ : Right size, wrong sign. The sign is $(-1)^{s\cdot x}$ , and $0100\cdot1001 = 0$ .
$\frac{1}{16}$ : $1/16$ is the size of a probability here. Each of the 16 amplitudes has size $1/\sqrt{2^{4}}$ , so that their squares add up to 1.
$0$ : Only after the last Hadamards does the amplitude gather on $\ket{0100}$ . Right after the call, every input still has amplitude of size $1/\sqrt{2^{4}}$ ; the call only sets its sign.

Check yourself

You build the oracle for $f(x) = s\cdot x$ with $s = 11110$ from CNOTs into the target. Which input wires get a CNOT?

Select all that apply.

A $x_1$
B $x_2$
C $x_3$
D $x_4$
E $x_5$

Hint

$s\cdot x$ adds up, mod 2, the bits $x_k$ where $s_k = 1$ .

Show the answer

Answers: A. $x_1$ ; B. $x_2$ ; C. $x_3$ ; D. $x_4$

$s\cdot x$ is the XOR of the bits $x_k$ with $s_k = 1$ : here $x_1$ , $x_2$ , $x_3$ , $x_4$ . One CNOT from each of them into the target adds that bit to it, so together they add $s\cdot x$ .

Why not the others

E. $s_5 = 0$ , so $x_5$ doesn’t appear in $s\cdot x$ and needs no CNOT.

12 / 14 · Explain

Explain it

A classical query to this box returns one bit, yet one quantum call reveals all $n$ bits of $s$ . Explain how, and why this doesn’t break the rule that each answer is one bit.

Show a model answer

With the target in $\ket-$ , the call writes no bit into the target at all: kickback multiplies each input branch $\ket{x}$ by $(-1)^{s\cdot x}$ . Because the inputs are in a superposition of all $2^n$ strings, one call writes a whole sign pattern, and that pattern is exactly $H^{\otimes n}\ket{s}$ . The last Hadamards undo the transform and leave $\ket{s}$ , so measuring the $n$ inputs gives every bit of $s$ . The one-bit rule is about the answer register; a quantum call also acts on the $n$ input qubits, and they carry the information out.

A good answer covers

Kickback: the call puts the sign $(-1)^{s\cdot x}$ on every input branch, not a bit in the target
The sign pattern equals $H^{\otimes n}\ket{s}$ , so the last Hadamards turn it into $\ket{s}$
The information leaves through the $n$ input qubits, which is how one call gives $n$ bits

13 / 14 · Mastery check

Mastery check

Check yourself

A black box hides a 6-bit string $s$ . Ask it about any 6-bit input $x$ and it answers with one bit, $f(x) = s\cdot x$ , the dot product mod 2. You ask about one input at a time and must be certain of $s$ at the end. How many questions do you need?

A $1$ , if it is well chosen
B $6$
C $33$
D $64$ : every input

Show the answer

Answer: B. $6$

Ask the 6 inputs with a single 1: the one with its 1 in place $k$ returns $s\cdot x = s_k$ . Fewer can’t do it: 5 one-bit answers form at most $2^{5} = 32$ patterns, but $s$ has 64 possible values, so two strings would give the same answers.

Why not the others

A. One answer is one bit, and $s$ could be any of $2^{6} = 64$ strings. A single bit splits them into at most two groups, so many strings would still fit the answer.
C. $2^{5} + 1 = 33$ is the Deutsch–Jozsa count, where many agreeing answers prove little. Here a well-chosen question gives one bit of $s$ directly: the input with a single 1 in place $k$ returns $s_k$ .
D. You never need every input. The input $10\ldots0$ returns $s_1$ , the input $010\ldots0$ returns $s_2$ , and so on: 6 questions.

Check yourself

Two algorithms solve the same problem with the same oracle. Algorithm A calls it 6 times and uses 120,000 other gates. Algorithm B calls it 60 times and uses 4,000 other gates. Built from gates, one call costs 1,200 gates. Which algorithm wins in the query model, and which uses fewer gates in all?

AA in the query model; B in total gates
BA on both counts: the number of calls is the whole cost
CB on both counts
DB in the query model; A in total gates

Show the answer

Answer: A. A in the query model; B in total gates

Calls: A makes 6, B makes 60, so A wins the query count. Gates: A uses 6 × 1,200 + 120,000 = 127,200 and B uses 60 × 1,200 + 4,000 = 76,000, so B is cheaper to run. The query model is a clean way to compare algorithms, but a real oracle is a circuit, and its gates count too.

Why not the others

B. The query count leaves out every gate outside the oracle, and treats each call as one step although it costs 1,200 gates. In all, A uses 6 × 1,200 + 120,000 = 127,200 gates and B uses 60 × 1,200 + 4,000 = 76,000.
C. In the query model only calls count, and A makes 6 against B’s 60. B wins only once every gate is counted: 76,000 against 127,200.
D. That swaps the two counts. Calls: A 6, B 60. Gates in all: A 127,200, B 76,000.

Check yourself

Bernstein–Vazirani with $n = 3$ . Right after the call, the eight input branches $\ket{000}, \ket{001}, \ldots, \ket{111}$ carry the signs $(+,\ -,\ -,\ +,\ -,\ +,\ +,\ -)$ , in that order. Which string $s$ is hidden?

A $001$
B $111$
C $000$
D $010$

Hints

The sign on $\ket{x}$ is $(-1)^{s\cdot x}$ . Which inputs $x$ make $s\cdot x$ equal to a single bit of $s$ ?
At $x = 100$ the sign is $(-1)^{s_1}$ ; at $010$ , $(-1)^{s_2}$ ; at $001$ , $(-1)^{s_3}$ .

Show the answer

Answer: B. $111$

The signs at the inputs with a single 1 spell out $s$ : $x = 100$ has $-$ , $x = 010$ has $-$ , $x = 001$ has $-$ , so $s = 111$ . Check one more: at $x = 111$ the sign is $(-1)^{s_1\oplus s_2\oplus s_3} = -1$ , as listed.

Why not the others

A. The pattern of $001$ has the sign $+$ at $x = 100$ , but this one has $-$ there. The signs at $100$ , $010$ and $001$ give $s_1$ , $s_2$ , $s_3$ .
C. A minus sign means $s\cdot x = 1$ . At $x = 100$ the sign is $-$ , so $s_1 = 1$ : read $-$ as 1 and $+$ as 0.
D. The pattern of $010$ has the sign $+$ at $x = 100$ , but this one has $-$ there. The signs at $100$ , $010$ and $001$ give $s_1$ , $s_2$ , $s_3$ .

Check yourself

The same box, hiding an 8-bit string $s$ , is now a quantum oracle, $U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus s\cdot x}$ , which you may call on a superposition of inputs, with any gates before and after. What is the fewest calls that can find $s$ with certainty?

A $1$
BAbout $\sqrt{8}$ : a quantum computer gives a square-root saving
C $8$ : each call still answers with one bit
DNo number of calls gives certainty: quantum measurements are random

Show the answer

Answer: A. $1$

One call. Hadamards on the inputs, one call with the target in $\ket-$ , and Hadamards again leave the inputs in $\ket{s}$ , so measuring them gives all 8 bits of $s$ with certainty.

Why not the others

B. A square-root saving is what Grover’s search gives on problems with no structure to exploit. Here $f$ is linear in $x$ , and that structure lets one call reveal all of $s$ .
C. The answer bit isn’t where the information goes. With the target in $\ket-$ , one call writes the sign $(-1)^{s\cdot x}$ onto every input branch, and Hadamards turn that sign pattern into $\ket{s}$ : the 8 input qubits carry all of $s$ out.
D. A measurement is certain when the state is a basis state, as at the end of Deutsch–Jozsa for a constant $f$ . Here the circuit ends with the inputs in $\ket{s}$ , so the result is $s$ every time.

Check yourself

Complete Bernstein–Vazirani for $s = 101$ . The top three wires are $x_1, x_2, x_3$ and the bottom wire is the target, which starts in $\ket1$ ; the Hadamards are in place. Put the oracle in the empty columns, so that the inputs end in $\ket{101}$ . A control dot and an $X$ in the same column make a CNOT; give each CNOT its own column.

Build it in the circuit builder (gates: control, X).

Show the answer

One circuit that works: H on q0, q1, q2 and q3, then CNOT q0→q3, then CNOT q2→q3, then H on q0, q1 and q2.

$f(x) = s\cdot x$ adds up the bits $x_1$ and $x_3$ , so the oracle is one CNOT from each of them into the target. Each kicks a minus sign back onto its control, which turns its $\ket+$ into $\ket-$ , and the last Hadamards read $101$ .

For $s = 101$ the oracle needs 2 CNOTs, from $x_1$ and $x_3$ into the target, each in its own column. With the target in $\ket-$ , each CNOT turns its control from $\ket+$ into $\ket-$ . The last Hadamards give $\ket{101}\ket-$ , so the inputs read $101$ .

Check yourself

A Bernstein–Vazirani program on 4 input qubits puts a CNOT from qubits 1, 2 and 3 into the target, qubit 4, and measures qubit $k$ into classical bit $k$ for $k = 0, \ldots, 3$ . It runs 1000 shots. What do Qiskit’s counts show?

A{'0001': 1000}
BAbout 63 shots on each of the 16 strings
C{'0111': 1000}
D{'1110': 1000}

Show the answer

Answer: D. {'1110': 1000}

Qubits 1, 2 and 3 get a CNOT, so they read 1 and the rest read 0. In lesson order, qubit 0 first, that is $0111$ . Qiskit prints qubit 0 rightmost, so every shot shows 1110.

Why not the others

A. The qubits with a CNOT read 1, not 0. Each CNOT into the $\ket-$ target turns its control’s $\ket+$ into $\ket-$ , and $H\ket- = \ket1$ .
B. The last Hadamards don’t spread the shots out. They turn the sign pattern from the call into one basis state, so every shot gives the same string.
C. That writes qubit 0 first, as the kets in these lessons do. Qiskit prints qubit 0 as the rightmost bit, so the string comes out the other way round.

Check yourself

A headline reads: “Quantum computer finds a hidden 1000-bit string exponentially faster.” The algorithm is Bernstein–Vazirani. Which verdict is accurate?

AAccurate: the quantum call returns 1000 bits where a classical one returns 1, an exponential gain
BExaggerated: one query against 1000 is a factor of 1000, and the oracle itself costs up to 1000 CNOTs
CAccurate: a classical computer must try all $2^{1000}$ inputs
DFalse: the quantum algorithm needs 1000 runs as well, one per bit

Show the answer

Answer: B. Exaggerated: one query against 1000 is a factor of 1000, and the oracle itself costs up to 1000 CNOTs

Classically, 1000 queries find $s$ (the single-1 inputs), and no deterministic method needs fewer. Quantumly, one call. A factor of 1000 is a polynomial gap, and counting gates, the call itself is up to 1000 CNOTs. The exponential claim is wrong; the advantage is real but modest.

Why not the others

A. A gain of 1000 bits against 1 per query is a factor of 1000 in the number of queries. An exponential gap would be 1 query against something like $2^{1000}$ .
C. No need: the 1000 inputs with a single 1 give the 1000 bits of $s$ , one query each. The classical cost is 1000 queries, not $2^{1000}$ .
D. One run measures all 1000 input qubits, and every bit matches $s$ . The quantum advantage is real; it just isn’t exponential.

14 / 14 · Recap

Recap

From memory

Before reading the summary, write down what you remember. Pulling it back from memory is what makes it last.

What does the query model count, why is it useful, and what does it leave out?
Show the key points
- Only calls to the oracle; every other gate is free
- Lower bounds can be proved, and it shows where a speed-up comes from
- A real oracle is a circuit, and each call costs its gates
Describe the Bernstein–Vazirani circuit and why it returns $s$ .
Show the key points
- $H$ on all inputs and on a target in $\ket1$ ; one call; $H$ on the inputs; measure
- After the call the inputs hold $\tfrac{1}{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}\ket{x} = H^{\otimes n}\ket{s}$
- The last Hadamards undo the transform: the inputs are $\ket{s}$ , read with certainty
How is the oracle built, and how big is the quantum advantage?
Show the key points
- One CNOT from each input with $s_k = 1$ into the target; no work qubits
- Classically $n$ queries, one bit each, and no fewer; quantumly 1
- A polynomial gap, small in gates too; Simon’s algorithm uses the same pattern for an exponential one

Key ideas

The query model counts oracle calls only. It makes lower bounds provable and shows where a speed-up comes from, but a real oracle is a circuit whose gates cost too.
Bernstein–Vazirani: $f(x) = s\cdot x$ . Classically each query gives one bit, so $n$ queries are needed and enough.
Quantumly: Hadamards, one call with the target in $\ket-$ , Hadamards. The call leaves $H^{\otimes n}\ket{s}$ on the inputs, and the last Hadamards turn it into $\ket{s}$ .
The oracle is one CNOT per 1 in $s$ , into the target. Each turns its control from $\ket+$ into $\ket-$ , so the circuit can be traced qubit by qubit.
In Qiskit, qubit 0 is the rightmost bit of a result. The gap is $n$ queries against 1: polynomial, and a warm-up for Simon’s algorithm.

Go further

Free resources for when you want more than this lesson covers.

Fundamentals of quantum algorithms: The Deutsch–Jozsa algorithmJohn Watrous, IBM Quantum · Course
Goes on to solve the Bernstein–Vazirani problem with the same Hadamard-transform algebra as this lesson.
Decision tree modelWikipedia · Article
Defines deterministic, randomised and quantum query complexity, with the decision trees behind lower bounds like this lesson’s.
Lecture notes on quantum algorithmsAndrew Childs · Lecture notes
Graduate notes whose part on query complexity shows how lower bounds on the number of oracle calls are proved.
Bernstein–Vazirani algorithmWikipedia · Article
The problem, the classical method with n queries, the one-query circuit, and its original use: separating quantum from classical complexity.

Before you start

The query model

The hidden-string problem

Finding s one bit at a time

One query

Why the last Hadamards return s

Building the oracle

Worked example: qubit by qubit

Bernstein–Vazirani for s=101s = 101s=101

Another example: s=110s = 110s=110

Bernstein–Vazirani in Qiskit

How big is the gap?

Practice

Explain it

Mastery check

Recap

Key ideas

Go further

Bernstein–Vazirani for $s = 101$

Another example: $s = 110$