# Quantum Algorithms: Bernstein–Vazirani and Grover's Search

```elixir
Mix.install([
  {:qx, "~> 0.11", hex: :qx_sim},
  {:kino, "~> 0.12"},
  {:vega_lite, "~> 0.1.11"},
  {:kino_vega_lite, "~> 0.1.11"}
])
```

## Learning objectives

By the end of this tutorial you will be able to:

* Recognise the superposition → oracle → interference pattern as the skeleton shared by both algorithms
* Build a Bernstein–Vazirani circuit that recovers an $n$-bit secret string in a single oracle query
* Construct a phase oracle and Grover's diffusion operator, and run a complete search on a four-item space
* Predict the optimal number of Grover iterations and explain amplitude amplification as inversion about the mean
* Compare quantum and classical query counts, and say where the speed-up actually comes from

## Introduction

This is the sixth tutorial in the series, following **Preparing for Quantum Algorithms**. There we built the engine: an oracle packs a function into a reversible circuit, superposition spreads a register across every input, phase kickback stamps a data-dependent phase onto each one, and a layer of Hadamards interferes those phases into an answer. We even ran Deutsch's algorithm to see all the steps fire together.

Now we assemble that engine into two real algorithms. **Bernstein–Vazirani** recovers a hidden bit-string in a single query where any classical method needs one query per bit. **Grover's search** finds a marked item in an unstructured set of $N$ in about $\sqrt{N}$ steps, against the $N/2$ a classical scan averages. Both are the same three-step pattern with different oracles and a different amount of interference.

We work in circuits throughout. When it helps to watch the amplitudes between gates, `Qx.steps/2` replays the circuit one operation at a time and hands back the state after each.

**Prerequisites:** the first five tutorials in this series. You especially need phase kickback, the $\ket{-}$ ancilla trick, interference turning phases into outcomes, and the multi-qubit helpers `Qx.h_all`, `Qx.x_all`, and `Qx.measure_all` — each of which also accepts a list or range of qubits when you want to target only part of a register, a form this tutorial leans on.

## The pattern both algorithms share

Strip away the specifics and both algorithms are the same three moves:

1. **Superposition.** Apply $H^{\otimes n}$ so the input register holds all $2^n$ basis states at equal amplitude.
2. **Oracle.** A black-box circuit marks the inputs you care about by kicking back a phase $(-1)^{f(x)}$ onto each $\ket{x}$, using an ancilla in $\ket{-}$ or a controlled phase gate.
3. **Interference.** Bring the marked amplitudes back together so the answer concentrates onto the states you can measure.

Bernstein–Vazirani needs one pass through this loop. Grover repeats steps 2 and 3 until the marked state dominates. Everything below is a variation on these three lines.

## Bernstein–Vazirani: one query for the whole string

You are handed a black-box function $f : \{0,1\}^n \to \{0,1\}$ and promised it has the form

$$
f(x) = s \cdot x = s_0 x_0 \oplus s_1 x_1 \oplus \cdots \oplus s_{n-1} x_{n-1}
$$

for some hidden bit-string $s$. Your job is to find $s$. Classically each query returns a single parity bit, so you need at least $n$ queries: feed in $x = 100\ldots0$ to read $s_0$, then $010\ldots0$ for $s_1$, and so on. The quantum version reads the whole string in **one** query.

The mechanism is the kickback from the previous tutorial, run on $n$ input qubits at once. Put the input register in a uniform superposition and the ancilla in $\ket{-}$. The oracle, which XORs $s \cdot x$ into the ancilla, kicks back a phase instead:

$$
U_f\,\ket{x}\,\tfrac{1}{\sqrt{2}}(\ket{0}-\ket{1}) = (-1)^{s\cdot x}\,\ket{x}\,\tfrac{1}{\sqrt{2}}(\ket{0}-\ket{1})
$$

so the input register becomes $\tfrac{1}{\sqrt{2^n}}\sum_x (-1)^{s\cdot x}\ket{x}$. A second round of Hadamards turns that phase pattern into a single basis state:

$$
H^{\otimes n}\!\left(\tfrac{1}{\sqrt{2^n}}\sum_x (-1)^{s\cdot x}\ket{x}\right) = \ket{s}
$$

Measure, and every shot reads $s$. The oracle for $f(x) = s \cdot x$ is built from CNOTs: one from input qubit $i$ into the ancilla for every position where $s_i = 1$. Each CNOT adds $x_i$ to the running XOR in the ancilla, so the ancilla computes exactly $s \cdot x$.

Take $n = 4$ and a hidden string $s = 1011$ (so $s_0 = 1$, $s_1 = 0$, $s_2 = 1$, $s_3 = 1$, with qubit 0 on the left). The ancilla lives on qubit $n$ — and note the `0..n` range in `h_all` below includes it, so the same Hadamard layer that puts the inputs in $\ket{+}$ turns the freshly flipped ancilla into $\ket{-}$:

