# Ancillas, Uncomputation, and Reusable Circuit Blocks

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

```elixir
Qx.version()
```

## Learning objectives

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

* Build an oracle for a predicate that needs a working qubit: compute the value with a Toffoli, phase-mark it with a $Z$, then put the working qubit back
* Explain why a working qubit left holding data destroys the interference an algorithm depends on, and recognise the quiet, partial form of that failure
* Apply the compute–use–uncompute discipline so every borrowed qubit returns to $\ket{0}$
* Write circuit-to-circuit blocks parameterised by qubit index and compose them with `Enum.reduce`, so a construction scales past the hand-written two-qubit case
* Build the adjoint of a block by reversing its gate order and daggering each gate, and check it against the block it undoes

## Prerequisites

The first five tutorials. You especially need, from **Preparing for Quantum Algorithms**: the Toffoli gate as a reversible AND, the $U_f$ shape that keeps the input and XORs the answer into an ancilla, interference turning a phase pattern into an outcome, and the habit of checking an oracle against its truth table. The $\ket{-}$ ancilla and phase kickback are worth having fresh too — not because this tutorial uses them, but because it phase-marks a different way, with a plain $Z$ on a $\ket{0}/\ket{1}$ ancilla, and the contrast is the point.

## Introduction

Every oracle you have built so far fit in a single layer of gates. Deutsch's four oracles were one CNOT and one $X$ between them; the doubling oracle was two CNOTs. Nothing had to be worked out in stages, so nothing needed anywhere to put a partial result.

Real predicates are not like that. The moment a function has to compute "$a$ and $b$, and then that result and $c$", it needs somewhere to hold the intermediate value — a **working qubit**, or *ancilla*, borrowed from the register for the duration. That is unremarkable classically. On a quantum computer it is a trap, because a working qubit still holding an intermediate result stays entangled with the inputs, and entanglement with anything outside the interference pattern is exactly what stops the interference from happening.

This tutorial follows that thread end to end: build an oracle that genuinely needs scratch space, watch it break the algorithm around it, fix it by *uncomputing*, and then notice that uncomputing is a special case of something more general — applying the adjoint of a block. That last step is what turns a pile of gates into quantum code you can reuse.

## An oracle for a real predicate

Take the predicate $f(x_0, x_1) = x_0 \wedge x_1$, true only for the input $11$, and build the phase oracle a search algorithm wants: one that leaves every basis state alone except $\ket{11}$, whose amplitude it multiplies by $-1$.

You already have the pieces. A Toffoli computes the AND into a working qubit, and a $Z$ on that qubit applies a $-1$ exactly when it holds $1$. Three gates:

```elixir
# The two helpers from the previous tutorial: load a classical input, and
# read a deterministic circuit's outcome back as a label. `load` is
# unchanged; `read` now takes the qubits to measure, since this tutorial
# reads registers that are only part of the circuit.
load = fn qc, bits ->
  bits
  |> Enum.with_index()
  |> Enum.reduce(qc, fn
    {1, i}, acc -> Qx.x(acc, i)
    {0, _i}, acc -> acc
  end)
end

read = fn qc, qubits ->
  qc
  |> Qx.measure_all(qubits)
  |> Qx.run(shots: 1)
  |> Qx.SimulationResult.most_frequent()
  |> elem(0)
end

Qx.create_circuit(3)
|> Qx.h_all([0, 1])
|> Qx.ccx(0, 1, 2)     # compute:   q2 ← x₀ ∧ x₁
|> Qx.z(2)             # use:       phase −1 iff q2 holds 1
|> Qx.ccx(0, 1, 2)     # uncompute: q2 back to |0⟩
|> Qx.draw_circuit()
```

Qubit 2 is the working qubit. It is borrowed, written to, read from by the $Z$, and then handed back — the third gate is the second gate's undoing, because a Toffoli applied twice is the identity ($f(x) \oplus f(x) = 0$).

Check it against its truth table first, as always. The phase itself is invisible to a measurement, so what the sweep checks is the other half of the contract: that every input leaves qubit 2 back at $0$.

```elixir
for x0 <- [0, 1], x1 <- [0, 1] do
  out =
    Qx.create_circuit(3, 3)
    |> load.([x0, x1])
    |> Qx.ccx(0, 1, 2)
    |> Qx.z(2)
    |> Qx.ccx(0, 1, 2)
    |> read.(0..2)

  {[x0, x1], out}
end
```

`000`, `010`, `100`, `110`. Third character zero on every row: the working qubit is clean for every input, including $11$ where it did hold a $1$ in the middle of the circuit.

