Measurement Patterns

An MBQC algorithm is fully specified by a measurement pattern: a finite recipe of which qubits to prepare, how to entangle them, which single-qubit measurements to perform (and in what order), and how later choices depend on earlier outcomes. The measurement calculus of Danos, Kashefi and Panangaden gives this an exact algebra. This lesson introduces its four kinds of command and the bookkeeping that ties them together.

The four commands

A pattern is a sequence built from exactly four primitive commands, each labelled by the qubit(s) it acts on:

Preparation $N_i$ — initialise qubit $i$ in $|+\rangle$ .
Entanglement $E_{ij}$ — apply a controlled- $Z$ to the pair $(i, j)$ . The set of $E$ commands draws the graph of the underlying cluster state.
Measurement $M_i^{\xi}$ — measure qubit $i$ in the basis $\{|{+}_\xi\rangle, |{-}_\xi\rangle\}$ with $|{\pm}_\xi\rangle = \tfrac{1}{\sqrt2}(|0\rangle \pm e^{i\xi}|1\rangle)$ , recording the outcome $s_i \in \{0, 1\}$ .
Correction $X_i^{s}$ and $Z_i^{s}$ — apply a Pauli $X$ or $Z$ to qubit $i$ , raised to a power $s$ that is a known function of earlier outcomes.

A full pattern looks like a product read right to left (commands on the right happen first), for example

\mathcal{P} = \Big(\prod_i X_i^{\,?}Z_i^{\,?}\Big)\,\Big(\prod_j M_j^{\xi_j}\Big)\,\Big(\prod_{(k,l)\in E} E_{kl}\Big)\,\Big(\prod_m N_m\Big).

The qubits split into the input qubits (carrying the state to be processed), the output qubits (never measured, holding the answer), and everything in between (measured during the run).

Why measurements carry dependencies

Recall the elementary gadget: an outcome $s$ leaves a Pauli byproduct $X^{s}$ (or $Z^{s}$ ) on the next wire. If that wire is later measured at angle $\xi$ , a leftover $X^{s}$ in front of the measurement is not harmless, because $X$ does not commute with the tilted basis. Concretely,

M^{\xi} X^{s} = M^{(-1)^{s}\,\xi}, \qquad M^{\xi} Z^{s} = M^{\xi + s\pi} .

So an earlier $X$ byproduct flips the sign of a later measurement angle, and an earlier $Z$ byproduct shifts it by $\pi$ . These two rules are the heart of the measurement calculus. They mean a later measurement's effective angle depends on earlier outcomes, and we encode this with two outcome sets:

the $X$ -dependency set $s^{X}_j$ — outcomes that flip the sign of $\xi_j$ ;
the $Z$ -dependency set $s^{Z}_j$ — outcomes that shift $\xi_j$ by $\pi$ .

The measured qubit $j$ is then physically measured at the adapted angle

\xi_j' = (-1)^{s^{X}_j}\,\xi_j + s^{Z}_j\,\pi .

This adaptation is feed-forward, treated in detail next lesson; here the point is simply that the pattern records which earlier outcomes each angle depends on.

Flow: the guarantee that a pattern is runnable

Not every set of commands is a sensible algorithm. We need a consistent partial order on the measurements such that every dependency points backward in time — a qubit's angle may depend only on outcomes already obtained. The structural condition guaranteeing this is called flow (and its generalisation gflow): a map assigning to each non-output qubit a successor, with the dependency sets derived from it, such that the induced order is acyclic.

A worked specification: the Hadamard pattern

The smallest non-trivial pattern realises a Hadamard on a two-qubit line, input on qubit $1$ , output on qubit $2$ :

\mathcal{H} = X_2^{\,s_1}\; M_1^{0}\; E_{12}\; N_2 .

Reading right to left: prepare qubit $2$ in $|+\rangle$ ; entangle $(1,2)$ with $CZ$ ; measure qubit $1$ at angle $\xi = 0$ (the plain $X$ basis); finally apply $X^{s_1}$ to the output to cancel the byproduct. The result on qubit $2$ is $H|\psi\rangle$ , deterministically. Composing such tiles — feeding each output line into the next tile's input — builds arbitrary single-qubit unitaries, and adding cross-edges $E_{ij}$ between two lines builds entangling gates.

What a pattern is, in one sentence

A measurement pattern is a graph (which qubits, which $CZ$ edges), a list of measurement angles, a dependency structure telling each angle which earlier outcomes to fold in, and a final Pauli correction on the outputs. Equipped with flow, it is a complete, runnable, deterministic specification of a quantum computation — the MBQC analogue of a circuit diagram. The next lesson turns the dependency rules into the explicit feed-forward corrections that make it run.