```elixir
n = 4
secret = [1, 0, 1, 1]

bv =
  Qx.create_circuit(n + 1, n)
  |> Qx.x(n)                       # ancilla → |1⟩
  |> Qx.h_all(0..n)                # inputs → |+⟩, ancilla → |−⟩
  |> Qx.barrier(0..n)              # superposition done
  |> then(fn qc ->
    secret
    |> Enum.with_index()
    |> Enum.reduce(qc, fn
      {1, i}, acc -> Qx.cx(acc, i, n)   # CNOT from input i into the ancilla
      {0, _i}, acc -> acc
    end)
  end)
  |> Qx.barrier(0..n)              # the one oracle query done
  |> Qx.h_all(0..(n - 1))          # interfere on the input register
  |> Qx.measure_all(0..(n - 1))    # measure the inputs, not the ancilla

Qx.draw_circuit(bv)
```

The two `Qx.barrier/2` calls are draw-only markers — like `h_all`, they take a range of qubits, and they change nothing in the simulation — but they cut the diagram at exactly the seams of the three-move skeleton: superposition on the left, the single oracle query in the middle, interference and measurement on the right. Now run it:

```elixir
Qx.draw_counts(Qx.run(bv, shots: 1024), title: "Bernstein–Vazirani — every shot reads 1011")
```

Every shot lands on `1011`, the secret, recovered in a single call to the oracle. The four input qubits each carried a superposition, the oracle phased them all in one pass, and interference snapped them onto $\ket{s}$.

**Try it:** change `secret` to any 4-bit list, for example `[0, 1, 1, 0]`, and rerun. The chart should read your string straight back. The classical approach would have queried the box four times to learn the same thing.

## Grover's search: amplifying the answer

Bernstein–Vazirani won by reading a global property in one shot. Grover's search tackles a harder job: find the one marked item in an unstructured set of $N = 2^n$, where the only tool is an oracle that says "yes" on the target and "no" everywhere else. Classically you can do no better than checking items one by one, $N/2$ on average. Grover finds it in about $\tfrac{\pi}{4}\sqrt{N}$ steps.

A single pass is not enough here, because one phase mark on one of $N$ states barely moves the measurement probabilities. Grover's idea is to repeat two operations that, together, pump amplitude toward the target:

* **The oracle** flips the *phase* of the marked state, leaving the rest alone.
* **The diffusion operator** reflects every amplitude about their collective mean, which turns the oracle's small phase dent into a real gain in probability.

Work with $n = 2$, so $N = 4$ and we search for the marked state $\ket{11}$. The oracle that phase-flips $\ket{11}$ is just a controlled-$Z$, since $CZ$ multiplies the amplitude by $-1$ exactly when both qubits are $\ket{1}$. Watch it mark the target, one gate at a time:

```elixir
# Uniform superposition, then the oracle flips the phase of |11⟩
Qx.create_circuit(2)
|> Qx.h(0)
|> Qx.h(1)
|> Qx.cz(0, 1)
|> Qx.steps()
|> Enum.to_list()
```

Each line is one executed gate with the state right after it. The two Hadamards spread the amplitude evenly, and the final step reads $0.5\ket{00} + 0.5\ket{01} + 0.5\ket{10} - 0.5\ket{11}$: four equal magnitudes, with $\ket{11}$ now carrying a minus sign. On its own this is invisible to a measurement: all four probabilities are still $0.25$. The diffusion operator is what converts that lone minus sign into a tall bar.

Diffusion reflects each amplitude about the mean of all of them. After the oracle the amplitudes are $\tfrac{1}{2}, \tfrac{1}{2}, \tfrac{1}{2}, -\tfrac{1}{2}$, whose mean is $\tfrac{1}{4}$. Reflecting each value $a$ to $2\bar{a} - a$ sends the three unmarked amplitudes to $2(\tfrac14) - \tfrac12 = 0$ and the marked one to $2(\tfrac14) - (-\tfrac12) = 1$:

$$
\tfrac{1}{2},\ \tfrac{1}{2},\ \tfrac{1}{2},\ -\tfrac{1}{2} \quad\xrightarrow{\text{reflect about } \bar{a}=\tfrac14}\quad 0,\ 0,\ 0,\ 1
$$

The marked state absorbs all the probability. Qx has no single "diffusion" gate, so we build it from the standard sandwich $H^{\otimes n} X^{\otimes n}\,CZ\,X^{\otimes n} H^{\otimes n}$, which implements exactly that reflection.

Why the sandwich works is a two-step story. The core, $X^{\otimes n}\,CZ\,X^{\otimes n}$, flips the phase of $\ket{0\ldots0}$ alone — the first $X$ layer ferries $\ket{0\ldots0}$ onto $\ket{1\ldots1}$, the $CZ$ marks it, and the second $X$ layer ferries it back — so the core is a reflection about $\ket{0\ldots0}$. Conjugating by the outer Hadamards transports that reflection onto $H^{\otimes n}\ket{0\ldots0} = \ket{s}$, the uniform superposition, giving the operator $2\ket{s}\bra{s} - I$ — and a reflection about the uniform state is precisely "reflect every amplitude about the mean" written in gate language.