Now the phase. Feed the oracle a uniform superposition and replay it gate by gate:

```elixir
Qx.create_circuit(3)
|> Qx.h_all([0, 1])
|> Qx.ccx(0, 1, 2)
|> Qx.z(2)
|> Qx.ccx(0, 1, 2)
|> Qx.steps()
|> Enum.to_list()
```

The final step holds $\ket{000}$, $\ket{010}$ and $\ket{100}$ at amplitude $\tfrac12$, and $\ket{110}$ at $-\tfrac12$. They print as `0.4999999701976776` rather than `0.5`: Qx simulates in single-precision complex numbers, so exact values arrive a few parts in ten million off. Read amplitudes with that tolerance throughout. Reading the first two characters as the input and the third as the working qubit: all four inputs are present at equal magnitude, the working qubit is $0$ in every one of them, and $\ket{11}$ carries the minus sign. That is precisely a phase oracle for $x_0 \wedge x_1$.

> **A note on the next tutorial.** In **Bernstein–Vazirani and Grover's Search** this same oracle appears as a single `Qx.cz(0, 1)`. That shortcut is correct — $CZ$ phase-flips $\ket{11}$ and nothing else — but it works only because this particular predicate happens to *be* a two-qubit gate Qx already has. The compute–use–uncompute circuit above is the general construction, and the one that survives contact with a predicate nobody built a gate for.

## The garbage problem

An oracle is never run on its own. Something downstream turns the phase it wrote into a measurable answer, and for a search that something is the **diffusion operator**: a five-layer block that reflects every amplitude about their collective mean, converting a lone minus sign into a tall bar. The next tutorial derives it. Borrow it here as a finished block — it is the consumer that makes the oracle's phase visible, and its own first appearance as a reusable circuit-to-circuit function:

```elixir
diffusion = fn qc ->
  qc
  |> Qx.h_all([0, 1])
  |> Qx.x_all([0, 1])
  |> Qx.cz(0, 1)
  |> Qx.x_all([0, 1])
  |> Qx.h_all([0, 1])
end
```

Oracle then diffusion, on two qubits, should find $\ket{11}$ with certainty. Now ask what happens if the oracle skips its last gate — if the working qubit is left holding $x_0 \wedge x_1$ instead of being handed back.

Nothing raises. That is the whole difficulty. The circuit is still a perfectly legal unitary; it simply computes something other than what you meant, and it does it quietly.

**Predict first:** with the uncompute removed, how much of the probability still lands on `11` — all of it, none of it, or something in between? Three versions, measuring only the two input qubits:

```elixir
clean =
  Qx.create_circuit(3, 2)
  |> Qx.h_all([0, 1])
  |> Qx.ccx(0, 1, 2)
  |> Qx.z(2)
  |> Qx.ccx(0, 1, 2)
  |> then(diffusion)
  |> Qx.measure_all(0..1)

# identical, minus the uncompute
partial_garbage =
  Qx.create_circuit(3, 2)
  |> Qx.h_all([0, 1])
  |> Qx.ccx(0, 1, 2)
  |> Qx.z(2)
  |> then(diffusion)
  |> Qx.measure_all(0..1)

# working qubit cleaned up, but the inputs were copied out to q3 and q4
total_garbage =
  Qx.create_circuit(5, 2)
  |> Qx.h_all([0, 1])
  |> Qx.cx(0, 3)
  |> Qx.cx(1, 4)
  |> Qx.ccx(0, 1, 2)
  |> Qx.z(2)
  |> Qx.ccx(0, 1, 2)
  |> then(diffusion)
  |> Qx.measure_all(0..1)

Kino.Layout.grid(
  [
    Qx.draw_counts(Qx.run(clean, shots: 1024), title: "A — uncomputed: |11⟩ every shot"),
    Qx.draw_counts(Qx.run(partial_garbage, shots: 1024), title: "B — garbage left: |11⟩ about 5/8"),
    Qx.draw_counts(Qx.run(total_garbage, shots: 1024), title: "C — inputs copied out: flat")
  ],
  columns: 3
)
```

Three shapes, and the middle one is the lesson.

| Panel | What the circuit does | $P(\texttt{11})$ | Each other outcome |
| ----- | --------------------- | ---------------- | ------------------ |
| A     | compute, use, uncompute | $1$            | $0$                |
| B     | uncompute omitted       | $\tfrac58 = 0.625$ | $\tfrac18 = 0.125$ |
| C     | inputs copied to two more qubits | $\tfrac14$ | $\tfrac14$    |

