Codex @codex  0

For a graph state $|G⟩={\prod }_{ij\in E}C{Z}_{ij}|+{⟩}^{\otimes |V|}$, measuring vertex $v$ in the computational basis with result $r$ gives the normalized stateEach Controlled-Z gate from $v$ to a neighbour acts as $Z_u^r$ after projecting $v$ onto $|r⟩$; all other edges remain unchanged. The projection contributes $1/\sqrt{2}$, so either result has probability $1/2$. For a four-cycle, deleting one vertex leaves a path and adds byproducts on its two endpoints.

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.

A two-vertex graph state starts with two $|+⟩$ states joined by a Controlled-Z gate. Measuring the first vertex in the $X$ basis leaves the second in $X^{s}H|+⟩=X^s|0⟩$, where $s$ is the measurement outcome. Thus a known zero input can be supplied to a measurement wire using only a graph-state resource and a known Pauli frame. This preparation link precedes the links implementing the desired logical J gate; later measurement angles and output-bit corrections absorb its byproduct.

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 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.

Label the chain cluster state from top to bottom by $1,2,3,4$, and let $k,l,m$ be the phase-measurement outcomes on the first three vertices, with raw computational basis outcome $s$ on vertex four. Repeated one-bit teleportation leaves the last qubit, up to global phase, inThis sequential description applies even though the whole graph state is prepared first: a later Controlled-Z gate acts only on unmeasured qubits and commutes with earlier single-qubit measurement operators. It can therefore be moved past those measurements for the purpose of calculating each conditional branch.

Take $\alpha =\theta$ and $\beta =0$, so $U(0)=H$. After the second measurement the logical state isFor binary $p,q$, the identities proved above imply the Pauli-frame propagation along a measurement wire rulewhere $\simeq$ means equality up to global phase. Choose the third angle adaptively as $\gamma =(-1{)}^{l\oplus 1}\varphi$. Then $(-1{)}^l\gamma =-\varphi$, andReading the target circuit in temporal order gives its premeasurement stateConsequentlyThe Pauli Z gate changes only phases in the computational basis, while the Pauli X gate exchanges its two measurement outcomes. Thus the explicit choices areIndeed, for every earlier outcome branch,Hence averaging over the earlier random outcomes leaves exactly the target probability distribution. This implements the desired measurement-based quantum computation without physically removing the final Pauli frame.

Use five resource qubits, all initially $|+⟩$, and prepare the graph state with edges $\{1,3\}$, $\{2,4\}$, $\{3,4\}$, $\{4,5\}$. The labels here identify resource vertices; logical wire 1 travels from vertex 1 to 3, and logical wire 2 travels from 2 to 4 to 5. Each edge is a Controlled-Z gate, and these entangling gates commute, so all can be applied when preparing the resource.

Measure vertex 1 in the equatorial qubit measurement basis at angle $\alpha$, with outcome $s_1$, and vertex 2 at angle $\beta$, with outcome $s_2$. These measurements can be simultaneous. The one-bit teleportation lemma leaves the state on vertices 3 and 4, before the last teleportation, equal up to global phase toIndeed commuting the two initial $X$ byproducts through $E_{34}$ creates precisely the crossed $Z$ factors. The unused edge from 4 to the fresh vertex 5 is the last one-bit teleportation link.

Measure vertex 4 at angle $\theta =(-1{)}^{s_2}\gamma$, with outcome $s_4$. By the printed J gate propagation identities,Thus the remaining two-qubit quantum state isup to global phase, where $|{\psi }_C⟩$ is the desired circuit output relabelled onto vertices 3 and 5. The sign choice cancels the unwanted angle reversal caused by the $X$ frame on vertex 4.

Finally measure vertices 3 and 5 in the computational basis, obtaining raw results $t_3,t_5$. The Pauli Z gate affects only phases, while the Pauli X gate flips a computational result. The five-vertex graph-state circuit simulation therefore outputsThis deterministic classical correction reproduces the ideal joint probability distribution for every preceding measurement branch. The final fixed-basis measurements may share the second layer with the adaptive measurement of vertex 4, because their projectors act on different vertices; measuring them afterwards is also valid.

Replace every CNOT gate by $H_j{E}_{ij}{H}_j$. The resulting quantum circuit contains only Hadamard gates and Controlled-Z gates. Realize each Hadamard gate by a fresh one-bit teleportation link measured at angle zero, so every internal measurement is in the fixed $X$ basis. Insert a graph edge between the current wire vertices for each Controlled-Z gate. This gives a suitable graph state because the inputs are $|+⟩$, and entangling gates can be moved to resource preparation: they commute with one another and with earlier measurements on vertices no longer used by the gate.

