# Preparing for Quantum Algorithms

## Section

```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 a quantum function as a reversible oracle that keeps its input and writes the answer into an ancilla, and say why a classical truth table can't be dropped into a circuit
* Run a doubling function $f(x) = 2x$ on a classical input, then on a superposition, and read both the parallelism and its catch straight off the measurement counts
* Describe the black-box (query) model and why we count an algorithm's cost in oracle calls
* Use a Hadamard to turn an invisible phase into a measurement outcome: interference
* Prime an ancilla in $\ket{-}$ so a controlled gate kicks a phase back onto its control: phase kickback
* Wire all of it into Deutsch's algorithm and decide constant-versus-balanced in a single query

## Prerequisites

The first four tutorials in this series. You should be comfortable with the $X$, $H$, and $Z$ gates, with superposition and how $\ket{+}$ and $\ket{-}$ differ by a phase, with the $\ket{0}/\ket{1}$ measurement convention, and with CNOT acting on two qubits.

## Introduction

This is the fifth tutorial in the series, following **Systems of Qubits and Entanglement**. You can now build superposition and entangle qubits. Useful, but neither one is where a quantum algorithm gets its edge.

This tutorial assembles the parts that every algorithm ahead shares. We'll see how a function becomes a circuit, how one oracle call can act on every input at once, and how interference and phase kickback turn that into an answer you can actually measure. The payoff is **Deutsch's algorithm**, the smallest problem a quantum computer solves with fewer queries than any classical one.

We build everything with `Qx.create_circuit` and the top-level `Qx.*` functions. When we want to read amplitudes before a measurement hides them, `Qx.steps/2` replays the circuit gate by gate and shows the state after each one.

## A function has to become reversible

Start with a classical gate. An AND takes two bits and returns one. Hand someone the output `0` and ask what went in, and they can't tell you: it might have been `00`, `01`, or `10`. The gate threw information away. That's fine for a logic chip, but a quantum gate can't do it.

Every quantum gate is a unitary, and unitaries are reversible. The same number of qubits comes out as went in, and you can always run the gate backwards to recover the input. So you can't compute $f(x)$ by overwriting $x$ with the answer. The information that made $x$ has to survive.

The standard fix keeps the input and writes the result into a separate output register, the **ancilla**, by XOR-ing it in:

$$
U_f \ket{x}\ket{y} = \ket{x}\,\ket{y \oplus f(x)}
$$

Set the ancilla to $\ket{0}$ and you read the answer cleanly, since $0 \oplus f(x) = f(x)$, giving $\ket{x}\ket{f(x)}$. The input $\ket{x}$ rides along untouched, which is exactly what makes the whole thing reversible. Apply $U_f$ a second time and the ancilla returns to $y$, because $f(x) \oplus f(x) = 0$. So $U_f$ is its own inverse.

Don't take the reversibility on faith; inspect it. Here is $U_f$ for the one-bit function $f(x) = x$, with each row an input pair $(x, y)$ going in and the pair $(x,\, y \oplus f(x))$ coming out:

| $x$ | $y$ | $y \oplus f(x)$ |
| --- | --- | --------------- |
| $0$ | $0$ | $0$             |
| $0$ | $1$ | $1$             |
| $1$ | $0$ | $1$             |
| $1$ | $1$ | $0$             |

Four distinct inputs, four distinct outputs, no two rows landing on the same $(x,\, y \oplus f(x))$ pair. Every output points back to exactly one input, so the map runs backwards without ambiguity. Contrast that with the AND gate that opened this section, where three different inputs piled onto the output `0` — that collision is precisely what the kept input and the ancilla eliminate.

This XOR-into-an-ancilla shape is how *every* function in the tutorials ahead gets packed into a circuit. Worth getting comfortable with it now.

## Quantum parallelism: doubling every input at once

Let's build a real one. Take $f(x) = 2x$ on a 2-bit input, so $x$ runs over $0,1,2,3$ and $2x$ runs over $0,2,4,6$. The outputs reach $6$, so the ancilla needs 3 bits.

Doubling a binary number just shifts its bits up one place. If $x = b_1 b_0$, then $2x = b_1 b_0 0$. So the oracle is two CNOTs: copy each input bit into the next-higher slot of the ancilla. No arithmetic, just rewiring.

We lay out 5 qubits. Qubits 0 and 1 hold $x$ (qubit 0 is the high bit). Qubits 2, 3, 4 hold the output with place values 4, 2, 1. Load a classical $x = 3$ and run it:

```elixir
# x = 3 is binary 11 on qubits 0,1; expect output 6 = binary 110 on qubits 2,3,4
double_3 =
  Qx.create_circuit(5, 5)
  |> Qx.x(0)
  |> Qx.x(1)        # load x = 3
  |> Qx.cx(0, 2)    # high bit of x -> the 4's place of the output
  |> Qx.cx(1, 3)    # low bit of x  -> the 2's place of the output
  |> Qx.measure_all()
