General procedure

The standard process of measurement-based quantum computing consists of three steps:^[16][17] entangle the qubits, measure the ancillae (auxiliary qubits) and correct the outputs. In the first step, the qubits are entangled in order to prepare the source state. In the second step, the ancillae are measured, affecting the state of the output qubits. However, the measurement outputs are non-deterministic result, due to undetermined nature of quantum mechanics:^[17] in order to carry on the computation in a deterministic way, some correction operators, called byproducts, are introduced.

Preparing the source state

The CZ operation in the circuit diagrams.

At the beginning of the computation, the qubits can be distinguished into two categories: the input and the ancillary qubits. The inputs represent the qubits set in a generic ${\displaystyle |\psi \rangle =\alpha |0\rangle +\beta |1\rangle }$ state, on which some unitary transformations are to be acted. In order to prepare the source state, all the ancillary qubits must be prepared in the ${\displaystyle |+\rangle }$ state:^[11][18]

${\displaystyle |+\rangle ={\tfrac {|0\rangle +|1\rangle }{\sqrt {2}}},}$

where ${\displaystyle |0\rangle }$ and ${\displaystyle |1\rangle }$ are the quantum encoding for the classical ${\displaystyle 0}$ and ${\displaystyle 1}$ bits:

${\displaystyle |0\rangle ={\begin{pmatrix}1\\0\end{pmatrix}};\quad |1\rangle ={\begin{pmatrix}0\\1\end{pmatrix}}}$.

A register with ${\displaystyle n}$ qubits will be therefore set as ${\displaystyle |+\rangle ^{\otimes n}}$. Thereafter, the entanglement between two qubits can be performed by applying a ${\displaystyle CZ}$ gate operation.^[19] The matrix representation of such two-qubits operator is given by

${\displaystyle CZ={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&-1\end{bmatrix}}.}$

The action of a ${\displaystyle CZ}$ gate over two qubits can be described by the following system:

${\displaystyle {\begin{cases}CZ|0+\rangle =|0+\rangle \\CZ|0-\rangle =|0-\rangle \\CZ|1+\rangle =|1-\rangle \\CZ|1-\rangle =|1+\rangle \end{cases}}}$

When applying a ${\displaystyle CZ}$ gate over two ancillae in the ${\displaystyle |+\rangle }$ state, the overall state

${\displaystyle CZ|++\rangle ={\frac {|0+\rangle +|1-\rangle }{\sqrt {2}}}}$

turns to be an entangled pair of qubits. When entangling two ancillae, no importance is given about which is the control qubit and which one the target, as far as the outcome turns to be the same. Similarly, as the ${\displaystyle CZ}$ gates are represented in a diagonal form, they all commute each other, and no importance is given about which qubits to entangle first. Photons are the most common source to prepare entangled physical qubits.^[20][21][22]

Measuring the qubits

Implementation of X and Z gates over two qubits in the circuit diagrams.

The process of measurement over a single-particle state can be described by projecting the state on the eigenvector of an observable. Consider an observable ${\displaystyle O}$ with two possible eigenvectors, say ${\displaystyle |o_{1}\rangle }$ and ${\displaystyle |o_{2}\rangle }$, and suppose to deal with a multi-particle quantum system ${\displaystyle |\Psi \rangle }$. Measuring the ${\displaystyle i}$-th qubit by the ${\displaystyle O}$ observable means to project the ${\displaystyle |\Psi \rangle }$ state over the eigenvectors of ${\displaystyle O}$:^[18]