Panel A is one bar. Panel C is four equal bars — the algorithm has been reduced to guessing, no better than picking one of the four inputs at random. Sampling noise means your charts will land a percent or two off these exact values.

Panel B is the one worth staring at. It is not broken. `11` is still by far the most likely outcome, still twice as likely as it would be by chance, and if you ran this circuit a handful of times you would see the right answer and conclude it worked. It is *degraded* — and quietly, which is far more dangerous than a crash. Uncomputation bugs survive casual testing precisely because they leave the algorithm mostly working.

Why it degrades rather than dies: after the missing uncompute, the working qubit still holds $x_0 \wedge x_1$, so it is $\ket{1}$ on the $\ket{11}$ branch and $\ket{0}$ on the other three. The register is entangled, and diffusion — acting only on qubits 0 and 1 — now reflects each of those two groups about its *own* mean rather than one shared mean. The interference that was supposed to cancel three amplitudes to zero only partly happens.

Panel C shows the endpoint. The extra CNOTs copy each input onto its own qubit, so *every* input branch is distinguishable from every other by something outside the interference. There is no cancellation left at all, and the distribution is flat.

The rule that falls out of this:

> **Every qubit a block borrows must be returned to $\ket{0}$ before the algorithm interferes.** Not "usually", and not "before measurement" — before the interference step, which is where the damage is done.

## Subroutines: blocks you can point at any qubits

`diffusion` above was already the right shape: a function taking a circuit and returning a circuit. But it hardcodes qubits 0 and 1, so it does exactly one thing forever. Take the qubit indices as arguments instead — `fn qc, qubits -> ... end` — and the same code becomes a component; the next tutorial does exactly that to run Grover over eight items.

Here is the payoff, and the answer to the obvious next question — what about an AND of three inputs, or five? There is no gate for it, but there is a construction: chain Toffolis through a ladder of working qubits, each one ANDing the next input against the running result.

```elixir
defmodule Blocks do
  @doc """
  AND every input qubit together, leaving the result on the last scratch qubit.
  Needs one fewer scratch qubit than it has inputs.
  """
  def and_all(qc, [a, b | rest], scratch) do
    rest
    |> Enum.with_index()
    |> Enum.reduce(Qx.ccx(qc, a, b, hd(scratch)), fn {input, k}, acc ->
      Qx.ccx(acc, input, Enum.at(scratch, k), Enum.at(scratch, k + 1))
    end)
  end

  @doc "Undo `and_all/3`: the same Toffolis, applied in reverse order."
  def unand_all(qc, [a, b | rest], scratch) do
    rest
    |> Enum.with_index()
    |> Enum.reverse()
    |> Enum.reduce(qc, fn {input, k}, acc ->
      Qx.ccx(acc, input, Enum.at(scratch, k), Enum.at(scratch, k + 1))
    end)
    |> Qx.ccx(a, b, hd(scratch))
  end
end
```

The first Toffoli ANDs the first two inputs into the first scratch qubit; each later input is ANDed against that running result and written one scratch qubit further along. Three inputs on qubits 0, 1, 2 with scratch on 3 and 4:

```elixir
Qx.create_circuit(5, 5)
|> load.([1, 1, 1])
|> Blocks.and_all([0, 1, 2], [3, 4])
|> Qx.draw_circuit()
```

Truth table, all eight inputs, reading the last character — the final scratch qubit:

```elixir
for x0 <- [0, 1], x1 <- [0, 1], x2 <- [0, 1] do
  out =
    Qx.create_circuit(5, 5)
    |> load.([x0, x1, x2])
    |> Blocks.and_all([0, 1, 2], [3, 4])
    |> read.(0..4)

  {[x0, x1, x2], out}
end
```

Only `111` ends in a `1`, as an AND should. Notice `110 -> 11010`: the *first* scratch qubit — the one holding the intermediate $x_0 \wedge x_1$ — came out set, because $x_0 \wedge x_1$ really was true. That is intermediate garbage, sitting in the register in exactly the state the previous section showed is fatal — and `and_all` has no idea, because it cannot know when you are finished with the result.

That is the contract a composable block has to publish: which qubits it borrows, what it leaves on them, and how to get them back. Which is what `unand_all` is for.

## Adjoints: how to undo a block

Undoing a block is not a special trick. Every quantum circuit is a unitary $U$, and every unitary has an inverse $U^\dagger$ that is also a circuit. For a block built from gates $G_1, G_2, \ldots, G_n$ applied in that order,