IO.puts("function f(x) = 2x for x = 3")
```

Let's see what the circuit for our `double_3` function looks like. The two input qubits, $q_0$ and $q_1$, are the "x" in our f(x), and $q_2$, $q_3$, $q_4$ hold the result $2x$.

```elixir
Qx.draw_circuit(double_3)
```

```elixir
Qx.draw_counts(Qx.run(double_3, shots: 1024), title: "f(3) = 6")
```

Every shot reads `11110`. Split the label where the registers split: the first two bits `11` are the input $x = 3$, the last three `110` are the output $6$. The quantum circuit just did ordinary classical arithmetic: it doubled 3.

Now feed the *same* oracle a superposition. A Hadamard on each input qubit spreads $x$ across all four values at once, and a single call to the oracle acts on the whole spread:

```elixir
double_super =
  Qx.create_circuit(5, 5)
  |> Qx.h(0)
  |> Qx.h(1)        # x is now 0,1,2,3 all at once
  |> Qx.cx(0, 2)
  |> Qx.cx(1, 3)
  |> Qx.measure_all()

Qx.draw_counts(Qx.run(double_super, shots: 1024), title: "Every (x, 2x) pair from one oracle call")
```

Four bars, each near 25%: `00000`, `01010`, `10100`, `11110`. Read them in pairs and you get $(0,0)$, $(1,2)$, $(2,4)$, $(3,6)$. One pass through the oracle entangled every input with its own doubled output. Before measuring, the register sits in

$$
\tfrac{1}{2}\bigl(\ket{0}\ket{0} + \ket{1}\ket{2} + \ket{2}\ket{4} + \ket{3}\ket{6}\bigr).
$$

Here is the anatomy of each label. Qx prints qubit 0 leftmost, so the first two characters are the input register (qubit 0 is the high bit of $x$) and the last three are the output register with place values 4, 2, 1:

| Label   | Input bits (qubits 0–1) | $x$ | Output bits (qubits 2–4) | $2x$ |
| ------- | ----------------------- | --- | ------------------------ | ---- |
| `00000` | `00`                    | 0   | `000`                    | 0    |
| `01010` | `01`                    | 1   | `010`                    | 2    |
| `10100` | `10`                    | 2   | `100`                    | 4    |
| `11110` | `11`                    | 3   | `110`                    | 6    |

That qubit-0-leftmost reading applies to every counts chart in this series, so it's worth fixing in your head now — some other frameworks print the register in the opposite order, and mixing up the two conventions is the classic way to misread a chart.

Here's the catch, and it's the one that trips up everyone new to this. The oracle did compute $f$ on all four inputs in a single call. But measuring collapses that superposition to one pair, picked at random. You can't read all four results out. Quantum parallelism gives you a state that *contains* every answer; it doesn't hand you a printout of them.

So the breadth is real but locked away. The rest of this tutorial is about the key: interference, which turns that hidden breadth into a single answer worth measuring.

## Black-box problems

One more idea before the mechanics. Algorithms like Deutsch's are stated as **black-box** (or **query**) problems. You're handed the oracle $U_f$ as a sealed unit. You may run it on any state you like, but you can't peek inside to read off $f$.

The function hides some global property: maybe $f$ is constant, maybe it has a secret string buried in it. Your job is to learn that property, and the cost is counted in **queries**, the number of times you call the oracle. Fewer queries wins.

This framing is what makes the speed-ups sharp. When we say Deutsch's algorithm beats every classical method, we mean it answers the question in one oracle call where any classical approach needs two. Bernstein–Vazirani, Grover, and Simon are all phrased the same way.

## Interference: turning phase into an outcome

A relative phase hides from a measurement. The states $\ket{+}$ and $\ket{-}$ differ only by the sign on their $\ket{1}$ amplitude, yet both measure as a 50/50 coin toss. A phase you can't measure looks worthless. The trick is that a Hadamard converts phase into amplitude, and amplitude is what a measurement reads.

Trace a $Z$ between two Hadamards, starting from $\ket{0}$:

$$
\ket{0} \xrightarrow{H} \ket{+} \xrightarrow{Z} \ket{-} \xrightarrow{H} \ket{1}
$$

The middle $Z$ only flipped a phase, invisible to a measurement at that point. The second Hadamard turned that phase into the gap between $\ket{0}$ and $\ket{1}$. The whole sequence equals an $X$.

**Predict first:** the left circuit is two Hadamards and nothing else; the right one slips a $Z$ between them. What does each measure? Then run it:

```elixir
no_phase =
  Qx.create_circuit(1, 1)
  |> Qx.h(0)
  |> Qx.h(0)
  |> Qx.measure(0, 0)