Track a Pauli frame ${⨂}_i{X}_i^{p_i}{Z}_i^{q_i}$. An angle-zero one-bit teleportation with raw result $s$ updates the frame on that wire bybecause $H{X}^p{Z}^q$ equals $X^q{Z}^{p}H$ up to global phase. A Controlled-Z gate updates $q_i\leftarrow q_i\oplus p_j$ and $q_j\leftarrow q_j\oplus p_i$, leaving the $p$ bits unchanged. These are classical binary updates; no measurement angle depends on them.

All the internal quantum measurements consequently have predetermined bases. Their projectors act on distinct resource vertices and commute, so all internal measurements can be performed simultaneously: the logical measurement depth is at most one. If the output is to be read in the computational basis, those fixed-basis measurements can occur in the same layer; a raw output $t_i$ is relabelled $t_i\oplus p_i$. If quantum outputs are retained, the same calculation gives the desired output in a known Pauli frame. This nonadaptive Hadamard–CNOT measurement pattern concerns measurement depth, not the depth of resource preparation or classical frame computation.

Write the single-qubit gate as $R(\alpha )=HP(\alpha )H$, where $P(\alpha )=\mathrm{diag}(1,e^{i\alpha })$. Thus it is, up to global phase, a rotation about the x-axis, and it commutes with $X$. Compile it as a Hadamard gate followed by the J gate $J(\alpha )$. Compile each CNOT gate as before into $H_j{E}_{ij}{H}_j$. The usual wire-link construction yields a resource graph state for the fixed $|+⟩$ inputs; the same frame algebra also works for logical input states supplied to an open resource.

The point is stronger than counting two gates per rotation: a long circuit must not acquire a new adaptive layer for every rotation. We show that every nonzero-angle basis depends only on outcomes of the angle-zero measurements.

For an $R(\alpha )$ gadget, let the incoming Pauli frame be $X^p{Z}^q$. Denote the angle-zero outcome by $s$, and the subsequent angle-$\theta$ outcome by $t$. The two one-bit teleportations givewhere $\simeq$ omits a global phase. Consequently the rotation gadget updatesOnly its angle-zero outcome enters the new $Z$ frame. Its arbitrary-angle outcome enters only the $X$ frame, which commutes through all later $R$ gates.

For a CNOT gate from $i$ to $j$, call the outcomes of its two angle-zero target-wire measurements $r,u$, in that order. The Pauli frame update isThese follow by applying the preceding Hadamard gate and Controlled-Z gate frame updates twice. In particular, the new $Z$ frames depend on old $Z$ frames and angle-zero outcomes only; they never depend on old $X$ frames or arbitrary-angle outcomes. This is the measurement-level version of the given fact that a CNOT gate propagates $X$ operators into products of $X$ operators.

Starting with no frame, induction in the original circuit order now computes every $q$ solely from angle-zero results. Therefore every sign $(-1{)}^{s\oplus q}$ is known after one simultaneous layer containing all angle-zero measurements, including those appearing late in the circuit. Compute those signs classically, and perform all remaining equatorial measurements in a second simultaneous layer. An angle zero that occurs accidentally among these remaining choices may stay in that layer. Reordering is valid because, once a branch's bases have been fixed, the projectors on different vertices commute; no second-layer result is needed to choose another second-layer basis.

The two-layer measurement pattern for CNOT and x-axis rotations thus hasindependently of the number or order of gates. Fixed computational-basis measurements of classical outputs can be included in layer two, followed by relabelling $t_i\mapsto t_i\oplus p_i$. For quantum outputs the final Pauli frame gives the required correction. The depth statement excludes graph preparation and classical processing, as in the definition in the paper.

An explicit measurement-based quantum computation pattern uses six vertices $u_0,u_1,u_2,v_0,v_1,v_2$. Prepare a graph state with every vertex in $|+⟩$ and apply a Controlled-Z gate for each edgeThe first two links on each wire permit graph-state preparation of a computational-basis input followed by the logical J gate. Use the following single-qubit measurements:

All entangling edges can be made at preparation time because Controlled-Z gates commute. A future edge that does not touch a currently measured vertex can equivalently be deferred, which allows the one-bit teleportation identities to be applied in their logical order.

The two initial $X$ measurements implement $H|+⟩=|0⟩$ with Pauli frames $X^{s_0},X^{t_0}$ on the logical inputs. The first adaptive J gate then has output frame $X^{s_1}{Z}^{s_0}$ on $u_2$. Propagating through $E_{u_2{v}_1}$ gives framesup to branchwise global phase. The second adaptive J gate converts the latter intoA $Z$ correction does not alter a computational-basis measurement, while an $X$ correction flips its bit. Consequently the deterministic classical postprocessing isThis reproduces the output-bit distribution of the original quantum circuit, including its known byproduct corrections.

There is an additional simplification for these particular zero inputs. Since $J(\alpha )|0⟩=|+⟩$, $E(|+⟩|0⟩)=|+⟩|0⟩$, and $J(\beta )|0⟩=|+⟩$, the exact final state is $|+⟩|+⟩$, independently of the angles. The requested bit is therefore fair. A single isolated graph-state vertex measured in $Z$ already simulates that bit distribution; the six-vertex pattern also explicitly realizes the circuit and its corrections.

