Graph States and Measurement-Based Computation

Let $G=(V,E)$ be a finite simple graph with a fixed order $V=(v_0,\dots ,v_{n-1})$. Put ${\mathbb{F}}_2:=\mathbb{Z}\mathrm{/}2\mathbb{Z}$; the field law follows from For every prime $p$, the two operations on $\mathbb{Z}\mathrm{/}p$ make it a field at $p=2$, and this field has order two by Finite fields and their order. Define the binary adjacency matrix $A_2(G)\in M_n({\mathbb{F}}_2)$ by

$(A_2(G){)}_{jk}=\{\begin{array}{ll}1,& \{v_j,v_k\}\in E,\\ 0,& \{v_j,v_k\}\mathrm{\notin }E\mathrm{.}\end{array}$

The indices use the ordered bit coordinates of Big-endian encoding of ordered bit strings. Since edges are unordered pairs of distinct vertices, $A_2(G)$ is symmetric and has zero diagonal. This is a matrix over ${\mathbb{F}}_2$, using Finite rectangular matrices over a commutative ring, their entries, rows and columns; it is not the root library's real-valued adjacency matrix. When $V=\mathrm{\varnothing }$, $A_2(G)$ is the unique $0\times 0$ matrix.

For $\alpha \in \mathbb{R}$, let $P_{\alpha }=\mathrm{diag}(1,e^{i\alpha })$ and $J(\alpha )=H{P}_{\alpha }$, with $H$ and the exact one-qubit gate convention from Exact one-qubit gates and rotations. Define the ordered measurement vectors

$\mathrm{\mid }b{⟩}_{\alpha }:=J(\alpha {)}^{†}\mathrm{\mid }b⟩,b\in \{0,1\},$

where $\mathrm{\mid }0⟩,\mathrm{\mid }1⟩$ are the ordered computational basis vectors. The adjoint and complex inner product use the root convention translated by Dirac Notation Conversion. The global phase in $J(\alpha )$ is fixed by the displayed matrix product; it is not suppressed.

For every $\alpha ,\beta \in \mathbb{R}$, $J(\alpha )$ is unitary and $\{\mathrm{\mid }0{⟩}_{\alpha },\mathrm{\mid }1{⟩}_{\alpha }\}$ is an orthonormal basis. The exact identities

$J(0)=H,J(0{)}^2=I,J(-\beta )X=e^{-i\beta }ZJ(\beta ),J(\pi \mathrm{/}2{)}^3=e^{i\pi \mathrm{/}4}I$

hold in the fixed phase convention.

Let $G=(V,E)$ be a finite simple graph with a fixed vertex order. Let ${\mathcal{H}}_V={⨂}_{v\in V}{\mathbb{C}}^2$ use that order and its ordered computational basis, as in Finite registers and their ordered computational bases, Big-endian encoding of ordered bit strings, and Ordered tensor registers, their inner product, and wire permutations. For each edge $\{u,v\}$ let $C{Z}_{uv}$ be the unique full-register local embedding from A local gate has a unique global wire embedding of the controlled phase gate with angle $\pi$ from Controlled Phase Rotation. Order the endpoints so that $u$ precedes $v$ in the fixed vertex order; the embedded two-qubit matrix is $\mathrm{diag}(1,1,1,-1)$ in the ordered pair basis $\mathrm{\mid }00⟩,\mathrm{\mid }01⟩,\mathrm{\mid }10⟩,\mathrm{\mid }11⟩$, and every other tensor factor acts as the identity. Thus the two local factors have the same order as the edge endpoints, within the full register ordered by $V$. Order the finite edge set lexicographically by its ordered endpoint indices and define

$\mathrm{\mid }G⟩:=\left({\prod }_{\{u,v\}\in E}^{\mathrm{l}\mathrm{e}\mathrm{x}}C{Z}_{uv}\right)\mathrm{\mid }+{⟩}^{\otimes V},\mathrm{\mid }+⟩=2^{-1\mathrm{/}2}(\mathrm{\mid }0⟩+\mathrm{\mid }1⟩)\mathrm{.}$

The lexicographic order makes the product a specified finite composition. If $V=\mathrm{\varnothing }$, the tensor product and empty product act on the one-dimensional trivial register and $\mathrm{\mid }G⟩$ is its unit vector.

The separate result Controlled-Z edge gates commute proves that this vector is independent of edge order.

Let $n\ge 0$ and let $M$ be a matching, meaning a set of pairwise disjoint two-element subsets of the ordered wire set $\{1,\dots ,n\}$. Give the graph $G_M=(\{1,\dots ,n\},M)$ the vertex order $1,\dots ,n$, so vertex $j$ is coordinate $j$ (position $j-1$ in the zero-based vertex list) of its binary adjacency matrix. Let $A_M:=A_2(G_M)\in M_n({\mathbb{F}}_2)$ from Binary adjacency matrix of an ordered finite simple graph, so $(A_M{)}_{jk}=1$ exactly when $\{j,k\}\in M$. For $x,z\in {\mathbb{F}}_2^n$, all coordinates use this wire order, and binary dot products mean $a\cdot b:={\sum }_{j=1}^n{a}_j{b}_j$ in ${\mathbb{F}}_2$. Define $q_M(x):={\sum }_{\{j,k\}\in M}{x}_j{x}_k\in {\mathbb{F}}_2$. For $n\ge 1$, put $P(x,z):=X^x{Z}^z=P(0,x,z)$ as in Phase aware n qubit pauli group. For $n=0$, the unique empty vectors satisfy $X^x=Z^z=I_{\mathbb{C}}$ and we define $P(x,z)=I_{\mathbb{C}}$; the register is the empty tensor product from Ordered tensor registers, their inner product, and wire permutations. With $C{Z}_M:={\prod }_{\{j,k\}\in M}C{Z}_{jk}$,

$C{Z}_{M}P(x,z)=(-1{)}^{q_M(x)}P(x,z\oplus A_{M}x)C{Z}_M\mathrm{.}$

For the empty wire set or empty matching the sum is zero and the formula is the identity.

Let $C$ be a finite $n$-wire circuit over the $J(\alpha )$ and $CZ$ gates, with chronological layers $L_1,\dots ,L_d$ and source wire labels $0,\dots ,n-1$ as in Finite circuit syntax and ordered wire labels. Schedule index $j\in \{1,\dots ,n\}$ denotes source wire $j-1$. For each source layer $L_r$, let $M_r$ be the matching of its $CZ$ occurrences after reindexing a source pair $\{u,v\}$ as $\{u+1,v+1\}$, and let $J_r\subseteq \{1,\dots ,n\}$ be the indices carrying one-qubit gates $J({\alpha }_{rj})$. The source layer has pairwise disjoint gate supports by Finite circuit syntax and ordered wire labels, so no $J$ gate in $J_r$ meets an edge of $M_r$. By Gates on disjoint wires commute, its denotation may be written with the CZ matching first and then at most one $J({\alpha }_{rj})$ per schedule index $j$. The normalized transport schedule $\mathcal{T}(C)$ is the finite chronological list of rounds $(M_s,({\alpha }_{s1},\dots ,{\alpha }_{sn}))$ and the scalar ${\sigma }_C$ defined as follows. A round applies its matching first and then one $J$ gate on each wire. Define ${\sigma }_C={\prod }_{r:0<\mathrm{\mid }{J}_r\mathrm{\mid }<n}{e}^{i\pi (n-\mathrm{\mid }{J}_r\mathrm{\mid })\mathrm{/}4}$. The round list is the concatenation, in source-layer order, of the blocks specified by the first matching case below; the empty product is $1$. This order makes the zero-wire empty-layer case unambiguous:

1. If $J_r=\mathrm{\varnothing }$ and $M_r=\mathrm{\varnothing }$, the block is empty.
2. If $n\ge 1$ and $J_r=\{1,\dots ,n\}$, the block consists of one round with matching $M_r$ and the original angles ${\alpha }_{rj}$.
3. If $J_r=\mathrm{\varnothing }$ and $M_r\mathrm{\ne }\mathrm{\varnothing }$, the block consists of two rounds: the first has matching $M_r$ and angle $0$ on every wire; the second has no matching and angle $0$ on every wire.
4. If $0<\mathrm{\mid }{J}_r\mathrm{\mid }<n$, the block consists of three rounds. The first has matching $M_r$, angle ${\alpha }_{rj}$ on active wires $j\in J_r$, and angle $\pi \mathrm{/}2$ on idle wires. The next two have no matching, angle $0$ on active wires, and angle $\pi \mathrm{/}2$ on idle wires. The factor for this mixed layer is included in the displayed product defining ${\sigma }_C$.

The rounds are numbered $s=1,\dots ,R$ in concatenation order. Their schedule indices continue to denote the corresponding source wires $j-1$. Angles at indices without an original $J$ gate are padding angles. For a mixed layer, the active-wire product is $J(0)J(0)J(\alpha )=J(\alpha )$ and each idle wire contributes $J(\pi \mathrm{/}2{)}^3=e^{i\pi \mathrm{/}4}I$; the scalar is therefore recorded in ${\sigma }_C$ rather than suppressed. The no-$J$ matching case has two $J(0)=H$ transports, whose product is $I$. No claim about the transport graph's simplicity is part of this definition.

For a normalized qubit $\mathrm{\mid }\psi ⟩=a\mathrm{\mid }0⟩+c\mathrm{\mid }1⟩$ and real $\alpha$, prepare $CZ(\mathrm{\mid }\psi ⟩\otimes \mathrm{\mid }+⟩)$ and project the first qubit in the ordered basis $\{\mathrm{\mid }b{⟩}_{\alpha }:b=0,1\}$ of J gate and ordered equatorial measurement vectors. The outcome-$b$ branch operator on the second qubit is

$K_b=2^{-1\mathrm{/}2}{X}^{b}J(\alpha )\mathrm{.}$

Thus each outcome has probability $1\mathrm{/}2$ and the normalized output is $X^{b}J(\alpha )\mathrm{\mid }\psi ⟩$. The operator identity is linear and therefore also holds when the input qubit is entangled with a finite-dimensional reference register.

For $k\ge 0$ controls and real angles ${\theta }_x$ indexed by $x\in \{0,1{\}}^k$, let $M_a={\sum }_{x\in \{0,1{\}}^k}\mathrm{\mid }x⟩⟨x\mathrm{\mid }\otimes R_a({\theta }_x),a\in \{y,z\},$ where $R_y(\theta )=R_{(0,1,0)}(\theta )$ and $R_z(\theta )=R_{(0,0,1)}(\theta )$ use the exact exponential convention of Exact one-qubit gates and rotations. There is an exact finite circuit for $M_a$ on the same $k+1$ wires, using arbitrary one-qubit rotations and CNOT gates and no ancillas. For $k=0$ it is one rotation and no CNOT; for $k>0$ it uses $2^k$ target rotations and $2^k$ CNOTs. The circuit uses exact real angle labels; no finite-bit encoding or synthesis-time bound is asserted.

Let $G=(V,E)$ be an ordered finite simple graph with $n=\mathrm{\mid }V\mathrm{\mid }$. In the ordered computational basis indexed by $x\in {\mathbb{F}}_2^V$,

$\mathrm{\mid }G⟩=2^{-n\mathrm{/}2}{\sum }_{x\in {\mathbb{F}}_2^V}(-1{)}^{{\sum }_{\{u,v\}\in E}{x}_u{x}_v}\mathrm{\mid }x⟩,$

where the exponent is evaluated as an integer and only its parity affects the sign.

For any two edges $e,f$ of a finite simple graph on an ordered qubit register, the embedded operators $C{Z}_e$ and $C{Z}_f$ commute. Consequently the finite graph-state edge product is independent of the ordering of its edges.

An open-graph adaptive measurement pattern consists of an ordered finite simple graph $G=(V,E)$, input and output subsets $I,O\subseteq V$, an ordering $m_1,\dots ,m_q$ of $M:=V\setminus O$, basis-choice functions ${\alpha }_j:\{0,1{\}}^{j-1}\to \mathbb{R}$, and a terminal correction function $C:\{0,1{\}}^q\to U({\mathcal{H}}_O)$. For each subset $S\subseteq V$, write ${\mathcal{H}}_S:={⨂}_{v\in S}{\mathbb{C}}^2$ in inherited vertex order, with ${\mathcal{H}}_{\mathrm{\varnothing }}=\mathbb{C}$. The tensor register ${\mathcal{H}}_V$ and all wire permutations use the fixed vertex order. Let ${\mathrm{\Pi }}_{I,V\setminus I}:{\mathcal{H}}_V\to {\mathcal{H}}_I\otimes {\mathcal{H}}_{V\setminus I}$ be the wire permutation listing $I$ first and then $V\setminus I$, each in inherited order. Let $a_{+}:\mathbb{C}\to {\mathbb{C}}^2$ be the linear map $c\mapsto c\mathrm{\mid }+⟩$, and let $a_{+,V\setminus I}:={⨂}_{v\in V\setminus I}{a}_{+}$ in inherited order. Using the empty-tensor identifications, define the ordered input map ${\iota }_I:={\mathrm{\Pi }}_{I,V\setminus I}^{-1}(I_{{\mathcal{H}}_I}\otimes a_{+,V\setminus I}):{\mathcal{H}}_I\to {\mathcal{H}}_V\mathrm{.}$ Thus the input is unchanged and each complementary vertex receives $\mathrm{\mid }+⟩$. Apply $U_G:={\prod }_{\{u,v\}\in E}^{\mathrm{l}\mathrm{e}\mathrm{x}}C{Z}_{uv}$. At step $j$, after transcript prefix $b_1,\dots ,b_{j-1}$, measure vertex $m_j$ in the ordered basis $\{\mathrm{\mid }{b}_j{⟩}_{{\alpha }_j(b_{<j})}:b_j\in \{0,1\}\}$ from J gate and ordered equatorial measurement vectors. The measured systems are removed and the vertices in $O$ are retained in their inherited order.

Let ${\mathrm{\Pi }}_{M,O}$ be the tensor permutation listing $m_1,\dots ,m_q$ first and the vertices of $O$ in inherited order. For a full transcript $\mathbf{b}=(b_1,\dots ,b_q)$, define the linear measurement contraction $B_{\mathbf{b}}:=({⨂}_{j=1}^q{}_{{\alpha }_j(b_{<j})}\text{\hspace{0.17em}⁣}⟨b_j{\mathrm{\mid }}_{m_j})\otimes I_{{\mathcal{H}}_O},$ where the bras are the linear functionals from Dirac Notation Conversion, their tensor map is formed in $m_1,\dots ,m_q$ order, so $B_{\mathbf{b}}:{\mathcal{H}}_{m_1}\otimes \cdots \otimes {\mathcal{H}}_{m_q}\otimes {\mathcal{H}}_O\to {\mathcal{H}}_O$. The scalar output ${\mathbb{C}}^{\otimes q}$ is identified with $\mathbb{C}$ by the tensor-unit convention. This tensor map is supplied by Tensor products of finitely many linear maps; for $q=0$ its measured-register factor is the identity on the empty tensor product. The branch map is the ordered composition

$K_{\mathbf{b}}=B_{\mathbf{b}}{\mathrm{\Pi }}_{M,O}{U}_G{\iota }_I:{\mathcal{H}}_I\to {\mathcal{H}}_O\mathrm{.}$

The measured systems are removed and the vertices in $O$ are retained in their inherited order. This pattern uses $\mathrm{\mid }V\mathrm{\mid }$ qubit registers, its width in the convention of Finite circuit resource accounting. Its projective measurement count is $q$, counting one occurrence for each listed vertex $m_j$. On a normalized pure input its probability is $\mathrm{\parallel }{K}_{\mathbf{b}}\psi {\mathrm{\parallel }}^2$; for a density operator $\rho$ it is $\mathrm{tr}(K_{\mathbf{b}}\rho K_{\mathbf{b}}^{†})$. The conditional output is normalized only when that probability is positive. The corrected branch is $C(\mathbf{b})K_{\mathbf{b}}$; the correction does not change the branch probability. This is a finite-dimensional mathematical circuit and instrument semantics, with no physical postulate or implementation claim.

If $I=\mathrm{\varnothing }$, the inputless resource is the graph state $\mathrm{\mid }G⟩$. If $M=\mathrm{\varnothing }$, the transcript is empty and no conditional normalization occurs. A zero-probability transcript has no normalized conditional output.

Let a one-qubit input carry the Pauli frame $X^x{Z}^z$, where $x,z\in \{0,1\}$, and let $\beta \in \mathbb{R}$. Choose the next equatorial measurement angle $(-1{)}^x\beta$. For outcome $b\in \{0,1\}$, the one-bit teleportation branch is

$2^{-1\mathrm{/}2}\gamma (x,z,\beta )X^{b\oplus z}{Z}^{x}J(\beta ),\gamma (x,z,\beta )=\{\begin{array}{ll}1,& x=0,\\ (-1{)}^z{e}^{-i\beta },& x=1.\end{array}$

Thus the updated Pauli frame is $(x^{\mathrm{\prime }},z^{\mathrm{\prime }})=(b\oplus z,x)$, and the exact branch scalar has unit modulus.

For a circuit $C$ as in Normalized transport schedule for a J/CZ circuit, let $U_C$ be its denotation and let ${\tilde{U}}_C$ be the chronological product of the normalized rounds. Then

${\tilde{U}}_C={\sigma }_C{U}_C\mathrm{.}$

Let $C$ be an $n$-wire, $d$-layer circuit and let $R$ be the number of rounds in the normalized schedule. Form a candidate vertex list $V_T=\{v_{j,s}:1\le j\le n,0\le s\le R\}$, horizontal edges $\{v_{j,s-1},v_{j,s}\}$, and vertical edges $\{v_{j,s-1},v_{k,s-1}\}$ for each $\{j,k\}\in M_s$. Each edge list is loop-free and duplicate-free, the lists are disjoint, and their union is a finite simple graph with exactly $n(R+1)$ vertices and $R\le 3d$; thus the graph object used in the Definition is well-defined.

For every $n\ge 1$ and $U\in U(2^n)$, there is a finite exact $n$-wire circuit with no ancillas, using arbitrary one-qubit gates and CNOT gates, whose denotation is exactly $U$. For $n=0$, the unitary channel on the one-dimensional register is the identity channel and is represented by the empty circuit. The finite alphabet may be chosen to contain the exact gate matrices used in the construction. This is an existence theorem for exact mathematical gate labels; it gives no finite-bit encoding or decomposition-time bound.