with_phase =
  Qx.create_circuit(1, 1)
  |> Qx.h(0)
  |> Qx.z(0)
  |> Qx.h(0)
  |> Qx.measure(0, 0)

Kino.Layout.grid(
  [
    Qx.draw_counts(Qx.run(no_phase, shots: 1024), title: "H · H: back to |0⟩"),
    Qx.draw_counts(Qx.run(with_phase, shots: 1024), title: "H · Z · H: flipped to |1⟩")
  ],
  columns: 2
)
```

Same two Hadamards, opposite answers. The lone $Z$, useless on its own, decides everything once interference brings the amplitudes back together. That sensitivity to phase is the lever.

It scales past one qubit. Put two qubits into a uniform superposition, stamp a sign onto some of the basis states, and send the register back through the Hadamards. Watch the amplitudes after a $Z$ on qubit 0:

```elixir
# replay the circuit gate by gate and read the amplitudes directly
Qx.create_circuit(2)
|> Qx.h(0)
|> Qx.h(1)
|> Qx.z(0)
|> Qx.steps()
|> Enum.to_list()
```

The last step shows four equal magnitudes, but the states with qubit 0 in $\ket{1}$ now carry a minus sign. That sign is a phase pattern. Send it back through both Hadamards and the pattern decides which outcome survives:

```elixir
steered =
  Qx.create_circuit(2, 2)
  |> Qx.h_all()
  |> Qx.z(0)
  |> Qx.h_all()
  |> Qx.measure_all()