**Predict first:** for $N = 4$ the optimal count is $\tfrac{\pi}{4}\sqrt{4} \approx 1.57$, rounded to one iteration. With a single oracle-plus-diffusion round, what probability should $\ket{11}$ get? Build the circuit and look at its shape first:

```elixir
grover =
  Qx.create_circuit(2, 2)
  |> Qx.h_all()          # uniform superposition over 4 states
  |> Qx.barrier(0..1)
  # Oracle: phase-flip the marked state |11⟩
  |> Qx.cz(0, 1)
  |> Qx.barrier(0..1)
  # Diffusion: reflect about the mean
  |> Qx.h_all()
  |> Qx.x_all()
  |> Qx.cz(0, 1)
  |> Qx.x_all()
  |> Qx.h_all()
  |> Qx.measure_all()

Qx.draw_circuit(grover)
```

The barriers split the wire diagram at the seams: superposition on the left, the phase-flip oracle between the barriers, and the diffusion sandwich plus measurement on the right. Everything after the first barrier — one oracle, one diffusion — is the unit Grover repeats. Run it:

```elixir
Qx.draw_counts(Qx.run(grover, shots: 1024), title: "Grover — |11⟩ found in one iteration")
```

Every shot reads `11`. For a four-item search, one Grover iteration is enough to reach the target with certainty. To search for a different item, wrap the oracle's $CZ$ in $X$ gates on the qubits that should read $0$: bracketing qubit 1 with $X$ before and after the $CZ$, for instance, marks $\ket{10}$ instead.

A word of caution that surprises people: more iterations are not better. Grover rotates the state toward the target by a fixed angle each round, so past the optimal count it rotates *past* the answer and the success probability falls again. For large $N$ the optimal number of rounds grows like $\sqrt{N}$, which is the whole speed-up.

**Try it:** duplicate the oracle-plus-diffusion block — the oracle's `Qx.cz(0, 1)` line and the five diffusion lines — just before `Qx.measure_all`, so the circuit runs two rounds, and rerun. $\ket{11}$ falls from every shot to about one in four, and the four bars come back near-uniform. The success probability after $k$ rounds is $\sin^2\bigl((2k+1)\theta\bigr)$ with $\sin\theta = 1/\sqrt{N}$; for $N = 4$ that makes $\theta = 30°$, so $k = 1$ gives $\sin^2 90° = 1$ and $k = 2$ gives $\sin^2 150° = \tfrac{1}{4}$ — the second round rotates the state straight past the target.

## How big is the win

Line the two algorithms up against their classical counterparts and the pattern is clear.

| Problem                                        | Classical queries  | Quantum queries                                    |
| ---------------------------------------------- | ------------------ | -------------------------------------------------- |
| Bernstein–Vazirani: learn an $n$-bit string    | $n$                | $1$                                                |
| Grover: find $1$ marked item among $N$         | $N/2$ on average   | $\lfloor \tfrac{\pi}{4}\sqrt{N} \rfloor$           |
| Grover at $N = 2^{20}$ (about a million items) | $\sim\!524{,}288$  | $\sim\!804$                                        |

The last row is the quadratic speed-up made concrete: it turns a million-step search into a thousand-step one.

Both wins come from the same place, and that place is easy to mistake. The register holds $2^n$ states at once, but it does not hand you $2^n$ answers: a measurement still returns a single outcome, as it has since the measurement tutorial. The advantage comes from arranging the phases so that interference cancels the outcomes you do not want before you ever measure. Superposition sets the stage; interference does the work.

### From simulator to real hardware

The `grover` circuit you built is not tied to the simulator: `Qx.to_qasm/1` emits it as OpenQASM 3.0, the lingua franca that cloud QPUs consume, measurements and all. Real devices each speak their own native gate set, and the Qx Portal's transpilation services adapt a circuit like this one to a specific device's gates.

```elixir
grover |> Qx.to_qasm() |> IO.puts()
```

That text block is your search algorithm, ready to leave the notebook.

## Summary

* **Both algorithms share one skeleton:** superposition with $H^{\otimes n}$, an oracle that kicks back phases, and interference that concentrates the answer onto measurable states.
* **Bernstein–Vazirani** recovers an $n$-bit secret in a single query by reading the phase pattern $(-1)^{s\cdot x}$ back into the basis state $\ket{s}$ with a second round of Hadamards.
* **Grover's search** alternates a phase-flip oracle with a diffusion operator that reflects amplitudes about their mean, amplifying the marked state in about $\tfrac{\pi}{4}\sqrt{N}$ rounds.
* **The speed-up comes from interference.** A measurement still yields a single outcome; the algorithm wins by arranging phases so the wrong answers cancel before you measure.

### What's next

A natural continuation is the **Quantum Fourier Transform** and **phase estimation**, the interference circuit that reads an eigenvalue out of a register and the backbone of Shor's factoring algorithm. The same three moves return there in a richer form, with controlled rotations replacing the plain Hadamards of the interference step.