Equivalence to the Circuit Model

The one-way model and the circuit model are equivalent in computational power: each can simulate the other with only polynomial overhead. This lesson states that equivalence precisely and sketches the constructions that establish it in both directions, so that MBQC inherits the universality of the circuit model and vice versa.

What "equivalent" means here

Two models of quantum computation are equivalent when any computation expressible in one can be carried out in the other using resources — qubits, gates or measurements, time steps — that grow at most polynomially in the size of the original. The claim is therefore twofold:

Circuit $\Rightarrow$ MBQC. Every quantum circuit on $n$ qubits with $g$ gates can be compiled into a measurement pattern on a cluster state of $O(n + g)$ qubits.
MBQC $\Rightarrow$ circuit. Every measurement pattern can be simulated by a circuit whose size is polynomial in the pattern's size.

Together these mean MBQC is exactly BQP-complete: it solves precisely the problems a quantum circuit can, no more and no less.

Circuit to pattern: compiling gates into measurements

The forward direction is constructive and was the original point of the model. Pick a universal gate set — say $\{H, R_z(\xi), CZ\}$ — and replace each gate with a small cluster tile:

A single-qubit gate $H R_z(\xi)$ becomes one teleportation gadget: an edge of the cluster measured in the tilted basis $M^{\xi}$ . Concatenating tiles along a horizontal line realises any single-qubit unitary as a product $H R_z(\xi_3) H R_z(\xi_2) H R_z(\xi_1)$ — the Euler-angle form an MBQC line produces naturally.
A two-qubit gate $CZ$ between logical wires becomes a vertical cross-edge connecting two horizontal lines, requiring no measurement of its own.

Laying the tiles on a two-dimensional lattice and threading each logical wire left to right turns the whole circuit into a single cluster state plus a list of measurement angles. The horizontal direction plays the role of circuit time; the vertical direction indexes the logical qubits. The cluster's size is linear in the circuit's gate count, establishing the $O(n+g)$ bound.

Pattern to circuit: simulating measurements with gates

The reverse direction is the easy one. A measurement pattern is built from the four commands $N$ , $E$ , $M$ , $X/Z$ . Each maps directly to circuit operations: $N_i$ is a state preparation, $E_{ij}$ is a $CZ$ gate, $M_i^{\xi}$ is a basis rotation $R_z(-\xi)$ followed by a Hadamard and a computational measurement, and the corrections are Pauli gates classically controlled on earlier outcomes. Since the number of commands is polynomial in the pattern size, the resulting circuit is too. Hence anything MBQC can do, a circuit can do.

Determinism despite randomness

A subtlety the equivalence must respect: an MBQC pattern produces random measurement outcomes, yet must realise a deterministic unitary to match a circuit. This is guaranteed exactly when the pattern has flow. Flow ensures every byproduct can be either folded into a later measurement angle (feed-forward) or removed by a final Pauli correction, so that the logical map from input to output is a fixed unitary — the same one for every branch of outcomes. A compiled circuit always yields a pattern with flow by construction, so determinism is automatic in the forward direction.

Consequences of the equivalence

Universality transfers. Because a universal circuit gate set compiles to cluster tiles, the cluster state on a 2D lattice plus single-qubit measurements is a universal quantum computer.
Complexity classes coincide. Decision problems solvable by polynomial-size patterns are exactly those in BQP.
Different costs are exposed. Equivalence in power does not mean equivalence in practical cost. MBQC front-loads all entanglement and can run many measurements in parallel, often giving lower logical depth; the trade is a larger qubit count. Which model is preferable is a hardware question, not a computability one.

The takeaway

Circuit and one-way models compute the same class of functions with polynomial overhead each way. The forward compilation lays each gate down as a cluster tile on a 2D lattice with measurement angles encoding the gate parameters; the reverse simply reads the four pattern commands as circuit operations. Flow is the condition that keeps the measurement-based version deterministic. MBQC is thus a genuinely different architecture for the same computational power — the perspective the rest of the module, and fault tolerance in particular, builds upon.