Qx.draw_counts(Qx.run(steered, shots: 1024), title: "Phase on qubit 0, then interfere")
```

Every shot reads `10`. The amplitudes for the other three outcomes didn't just shrink, they cancelled to zero, while `10` collected the whole amplitude. The factoring shows why: the first Hadamards spread $\ket{00}$ into $\tfrac{1}{2}(\ket{00} + \ket{01} - \ket{10} - \ket{11})$ after the $Z$, which is $\ket{-}$ on qubit 0 and $\ket{+}$ on qubit 1. The second Hadamards send $H\ket{-} = \ket{1}$ and $H\ket{+} = \ket{0}$, landing on $\ket{10}$ with certainty. Spread out, mark with a phase, interfere, read the answer. That's the skeleton of every algorithm ahead.

## Phase kickback: writing the phase from data

The interference demos assumed a phase was simply sitting there. A real algorithm has to *write* it, based on the data, and without a measurement that would collapse the superposition. The mechanism is **phase kickback**.

It rests on eigenstates. The state $\ket{-}$ is an eigenstate of $X$ with eigenvalue $-1$:

$$
X\ket{-} = \tfrac{1}{\sqrt{2}}\bigl(\ket{1} - \ket{0}\bigr) = -\ket{-}
$$

Prepare a control in $\ket{+}$ and a target in $\ket{-}$, then apply CNOT (a controlled $X$):

$$
\text{CNOT}\,\ket{+}\ket{-} = \tfrac{1}{\sqrt{2}}\bigl(\ket{0}\ket{-} + \ket{1}\,X\ket{-}\bigr) = \tfrac{1}{\sqrt{2}}\bigl(\ket{0} - \ket{1}\bigr)\ket{-} = \ket{-}\ket{-}
$$

The target came out untouched, still $\ket{-}$. But the control flipped from $\ket{+}$ to $\ket{-}$: the $-1$ eigenvalue rode back onto the control's $\ket{1}$ branch. The phase CNOT would normally write into the target got *kicked back* onto the control.

Read it out with a Hadamard on the control, the same phase-to-outcome trick. With the target in $\ket{-}$ the control ends on $\ket{1}$; with the target in $\ket{+}$ (eigenvalue $+1$) nothing kicks back and the control ends on $\ket{0}$:

```elixir
# target in |+⟩, eigenvalue +1, no kickback
no_kickback =
  Qx.create_circuit(2, 1)
  |> Qx.h(0)
  |> Qx.h(1)
  |> Qx.cx(0, 1)
  |> Qx.h(0)
  |> Qx.measure(0, 0)

# target in |−⟩, eigenvalue −1, the kickback flips the control
with_kickback =
  Qx.create_circuit(2, 1)
  |> Qx.h(0)
  |> Qx.x(1)
  |> Qx.h(1)
  |> Qx.cx(0, 1)
  |> Qx.h(0)
  |> Qx.measure(0, 0)

Kino.Layout.grid(
  [
    Qx.draw_counts(Qx.run(no_kickback, shots: 1024), title: "target |+⟩: control reads 0"),
    Qx.draw_counts(Qx.run(with_kickback, shots: 1024), title: "target |−⟩: control reads 1")
  ],
  columns: 2
)
```

The two circuits differ only in how the target was prepared, yet the answer shows up on the control. The circuit never measured the target and never changed its value, and still pulled a $\pm 1$ out of it. That's how an oracle stamps $(-1)^{f(x)}$ onto a register without disturbing the data it computed from.

The whole mechanism fits in a table small enough to carry forward:

| Target prepared in | Eigenvalue under $X$ | Control after the final $H$ |
| ------------------ | -------------------- | --------------------------- |
| $\ket{+}$          | $+1$                 | reads `0`                   |
| $\ket{-}$          | $-1$                 | reads `1`                   |

The bottom row is the one every algorithm ahead leans on: prime an ancilla in $\ket{-}$, and each controlled operation deposits its $-1$ as a phase on the control side, where a Hadamard turns it into a readable outcome.

## Deutsch's algorithm

Now put the pieces together on a real problem. You're handed a black-box function $f:\{0,1\} \to \{0,1\}$. There are exactly four of them: the two **constant** functions ($f(x) = 0$ and $f(x) = 1$) and the two **balanced** ones ($f(x) = x$ and $f(x) = 1-x$, each returning $0$ once and $1$ once). Your question: is $f$ constant or balanced?

Classically you have no choice but to call the oracle twice, once for $f(0)$ and once for $f(1)$, and compare. One query tells you nothing about the global property. Deutsch's algorithm settles it in a **single** query.

The circuit is the whole tutorial in miniature. Put the input qubit in $\ket{+}$ and the ancilla in $\ket{-}$. Call the oracle once: kickback stamps $(-1)^{f(x)}$ onto each branch of the input. Then a Hadamard on the input interferes those phases, and a measurement reads the verdict:

$$
\ket{0} \xrightarrow{H} \tfrac{1}{\sqrt{2}}\bigl(\ket{0} + \ket{1}\bigr)
\xrightarrow{U_f} \tfrac{1}{\sqrt{2}}\bigl((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}\bigr)
$$

If $f$ is constant, both branches get the same sign, so the input is back in $\ket{+}$ and the final Hadamard returns $\ket{0}$. If $f$ is balanced, the branches get opposite signs, the input is now $\ket{-}$, and the Hadamard returns $\ket{1}$. So a measured `0` means constant and a measured `1` means balanced, every time.

Here are all four oracles, each XOR-ing $f(x)$ into the ancilla on qubit 1:

```elixir
defmodule Deutsch do
  # U_f |x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩, with input on qubit 0 and ancilla on qubit 1
  def constant_0(qc), do: qc                          # f(x) = 0: do nothing
  def constant_1(qc), do: Qx.x(qc, 1)                 # f(x) = 1: always flip the ancilla
  def identity(qc), do: Qx.cx(qc, 0, 1)               # f(x) = x
  def negation(qc), do: qc |> Qx.cx(0, 1) |> Qx.x(1)  # f(x) = 1 - x

  def run(oracle) do
    Qx.create_circuit(2, 1)
    |> Qx.x(1)            # ancilla -> |1⟩ ...
    |> Qx.h(1)           # ... -> |−⟩, primed for kickback
    |> Qx.h(0)           # input -> |+⟩
    |> oracle.()         # the one black-box query
    |> Qx.h(0)           # interfere the kicked-back phases
    |> Qx.measure(0, 0)  # 0 = constant, 1 = balanced
    |> Qx.run(shots: 1024)
  end