${\displaystyle |\Psi '\rangle =|o_{i}\rangle \langle o_{i}|\Psi \rangle }$.

The actual state of the ${\displaystyle i}$-th qubit is now ${\displaystyle |o_{i}\rangle }$, which can turn to be ${\displaystyle |o_{1}\rangle }$ or ${\displaystyle |o_{2}\rangle }$, depending on the outcome from the measurement (which is probabilistic in quantum mechanics). The measurement projection can be performed over the eigenstates of the ${\displaystyle M(\theta )=\cos(\theta )X+\sin(\theta )Y}$ observable:

${\displaystyle M(\theta )=\cos(\theta ){\begin{bmatrix}0&1\\1&0\end{bmatrix}}+\sin(\theta ){\begin{bmatrix}0&-i\\i&0\end{bmatrix}}={\begin{bmatrix}0&e^{-i\theta }\\e^{i\theta }&0\end{bmatrix}}}$,

where ${\displaystyle X}$ and ${\displaystyle Y}$ belong to the Pauli matrices. The eigenvectors of ${\displaystyle M(\theta )}$ are ${\displaystyle |\theta _{\pm }\rangle =|0\rangle \pm e^{i\theta }|1\rangle }$. Measuring a qubit on the ${\displaystyle X}$-${\displaystyle Y}$ plane, i.e. by the ${\displaystyle M(\theta )}$ observable, means to project it over ${\displaystyle |\theta _{+}\rangle }$ or ${\displaystyle |\theta _{-}\rangle }$. In the one-way quantum computing, once a qubit has been measured, there is no way to recycle it in the flow of computation. Therefore, instead of using the ${\displaystyle |o_{i}\rangle \langle o_{i}|}$ notation, it is common to find ${\displaystyle \langle o_{i}|}$ to indicate a projective measurement over the ${\displaystyle i}$-th qubit.

Correcting the output

After all the measurements have been performed, the system has been reduced to a smaller number of qubits, which form the output state of the system. Due to the probabilistic outcome of measurements, the system is not set in a deterministic way: after a measurement on the ${\displaystyle X}$-${\displaystyle Y}$ plane, the output may change whether the outcome had been ${\displaystyle |\theta _{+}\rangle }$ or ${\displaystyle |\theta _{-}\rangle }$. In order to perform a deterministic computation, some corrections must be introduced. The correction operators, or byproduct operators, are applied to the output qubits after all the measurements have been performed.^[18][23] The byproduct operators which can be implemented are ${\displaystyle X}$ and ${\displaystyle Z}$.^[24] Depending on the outcome of the measurement, a byproduct operator can be applied or not to the output state: a ${\displaystyle X}$ correction over the ${\displaystyle j}$-th qubit, depending on the outcome of the measurement performed over the ${\displaystyle i}$-th qubit via the ${\displaystyle M(\theta )}$ observable, can be described as ${\displaystyle X_{j}^{s_{i}}}$, where ${\displaystyle s_{i}}$ is set to be ${\displaystyle 0}$ if the outcome of measurement was ${\displaystyle |\theta _{+}\rangle }$, otherwise is ${\displaystyle 1}$ if it was ${\displaystyle |\theta _{-}\rangle }$. In the first case, no correction will occur, in the latter one a ${\displaystyle X}$ operator will be implemented on the ${\displaystyle j}$-th qubit. Eventually, even though the outcome of a measurement is not deterministic in quantum mechanics, the results from measurements can be used in order to perform corrections, and carry on a deterministic computation.

An example: Euler rotations

As an illustrative example, consider the Euler rotation in the ${\displaystyle XZX}$ basis: such operation, in the gate model of quantum computation, is described as^[25]

${\displaystyle e^{i\gamma }R_{X}(\phi )R_{Z}(\theta )R_{X}(\lambda )}$,

where ${\displaystyle \phi ,\theta ,\lambda }$ are the angles for the rotation, while ${\displaystyle \gamma }$ defines a global phase which is irrelevant for the computation. To perform such operation in the one-way computing frame, it is possible to implement the following CME pattern:^[23][26]

${\displaystyle Z_{5}^{s_{1}+s_{3}}X_{5}^{s_{2}+s_{4}}[M_{4}^{-\phi }]^{s_{1}+s_{3}}[M_{3}^{-\theta }]^{s_{2}}[M_{2}^{-\lambda }]^{s_{1}}M_{1}^{0}E_{4,5}E_{3,4}E_{2,3}E_{1,2}}$,

where the input state ${\displaystyle |\psi \rangle =\alpha |0\rangle +\beta |1\rangle }$ is the qubit ${\displaystyle 1}$, all the other qubits are auxiliary ancillae and therefore have to be prepared in the ${\displaystyle |+\rangle }$ state. In the first step, the input state ${\displaystyle |\psi \rangle }$ must be entangled with the second qubits; in turn, the second qubit must be entangled with the third one and so on. The entangling operations ${\displaystyle E_{ij}}$ between the qubits can be performed by the ${\displaystyle CZ}$ gates.

In the second place, the first and the second qubits must be measured by the ${\displaystyle M(\theta )}$ observable, which means they must be projected onto the eigenstates ${\displaystyle |\theta \rangle }$ of such observable. When the ${\displaystyle \theta }$ is zero, the ${\displaystyle |\theta _{\pm }\rangle }$ states reduce to ${\displaystyle |\pm \rangle }$ ones, i.e. the eigenvectors for the ${\displaystyle X}$ Pauli operator. The first measurement ${\displaystyle M_{1}^{0}}$ is performed on the qubit ${\displaystyle 1}$ with a ${\displaystyle \theta =0}$ angle, which means it has to be projected onto the ${\displaystyle \langle \pm |}$ states. The second measurement ${\displaystyle [M_{2}^{-\lambda }]^{s_{1}}}$ is performed with respect to the ${\displaystyle -\lambda }$ angle, i.e. the second qubit has to be projected on the ${\displaystyle \langle 0|\pm e^{i\lambda }\langle 1|}$ state. However, if the outcome from the previous measurement has been ${\displaystyle \langle -|}$, the sign of the ${\displaystyle \lambda }$ angle has to be flipped, and the second qubit will be projected to the ${\displaystyle \langle 0|+e^{-i\lambda }\langle 1|}$ state; if the outcome from the first measurement has been ${\displaystyle \langle +|}$, no flip needs to be performed. The same operations have to be repeated for the third ${\displaystyle [M_{3}^{\theta }]^{s_{2}}}$ and the fourth ${\displaystyle [M_{4}^{\phi }]^{s_{1}+s_{3}}}$ measurements, according to the respective angles and sign flips. The sign over the ${\displaystyle \phi }$ angle is set to be ${\displaystyle (-)^{s_{1}+s_{3}}}$. Eventually the fifth qubit (the only one not to be measured) figures out to be the output state.

At last, the corrections ${\displaystyle Z_{5}^{s_{1}+s_{3}}X_{5}^{s_{2}+s_{4}}}$ over the output state have to be performed via the byproduct operators. For instance, if the measurements over the second and the fourth qubits turned to be ${\displaystyle \langle \phi _{+}|}$ and ${\displaystyle \langle \lambda _{+}|}$, no correction will be conducted by the ${\displaystyle X_{5}}$ operator, as ${\displaystyle s_{2}=s_{4}=0}$. The same result holds for a ${\displaystyle \langle \phi _{-}|}$ ${\displaystyle \langle \lambda _{-}|}$ outcome, as ${\displaystyle s_{2}=s_{4}=1}$ and thus the squared Pauli operator ${\displaystyle X^{2}}$ returns the identity.

As seen in such example, in the measurement-based computation model, the physical input qubit (the first one) and output qubit (the third one) may differ each other.

Standardization

In order to move all the ${\displaystyle E_{ij}}$ entanglements at the beginning of the process, some rules of commutation must be pointed out:

${\displaystyle E_{ij}Z_{i}^{s}=Z_{i}^{s}E_{ij}}$

${\displaystyle E_{ij}X_{i}^{s}=X_{i}^{s}Z_{j}^{s}E_{ij}}$

${\displaystyle E_{ij}A_{k}=A_{k}E_{ij}}$.

The entanglement operator ${\displaystyle E_{ij}}$ commutes with the ${\displaystyle Z}$ Pauli operators and with any other operator ${\displaystyle A_{k}}$ acting on a qubit ${\displaystyle k\neq i,j}$, but not with the ${\displaystyle X}$ Pauli operators acting on the ${\displaystyle i}$-th or ${\displaystyle j}$-th qubits.

Pauli simplification

The measurement operations ${\displaystyle M_{i}^{\theta }}$ commute with the corrections in the following manner:

${\displaystyle M_{i}^{\theta }X_{i}^{s}=[M_{i}^{\theta }]^{s}}$

${\displaystyle M_{i}^{\theta }Z_{i}^{t}=S_{i}^{t}M_{i}^{\theta }}$,

where ${\displaystyle [M_{i}^{\theta }]^{s}=M_{i}^{(-)^{s}\theta }}$. Such operation means that, when shifting the ${\displaystyle X}$ corrections at the end of the pattern, some dependencies between the measurements may occur. The ${\displaystyle S_{i}^{t}}$ operator is called signal shifting, whose action will be explained in the next paragraph. For particular ${\displaystyle \theta }$ angles, some simplifications, called Pauli simplifications, can be introduced:

${\displaystyle M_{i}^{0}X_{i}^{s}=M_{i}^{0}}$

${\displaystyle M_{i}^{\pi /2}X_{i}^{s}=M_{i}^{\pi /2}Z_{i}^{s}}$.

Signal shifting

The action of the signal shifting operator ${\displaystyle S_{i}^{t}}$ can be explained through its rules of commutation:

${\displaystyle X_{i}^{s}S_{i}^{t}=S_{i}^{t}X_{i}^{s[(s_{i}+t)/s_{i}]}}$

${\displaystyle Z_{i}^{s}S_{i}^{t}=S_{i}^{t}Z_{i}^{s[(s_{i}+t)/s_{i}]}}$.

The ${\displaystyle s[(t+s_{i})/s_{i}]}$ operation has to be explained: suppose to have a sequence of signals ${\displaystyle s}$, consisting of ${\displaystyle s_{1}+s_{2}+...+s_{i}+...}$, the operation ${\displaystyle s[(t+s_{i})/s_{i}]}$ means to substitute ${\displaystyle s_{i}}$ with ${\displaystyle s_{i}+t}$ in the sequence ${\displaystyle s}$, which becomes ${\displaystyle s_{1}+s_{2}+...+s_{i}+t+...}$. If no ${\displaystyle s_{i}}$ appears in the ${\displaystyle s}$ sequence, no substitution will occur. To perform a correct CME pattern, every signal shifting operator ${\displaystyle S_{i}^{t}}$ must be translated at the end of the pattern.

The Clifford group

The Clifford group ${\displaystyle {\mathcal {C}}_{n}}$ is composed by elements which leave invariant the elements from the Pauli's group ${\displaystyle {\mathcal {P}}_{n}}$:^[19][29][33]

${\displaystyle {\mathcal {C}}_{n}=\{U\in SU(2^{n})\;|\;USU^{\dagger }\in {\mathcal {P}}_{n},S\in {\mathcal {P}}_{n}\}}$.

The Clifford group requires three generators, which can be chosen as the Hadamard gate ${\displaystyle H}$ and the phase rotation ${\displaystyle S}$ for the single-qubit gates, and another two-qubits gate from the ${\displaystyle CNOT}$ (controlled NOT gate) or the ${\displaystyle CZ}$ (controlled phase gate):

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\quad S={\begin{bmatrix}1&0\\0&i\end{bmatrix}},\quad CNOT={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}}}$.