$$
(G_n \cdots G_2 G_1)^\dagger = G_1^\dagger G_2^\dagger \cdots G_n^\dagger
$$

so the recipe is two rules, and the first one is the one people forget: **reverse the order, then dagger each gate.**

Some gates are their own dagger — $H$, $X$, $Y$, $Z$, $CNOT$, $CZ$, and the Toffoli — which is why `unand_all` is just `and_all`'s Toffolis in reverse, and why the oracle at the top of this tutorial could uncompute with a literal repeat of its compute gate. Others come in pairs: `Qx.s/2` with `Qx.sdg/2`, `Qx.t/2` with `Qx.tdg/2`, and any rotation with the negation of its angle.

Watch both rules on a block where they bite:

```elixir
prep = fn qc, q -> qc |> Qx.h(q) |> Qx.t(q) |> Qx.s(q) end

# the block is h, t, s — reverse it to s, t, h, then dagger each: sdg, tdg, h
unprep = fn qc, q -> qc |> Qx.sdg(q) |> Qx.tdg(q) |> Qx.h(q) end

back_to_zero =
  Qx.create_circuit(1)
  |> prep.(0)
  |> unprep.(0)
  |> Qx.get_probabilities()

# same three daggered gates, but applied in the block's original order
wrong_order =
  Qx.create_circuit(1)
  |> prep.(0)
  |> Qx.h(0)
  |> Qx.tdg(0)
  |> Qx.sdg(0)
  |> Qx.get_probabilities()

{Nx.to_flat_list(back_to_zero), Nx.to_flat_list(wrong_order)}
```

The first list reads `[0.9999998807907104, 1.776356733521132e-15]`, which at the single-precision tolerance noted earlier is $1$ and $0$: the qubit is back in $\ket{0}$ and the block has been erased.

The second list is `[0.1464465856552124, 0.8535533547401428]` — nowhere near $\ket{0}$, and not a rounding question. The three gates were individually the right daggers; only the order was wrong. The qubit is left in a state that will entangle with whatever comes next just as surely as an uncomputed ancilla would.

Now apply the rule to the ladder. `unand_all` should leave the scratch qubits at $0$ for every input, while the inputs themselves come through untouched:

```elixir
for x0 <- [0, 1], x1 <- [0, 1], x2 <- [0, 1] do
  out =
    Qx.create_circuit(5, 5)
    |> load.([x0, x1, x2])
    |> Blocks.and_all([0, 1, 2], [3, 4])
    |> Blocks.unand_all([0, 1, 2], [3, 4])
    |> read.(0..4)

  {[x0, x1, x2], out}
end
```

Every row ends in `00`, including `110 -> 11000` where the first scratch qubit had been set. The inputs are unchanged in every row. That is a block and its adjoint composing to the identity — the same thing the oracle's two Toffolis were doing, now with the general rule behind it.

In practice a subroutine sandwiches its payload between the two: `and_all`, then whatever uses the result, then `unand_all`. Compute, use, uncompute — the shape this tutorial opened with, and the shape every ancilla-using quantum subroutine has.

Qx has no function that takes a block and hands you its inverse; there is no circuit introspection API to build one on. So adjoints are written by hand, as a pair, and the discipline is to write them together and check them together — a sweep like the one above, run once, is cheap insurance against a bug that would otherwise show up as a merely *disappointing* success probability rather than an error.

## Summary

* **A predicate that needs intermediate results needs a working qubit**, and the oracle for it is three stages: compute the value into the ancilla, use it, then uncompute it.
* **A working qubit left holding data stays entangled with the inputs**, which splits the register into branches that interfere separately. The algorithm's cancellation stops working.
* **That failure is partial and quiet.** Leaving one ancilla dirty took $\ket{11}$ from certainty to $\tfrac58$ — still the top answer, still wrong. Copying the inputs out flattened it to $\tfrac14$, pure chance.
* **A reusable block is a circuit-to-circuit function parameterised by qubit index**, composed with ordinary Elixir. `Enum.reduce` over a ladder of Toffolis gives an AND of as many inputs as you like.
* **The adjoint of a block reverses its gate order and daggers each gate.** Self-inverse gates make that look like a repeat; the general rule is what keeps it correct when they aren't.

### What's next

In **Quantum Algorithms: Bernstein–Vazirani and Grover's Search** the diffusion operator borrowed here gets derived, and the oracle built in this tutorial gets used in anger: a search over eight items, with the oracle and the diffusion both written as parameterised blocks so the same code runs at any register size.