end
```

Before running all four, look at the machine itself. Here is the circuit for the `identity` oracle, drawn with `Qx.barrier/2` — a draw-only marker that takes a range of qubits and changes nothing in the simulation — slicing it at the seams of the three phases: prepare the $\ket{+}$ input and $\ket{-}$ ancilla, make the single query, then interfere and measure:

```elixir
Qx.create_circuit(2, 1)
|> Qx.x(1)
|> Qx.h(1)
|> Qx.h(0)
|> Qx.barrier(0..1)   # preparation done
|> Deutsch.identity() # the one black-box query
|> Qx.barrier(0..1)   # query done
|> Qx.h(0)
|> Qx.measure(0, 0)
|> Qx.draw_circuit()
```

The diagram is the whole tutorial in one picture: the XOR oracle from the first section sits between the kickback preparation on the left and the interference readout on the right. Now run all four oracles:

```elixir
Kino.Layout.grid(
  [
    Qx.draw_counts(Deutsch.run(&Deutsch.constant_0/1), title: "f(x) = 0: reads 0, constant"),
    Qx.draw_counts(Deutsch.run(&Deutsch.constant_1/1), title: "f(x) = 1: reads 0, constant"),
    Qx.draw_counts(Deutsch.run(&Deutsch.identity/1), title: "f(x) = x: reads 1, balanced"),
    Qx.draw_counts(Deutsch.run(&Deutsch.negation/1), title: "f(x) = 1 − x: reads 1, balanced")
  ],
  columns: 2
)
```

Both constant oracles read `0` on every shot, both balanced ones read `1`. One query each. The algorithm never learned $f(0)$ or $f(1)$ on their own; it asked the oracle a single superposed question and let interference report the property that spans both inputs.

## Summary

* **A quantum function is a reversible oracle.** It keeps the input and XORs the answer into an ancilla, $U_f\ket{x}\ket{y} = \ket{x}\ket{y \oplus f(x)}$, because unitaries can't throw information away.
* **One oracle call touches every input.** Feed it a superposition and it computes $f$ across all inputs at once, but a measurement still returns only one pair. Interference is the way out.
* **A Hadamard turns phase into outcome**, and an ancilla in $\ket{-}$ lets a controlled gate kick a data-dependent phase $(-1)^{f(x)}$ back onto the control without measuring the data.
* **Deutsch's algorithm** wires all of it together to decide constant-versus-balanced in a single query, where any classical method needs two.

### What's next

In the next tutorial, **Quantum Algorithms: Bernstein–Vazirani and Grover's Search**, you scale this engine up. Bernstein–Vazirani recovers an $n$-bit secret string in one query, and Grover's search uses repeated rounds of kickback and interference to amplify a marked item until a measurement almost always returns it.