Consider a state ${\displaystyle |G\rangle }$ which is stabilized by a set of stabilizers ${\displaystyle S_{i}}$. Acting via an element ${\displaystyle U}$ from the Clifford group on such state, the following equalities hold:^[29][34]

${\displaystyle U|G\rangle =US_{i}|G\rangle =US_{i}U^{\dagger }U|G\rangle =S'_{i}U|G\rangle }$.

Therefore, the ${\displaystyle U}$ operations map the ${\displaystyle |G\rangle }$ state to ${\displaystyle U|G\rangle }$ and its ${\displaystyle S_{i}}$ stabilizers to ${\displaystyle US_{i}U^{\dagger }}$. Such operation may give rise to different representations for the ${\displaystyle K_{i}}$ generators of the stabilizer group.

The Gottesman–Knill theorem states that, given a set of logic gates from the Clifford group, followed by ${\displaystyle Z}$ measurements, such computation can be efficiently simulated on a classical computer in the strong sense, i.e. a computation which elaborates in a polynomial-time the probability ${\displaystyle P(x)}$ for a given output ${\displaystyle x}$ from the circuit.^{[19][29][35][36][37]}

Topological cluster state quantum computer

Measurement-based computation on a periodic 3D lattice cluster state can be used to implement topological quantum error correction.^[38] Topological cluster state computation is closely related to Kitaev's toric code, as the 3D topological cluster state can be constructed and measured over time by a repeated sequence of gates on a 2D array.^[39]

Implementations

One-way quantum computation has been demonstrated by running the 2 qubit Grover's algorithm on a 2x2 cluster state of photons.^[40][41] A linear optics quantum computer based on one-way computation has been proposed.^[42]

Cluster states have also been created in optical lattices,^[43] but were not used for computation as the atom qubits were too close together to measure individually.

AKLT state as a resource

It has been shown that the (spin ${\displaystyle {\tfrac {3}{2}}}$) AKLT state on a 2D honeycomb lattice can be used as a resource for MBQC.^[44][45] More recently it has been shown that a spin-mixture AKLT state can be used as a resource.^[46]