Measurement-based quantum computation (MBQC)

Measurement-based quantum computation prepares an entangled resource quantum state, then applies single-qubit quantum measurements, potentially adapting later bases to earlier outcomes. Pauli frame tracking and classical outcome processing convert random physical branches into a specified logical computation. Graph states and one-bit teleportation provide a concrete construction.

A path graph state on three qubits simulates two successive gates $U(\theta )=H\mathrm{diag}(1,e^{-i\theta })=J(-\theta )$. Measure vertex one in the equatorial qubit measurement basis $|v_r(\alpha )⟩=(|0⟩+(-1{)}^r{e}^{i\alpha }|1⟩)/\sqrt{2}$, then vertex two at angle $(-1{)}^r\beta$, obtaining bits $r,s$. Two one-bit teleportations and $U(\theta )X=e^{-i\theta }ZU(-\theta )$ leave vertex three in $X^s{Z}^{r}U(\beta )U(\alpha )|+⟩$, up to global phase. A computational output bit $z$ is corrected to $z\oplus s$; the $Z$ factor affects only phase. Adaptive sign choice is required for general angles, although the final bit correction is purely classical.

A graph state with edges $13,24,34,45$ simulates $J_2(\gamma )E_{12}(J_1(\alpha )\otimes J_2(\beta ))$ on $|++⟩$. Measure vertices 1 and 2 at angles $\alpha ,\beta$, with results $s_1,s_2$, and vertex 4 at $(-1{)}^{s_2}\gamma$, with result $s_4$. One-bit teleportation and Pauli frame propagation leave output frames $X_3^{s_1}{Z}_3^{s_2}$ and $X_5^{s_4\oplus s_1}{Z}_5^{s_2}$. Computational outputs are therefore corrected by $s_1$ and $s_4\oplus s_1$ respectively.

Label a four-cycle $0-1-2-3-0$. Measure vertex $0$ in the computational basis with result $r$, then vertex $1$ in the equatorial qubit measurement basis at angle $\alpha$ with result $s$. Graph-state vertex deletion and one-bit teleportation leaveFinal computational basis measurements with raw results $d_2,d_3$ therefore simulate the ideal circuit $E_{23}J(\alpha {)}_2$ on $|++⟩$ after the classical correction $k=d_2\oplus r\oplus s$, $l=d_3$. The output probability distribution is correct in every prior branch; no physical Pauli frame correction is needed.

A measurement pattern specifies the resource quantum state, the measured qubits, their measurement bases, outcome-dependent basis choices and output corrections or classical relabellings. The dependence of a basis on earlier outcomes determines the logical depth of a measurement pattern. Preparing the resource and processing the final classical results are separate costs.

Logical measurement depth is the number of sequential measurement layers required by outcome-dependent basis choices. Depth one means all bases are fixed in advance, so the quantum measurements on distinct qubits can be simultaneous. Classical output corrections may still depend on all outcomes. This does not assert depth-one graph-state preparation or constant-depth classical processing.

An $R(\alpha )=J(\alpha )J(0)$ gadget with input Pauli frame $X^p{Z}^q$, angle-zero outcome $s$, and arbitrary-angle outcome $t$ uses angle $(-1{)}^{s\oplus q}\alpha$ and produces frame $X^{p\oplus t}{Z}^{q\oplus s}$. The CNOT gate gadget also updates its $Z$ frames without any dependence on incoming $X$ frames. Therefore all adaptive angle signs depend solely on angle-zero outcomes. Measure all those vertices first, compute every sign, and measure all remaining vertices in a second layer. The result is the desired logical circuit in a known Pauli frame. Computational output measurements can share the second layer.

A path graph state simulates a sequence of Clifford gates $J({\alpha }_j)$, ${\alpha }_j\in \{0,\pi /2\}$, using fixed equatorial qubit measurement bases on successive path vertices. Let $s_j$ be raw outcomes, $t_j=2{\alpha }_j/\pi \in \{0,1\}$, and start the Pauli frame at $a_0=b_0=0$. Matrix commutation and $J(-\pi /2)=XJ(\pi /2)$ giveInduction shows the final unmeasured state differs from the ideal circuit output by $X^{a_m}{Z}^{b_m}$, up to global phase. A final computational basis result $d$ is corrected to $d\oplus a_m$. All bases are fixed, and projectors on distinct vertices commute, so all measurements, including the final one, can occur in a single layer. The frame recurrence is classical outcome processing, not quantum feed-forward.

Compile each CNOT gate into a Hadamard gate, a Controlled-Z gate, and another Hadamard gate on its target. Every one-bit teleportation implementing a Hadamard gate uses a fixed angle-zero basis. A Pauli frame propagates by classical binary updates without changing a measurement basis. All internal measurements, and any fixed computational output measurements, therefore share one simultaneous layer. Resource preparation and classical processing are not included in this logical measurement depth.