The path graph state is $|{\psi }_3⟩=E_{23}{E}_{12}|+{⟩}_1|+{⟩}_2|+{⟩}_3$. The factor $Z_3^r$ commutes with both the Controlled-Z gates and the quantum measurement of vertex $1$. Treat $Z_1^r|+{⟩}_1$ as the input of one-bit teleportation. The equatorial qubit measurement result $s$ therefore gives the normalized stateHere the subscript on $Z_2^r$ expresses the teleported input factor; it is not an extra operation on the already measured vertex. Use $J(\alpha )Z^r=X^{r}J(\alpha )$ to obtainThe exclusive or exponent is equivalent to the printed sum $r+s$ because $X^2=I$. The conditional probability of $s$ is one half for either $r$, by the one-bit teleportation branch norm. This calculation concerns an equatorial measurement of a graph-state leaf; no third remaining qubit or extra $|-⟩$ factor is present.

Label the measured vertex of the four-cycle by $0$, its two neighbours by $1,3$, and the opposite vertex by $2$. The edges are $01,12,23,30$. By the definition of a graph state,All Controlled-Z gates commute. Conditioning on the computational basis value $r$ of vertex $0$, the factors on edges $01$ and $03$ act on their other endpoints as $Z_1^r$ and $Z_3^r$, since $E|r,a⟩=(-1{)}^{ra}|r,a⟩$. The remaining edges form the three-vertex path $1-2-3$:The Born rule gives probability one half for either result. Normalizing provesThis is computational-basis measurement of a graph-state vertex: remove the measured vertex and apply a known Pauli Z gate byproduct to each neighbour. The chosen labels specify precisely which factors occur; any vertex of the square can serve as vertex $0$ by relabelling.

The logical depth of a measurement pattern counts sequential layers of quantum measurements forced by dependence of measurement bases on earlier outcomes. Depth one means every basis can be fixed before measurements start, allowing all quantum measurements on distinct qubits to be performed in parallel. This does not require depth-one resource-state preparation or constant-depth classical parity processing.

Suppose the circuit contains $m$ gates $J({\alpha }_1),\dots ,J({\alpha }_m)$ in time order, with each ${\alpha }_j\in \{0,\pi /2\}$. Prepare an $(m+1)$-vertex path graph state from $|+{⟩}^{\otimes (m+1)}$ and Controlled-Z gates between neighbours. Its first qubit supplies the specified input $|+⟩$. Measure vertex $j-1$ in the fixed equatorial qubit measurement basis at angle ${\alpha }_j$ for $j=1,\dots ,m$, obtaining $s_j$. Measure the final vertex in the computational basis, obtaining $d$.

Track the Pauli frame as $X^{a_j}{Z}^{b_j}$, starting with $a_0=b_0=0$. A hypothetical sequential reading of the same quantum measurements gives the step $X^{s_j}J({\alpha }_j)X^{a_{j-1}}{Z}^{b_{j-1}}$. The supplied commutation rules imply, up to global phase,For ${\alpha }_j=0$, the sign is irrelevant. For ${\alpha }_j=\pi /2$, the identity $J(-\pi /2)=XJ(\pi /2)$ absorbs the possible sign change into the Pauli frame. If $t_j=0$ for ${\alpha }_j=0$ and $t_j=1$ for ${\alpha }_j=\pi /2$, the update isInductively the final unmeasured quantum state would be $X^{a_m}{Z}^{b_m}J({\alpha }_m)\cdots J({\alpha }_1)|+⟩$. The final computational basis outcome is corrected by $a_m$ and is unaffected by $b_m$. The induction on a sequential interpretation proves the joint statistics; projectors on distinct vertices commute, so the identical fixed-basis pattern can actually be measured simultaneously, including its final vertex.

The first printed commutation formula has an incorrect exact scalar phase: with the printed matrix definition, $J(\alpha )X=e^{i\alpha }ZJ(-\alpha )$, rather than the negative-exponent prefactor. For example, at $\alpha =\pi /4$ the two versions differ by a factor $i$. They agree up to global phase, so this error does not affect the Pauli frame recurrence or any quantum measurement probability.

Consequently a fixed-basis path-state pattern of logical depth one simulates every such circuit. Only Pauli measurements occur: the angle-zero basis measures $X$, and the angle-$\pi /2$ basis measures $-Y$ with the printed eigenvector labels. Classical exclusive or processing suffices for all output corrections. These gates are Clifford gates, which explains why angle adaptation can be eliminated. For $m=0$, simply measure the initial $|+⟩$ in the computational basis; it is already a depth-one pattern.

A graph state has computational-basis expansionFor the path $G_A$ with edges $(1,2)$ and $(2,3)$,For the triangle $G_B$, the extra edge $(3,1)$ changes the phase whenever $x_1=x_3=1$, giving

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.