One-way quantum computer

The measurement-based techniques consist of entangling a cluster of qubits and performing a set of measurements. Thanks to the correlation between the entangled qubits, the flow of information (from left to right) is carried on by the measurements on the physical qubits in the cluster.

The one-way quantum computer, also known as measurement-based quantum computer (MBQC), is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

The outcome of each individual measurement is random, but they are related in such a way that the computation always succeeds. In general, the choices of basis for later measurements need to depend on the results of earlier measurements, and hence the measurements cannot all be performed at the same time.

The implementation of MBQC is mainly considered for photonic devices, ^[1] due to the difficulty of entangling photons without measurements, and the simplicity of creating and measuring them. However, MBQC is also possible with matter-based qubits. ^[2] The process of entanglement and measurement can be described with the help of graph tools and group theory, in particular by the elements from the stabilizer group.

Definition

The purpose of quantum computing focuses on building an information theory with the features of quantum mechanics: instead of encoding a binary unit of information (bit), which can be switched to 1 or 0, a quantum binary unit of information (qubit) can simultaneously turn to be 0 and 1 at the same time, thanks to the phenomenon called superposition. ^{[3] [4] [5]} Another key feature for quantum computing relies on the entanglement between the qubits. ^{[6] [7] [8]}

A quantum circuit implementing the Bernstein-Vazirani algorithm: ${\displaystyle H}$ and ${\displaystyle U_{f}}$ represent the logic gates (unitary operators) which act on the register of qubits. In the MBQC frame, the logic gates are performed by entangling the qubits and measuring the auxiliary ones.

In the quantum logic gate model, a set of qubits, called register, is prepared at the beginning of the computation, then a set of logic operations over the qubits, carried by unitary operators, is implemented. ^{[9] [10]} A quantum circuit is formed by a register of qubits on which unitary transformations are applied over the qubits. In the measurement-based quantum computation, instead of implementing a logic operation via unitary transformations, the same operation is executed by entangling a number ${\displaystyle k}$ of input qubits with a cluster of ${\displaystyle a}$ ancillary qubits, forming an overall source state of ${\displaystyle a+k=n}$ qubits, and then measuring a number ${\displaystyle m}$ of them. ^{[11] [12]} The remaining ${\displaystyle k=n-a}$ output qubits will be affected by the measurements because of the entanglement with the measured qubits. The one-way computer has been proved to be a universal quantum computer, which means it can reproduce any unitary operation over an arbitrary number of qubits. ^{[9] [13] [14] [15]}

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 (Controlled) ${\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 qubit system that is used in the context of one-way quantum computing. ^{[20] [21] [22]} However, deterministic ${\displaystyle CZ}$ gates between photons are difficult to realize. Therefore, probabilistic entangling gates such as Bell state measurements are typically considered. ^[23] Furthermore, quantum emitters such as atoms ^[24] or quantum dots ^[25] can be used to create deterministic entanglement between photonic qubits. ^[26]

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] [27]} The byproduct operators which can be implemented are ${\displaystyle X}$ and ${\displaystyle Z}$. ^[28] 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.

CME pattern

The Euler rotation (with respect to the XZX basis) in the MBQC computation. The lines describe the entanglement between the qubits. The first qubit corresponds to the input state ${\displaystyle |\psi \rangle }$, the fifth one to the output state. The qubits from 2 to 4 are the ancillae. All the states, except for the input, are prepared in the ${\displaystyle |+\rangle }$ state. All the qubits, except for the output, are measured by the ${\displaystyle M}$ observable with a specific angle. After the measurements have been carried on, implementing the ${\displaystyle U}$ unitary, the ${\displaystyle X}$ and ${\displaystyle Z}$ corrections are performed with respect to the ${\displaystyle s_{i}}$ outcomes.

The operations of entanglement, measurement and correction can be performed in order to implement unitary gates. Such operations can be performed time by time for any logic gate in the circuit, or rather in a pattern which allocates all the entanglement operations at the beginning, the measurements in the middle and the corrections at the end of the circuit. Such pattern of computation is referred to as CME standard pattern. ^{[16] [17]} In the CME formalism, the operation of entanglement between the ${\displaystyle i}$ and ${\displaystyle j}$ qubits is referred to as ${\displaystyle E_{ij}}$. The measurement on the ${\displaystyle i}$ qubit, in the ${\displaystyle X}$-${\displaystyle Y}$ plane, with respect to a ${\displaystyle \theta }$ angle, is defined as ${\displaystyle M_{i}^{\theta }}$. At last, the ${\displaystyle X}$ byproduct over a ${\displaystyle i}$ qubit, with respect to the measurement over a ${\displaystyle j}$ qubit, is described as ${\displaystyle X_{i}^{s_{j}}}$, where ${\displaystyle s_{j}}$ is set to ${\displaystyle 0}$ if the outcome is the ${\displaystyle |\theta _{+}\rangle }$ state, ${\displaystyle 1}$ when the outcome is ${\displaystyle |\theta _{-}\rangle }$. The same notation holds for the ${\displaystyle Z}$ byproducts.

When performing a computation following the CME pattern, it may happen that two measurements ${\displaystyle M_{i}^{\theta _{1}}}$ and ${\displaystyle M_{j}^{\theta _{2}}}$ on the ${\displaystyle X}$-${\displaystyle Y}$ plane depend one on the outcome from the other. For example, the sign in front of the angle of measurement on the ${\displaystyle j}$-th qubit can be flipped with respect to the measurement over the ${\displaystyle i}$-th qubit: in such case, the notation will be written as ${\displaystyle [M_{j}^{\theta _{2}}]^{s_{i}}M_{i}^{\theta _{1}}}$, and therefore the two operations of measurement do commute each other no more. If ${\displaystyle s_{i}}$ is set to ${\displaystyle 0}$, no flip on the ${\displaystyle \theta _{2}}$ sign will occur, otherwise (when ${\displaystyle s_{i}=1}$) the ${\displaystyle \theta _{2}}$ angle will be flipped to ${\displaystyle -\theta _{2}}$. The notation ${\displaystyle [M_{j}^{\theta _{2}}]^{s_{i}}}$ can therefore be rewritten as ${\displaystyle M_{j}^{(-)^{s_{i}}\theta _{2}}}$.

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 ^[29]

${\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: ^{[27] [30]}

${\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.

Equivalence between quantum circuit model and MBQC

The one-way quantum computer allows the implementation of a circuit of unitary transformations through the operations of entanglement and measurement. At the same time, any quantum circuit can be in turn converted into a CME pattern: a technique to translate quantum circuits into a MBQC pattern of measurements has been formulated by V. Danos et al. ^{[16] [17] [31]}

Such conversion can be carried on by using a universal set of logic gates composed by the ${\displaystyle CZ}$ and the ${\displaystyle J(\theta )}$ operators: therefore, any circuit can be decomposed into a set of ${\displaystyle CZ}$ and the ${\displaystyle J(\theta )}$ gates. The ${\displaystyle J(\theta )}$ single-qubit operator is defined as follows:

${\displaystyle J(\theta )={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&e^{i\theta }\\1&-e^{i\theta }\end{pmatrix}}}$.

The ${\displaystyle J(\theta )}$ can be converted into a CME pattern as follows, with qubit 1 being the input and qubit 2 being the output:

${\displaystyle J(\theta )=X_{2}^{s_{1}}M_{1}^{-\theta }E_{1,2}}$

which means, to implement a ${\displaystyle J(\theta )}$ operator, the input qubits ${\displaystyle |\psi \rangle }$ must be entangled with an ancilla qubit ${\displaystyle |+\rangle }$, therefore the input must be measured on the ${\displaystyle X}$-${\displaystyle Y}$ plane, thereafter the output qubit is corrected by the ${\displaystyle X_{2}}$ byproduct. Once every ${\displaystyle J(\theta )}$ gate has been decomposed into the CME pattern, the operations in the overall computation will consist of ${\displaystyle E_{ij}}$ entanglements, ${\displaystyle M_{i}^{-\theta _{i}}}$ measurements and ${\displaystyle X_{j}}$ corrections. In order to lead the whole flow of computation to a CME pattern, some rules are provided.

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.

Stabilizer formalism

When preparing the source state of entangled qubits, a graph representation can be given by the stabilizer group. The stabilizer group ${\displaystyle {\mathcal {S}}_{n}}$ is an abelian subgroup from the Pauli group ${\displaystyle {\mathcal {P}}_{n}}$, which one can be described by its generators ${\displaystyle \{\pm 1,\pm i\}\times \{I,X,Y,Z\}^{\otimes n}}$. ^{[32] [33]} A stabilizer state is a ${\displaystyle n}$-qubit state ${\displaystyle |\Psi \rangle }$ which is a unique eigenstate for the generators ${\displaystyle S_{i}}$ of the ${\displaystyle {\mathcal {S}}_{n}}$ stabilizer group: ^[19]

${\displaystyle S_{i}|\Psi \rangle =|\Psi \rangle .}$

Of course, ${\displaystyle S_{i}\in {\mathcal {S}}_{n}\,\forall i}$.

A math graph defined by three vertices and three edges. Each vertex is connected with the other ones by an edge. In the MBQC frame, the vertices ${\displaystyle 1,2,3}$ represent the qubits, while the links between them the entanglements. In the stabilizer formalism, such graph is represented by the ${\displaystyle \langle X_{1}Z_{2}Z_{3},Z_{1}X_{2}Z_{3},Z_{1}Z_{2}X_{3}\rangle }$ generators, which all of them commute each other with.

It is therefore possible to define a ${\displaystyle n}$ qubit graph state ${\displaystyle |G\rangle }$ as a quantum state associated with a graph, i.e. a set ${\displaystyle G=(V,E)}$ whose vertices ${\displaystyle V}$ correspond to the qubits, while the edges ${\displaystyle E}$ represent the entanglements between the qubits themselves. The vertices can be labelled by a ${\displaystyle i}$ index, while the edges, linking the ${\displaystyle i}$-th vertex to the ${\displaystyle j}$-th one, by two-indices labels, such as ${\displaystyle (i,j)}$. ^[34] In the stabilizer formalism, such graph structure can be encoded by the ${\displaystyle K_{i}}$ generators of ${\displaystyle {\mathcal {S}}_{n}}$, defined as ^{[15] [35] [36]}

${\displaystyle K_{i}=X_{i}\prod _{j\in (i,j)}Z_{j}}$,

where ${\displaystyle {j\in (i,j)}}$ stands for all the ${\displaystyle j}$ qubits neighboring with the ${\displaystyle i}$-th one, i.e. the ${\displaystyle j}$ vertices linked by a ${\displaystyle (i,j)}$ edge with the ${\displaystyle i}$ vertex. Each ${\displaystyle K_{i}}$ generator commute with all the others. A graph composed by ${\displaystyle n}$ vertices can be described by ${\displaystyle n}$ generators from the stabilizer group:

${\displaystyle \langle K_{1},K_{2},...,K_{n}\rangle }$.

While the number of ${\displaystyle X_{i}}$ is fixed for each ${\displaystyle K_{i}}$ generator, the number of ${\displaystyle Z_{j}}$ may differ, with respect to the connections implemented by the edges in the graph.

The Clifford group

See also: Clifford gates

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] [33] [37]}

${\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: ^{[33] [38]}

${\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] [33] [39] [40] [41]}

Hardware and applications

Topological cluster state quantum computer

Measurement-based computation on a periodic 3D lattice cluster state can be used to implement topological quantum error correction. ^[42] 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. ^[43]

Implementations

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

Cluster states have also been created in optical lattices, ^[47] 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. ^{[48] [49]} More recently it has been shown that a spin-mixture AKLT state can be used as a resource. ^[50]

See also

• Quantum gate teleportation
• Continuous-variable quantum information
• Quantum algorithm
• Quantum logic gate
• Linear optical quantum computing
• Quantum optics
• Quantum error correction
• Quantum Turing machine
• Adiabatic quantum computation

References

1. Fowler, Austin G.; Goyal, Kovid (2009-02-25). "Topological cluster state quantum computing". Quantum Information & Computation. 9 (9&10): 721–738. arXiv: 0805.3202 . doi:10.26421/QIC9.9-10-1. S2CID   6652655.
2. Raussendorf, R; Harrington, J; Goyal, K (2007-06-29). "Topological fault-tolerance in cluster state quantum computation". New Journal of Physics. 9 (6): 199. arXiv: quant-ph/0703143 . Bibcode:2007NJPh....9..199R. doi:10.1088/1367-2630/9/6/199. ISSN   1367-2630. S2CID   13811487.
3. S. S. Li; G. L. Long; F. S. Bai; S. L. Feng; H. Z. Zheng (2001). "Quantum computing". Proceedings of the National Academy of Sciences. 98 (21): 11847–11848. Bibcode:2001PNAS...9811847L. doi: 10.1073/pnas.191373698 . PMC   59812 . PMID   11562459.
4. E. Grumbling; M. Horowitz (2019). Quantum computing: progress and prospects. National Academies of Sciences, Engineering, and Medicine. p. 2. doi:10.17226/25196. ISBN   978-0-309-47969-1. S2CID   125635007.
5. T. Sleator; H. Weinfurter (1995). "Realizable Universal Quantum Logic Gates". Physical Review Letters. 74 (20): 4087–4090. Bibcode:1995PhRvL..74.4087S. doi:10.1103/PhysRevLett.74.4087. PMID   10058409.
6. T. Hey (1999). "Quantum computing: An introduction". Computing & Control Engineering Journal. 10 (3): 105–112. doi:10.1049/cce:19990303 (inactive 7 December 2024).
7. P. Shor (1998). Quantum Computing (PDF). Documenta Mathematica. p. 468.
8. G.K. Brennen; C.M. Caves; P.S. Jessen; I.H. Deutsch (1999). "Quantum Logic Gates in Optical Lattices". Physical Review Letters. 82 (5): 1060–1063. arXiv: quant-ph/9806021 . Bibcode:1999PhRvL..82.1060B. doi:10.1103/PhysRevLett.82.1060. S2CID   15297433.
9. A. Barenco; C.H. Bennett; R. Cleve; D.P. DiVincenzo; N. Margolus; P. Shor; T. Sleator; J. Smolin; H. Weinfurter (1995). "Elementary gates for quantum computation". Physical Review A. 74 (20): 3457–3467. arXiv: quant-ph/9503016 . Bibcode:1995PhRvA..52.3457B. doi:10.1103/PhysRevA.52.3457. PMID   9912645. S2CID   8764584.
10. S. Lloyd (1995). "Almost Any Quantum Logic Gate is Universal". Physical Review Letters. 75 (2): 346–349. Bibcode:1995PhRvL..75..346L. doi:10.1103/PhysRevLett.75.346. PMID   10059671.
11. J. Joo; C.W. Lee; S. Kono; J. Kim (2019). "Logical measurement-based quantum computation in circuit-QED". Scientific Reports. 9 (1): 16592. arXiv: 1808.07638 . Bibcode:2019NatSR...916592J. doi:10.1038/s41598-019-52866-3. PMC   6851091 . PMID   31719588. S2CID   119440765.
12. M.S. Tame; R. Prevedel; M. Paternostro; P. Bohi; M.S. Kim; A. Zeilinger (2007). "Experimental realization of Deutsch's algorithm in a one-way quantum computer". Physical Review Letters. 98 (14): 140501. arXiv: quant-ph/0611186 . Bibcode:2007PhRvL..98n0501T. doi:10.1103/PhysRevLett.98.140501. PMID   17501253. S2CID   21518741.
13. R. Raussendorf; D. E. Browne & H. J. Briegel (2003). "Measurement-based quantum computation with cluster states". Physical Review A. 68 (2): 022312. arXiv: quant-ph/0301052 . Bibcode:2003PhRvA..68b2312R. doi:10.1103/PhysRevA.68.022312. S2CID   6197709.
14. P. Walther; K. J. Resch; T. Rudolph; E. Schenck; H. Weinfurter; V. Vedral; M. Aspelmeyer; A. Zeilinger (2005). "Experimental one-way quantum computing". Nature. 434 (7030): 169–176. arXiv: quant-ph/0503126 . Bibcode:2005Natur.434..169W. doi:10.1038/nature03347. PMID   15758991. S2CID   119329998.
15. R. Raussendorf & H. J. Briegel (2006). "A One-Way Quantum Computer". Physical Review Letters . 86 (22): 5188–91. arXiv: quant-ph/0510135 . Bibcode:2001PhRvL..86.5188R. doi:10.1103/PhysRevLett.86.5188. PMID   11384453.
16. V. Danos; E. Kashefi; P. Panangaden (2007). "The measurement calculus". Journal of the ACM. 54 (2): 8. arXiv: 0704.1263 . doi:10.1145/1219092.1219096. S2CID   5851623.
17. E. Pius (2010). Automatic Parallelisation of Quantum Circuits Using the Measurement Based Quantum Computing Model (PDF) (MSc thesis). University of Edinburgh.
18. A. Mantri; T.F. Demarie; J.F. Fitzsimons (2017). "Universality of quantum computation with cluster states and (X, Y)-plane measurements". Scientific Reports. 7 (1): 42861. arXiv: 1607.00758 . Bibcode:2017NatSR...742861M. doi:10.1038/srep42861. PMC   5316959 . PMID   28216652.
19. S. Anders; H.J. Briegel (2006). "Fast simulation of stabilizer circuits using a graph state representation". Physical Review A. 73 (2): 022334. arXiv: quant-ph/0504117 . Bibcode:2006PhRvA..73b2334A. doi:10.1103/PhysRevA.73.022334. S2CID   12763101.
20. T. Nutz; A. Milne; P. Shadbolt; T. Rudolph (2017). "Proposal for demonstration of long-range cluster state entanglement in the presence of photon loss". APL Photonics. 2 (6): 066103. arXiv: 1702.01958 . Bibcode:2017APLP....2f6103N. doi:10.1063/1.4983822. S2CID   125732242.
21. M. Gimeno-Segovia; P. Shadbolt; D.E. Browne; T. Rudolph (2015). "From Three-Photon Greenberger-Horne-Zeilinger States to Ballistic Universal Quantum Computation". Physical Review Letters. 115 (2): 020502. arXiv: 1410.3720 . Bibcode:2015PhRvL.115b0502G. doi:10.1103/PhysRevLett.115.020502. PMID   26207455. S2CID   45848374.
22. J.R. Scott; K.C. Balram (2022). "Timing Constraints Imposed by Classical Digital Control Systems on Photonic Implementations of Measurement-Based Quantum Computing". IEEE Transactions on Quantum Engineering. 3: 1–20. arXiv: 2109.04792 . doi:10.1109/TQE.2022.3175587. S2CID   237485449.
23. Browne, Daniel E.; Rudolph, Terry (2005-06-27). "Resource-Efficient Linear Optical Quantum Computation". Physical Review Letters. 95 (1): 010501. arXiv: quant-ph/0405157 . Bibcode:2005PhRvL..95a0501B. doi: 10.1103/physrevlett.95.010501 . ISSN   0031-9007. PMID   16090595.
24. Thomas, Philip; Ruscio, Leonardo; Morin, Olivier; Rempe, Gerhard (2022-08-24). "Efficient generation of entangled multiphoton graph states from a single atom". Nature. 608 (7924): 677–681. arXiv: 2205.12736 . Bibcode:2022Natur.608..677T. doi: 10.1038/s41586-022-04987-5 . ISSN   0028-0836. PMC   9402438 . PMID   36002484.
25. Cogan, Dan; Su, Zu-En; Kenneth, Oded; Gershoni, David (2023-02-09). "Deterministic generation of indistinguishable photons in a cluster state". Nature Photonics. 17 (4): 324–329. Bibcode:2023NaPho..17..324C. doi: 10.1038/s41566-022-01152-2 . ISSN   1749-4885. PMC   10091623 . PMID   37064524.
26. Lindner, Netanel H.; Rudolph, Terry (2009-09-08). "Proposal for Pulsed On-Demand Sources of Photonic Cluster State Strings". Physical Review Letters. 103 (11): 113602. arXiv: 0810.2587 . Bibcode:2009PhRvL.103k3602L. doi: 10.1103/physrevlett.103.113602 . ISSN   0031-9007. PMID   19792371.
27. R. Jozsa (2006). "An introduction to measurement based quantum computation". NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment. 199. arXiv: quant-ph/0508124 .
28. R. Raussendorf; H. J. Briegel (2002). "Computational model underlying the one-way quantum computer". arXiv: quant-ph/0108067 .
29. "OneQubitEulerDecomposer". Qiskit. Retrieved 29 June 2022.
30. "MBQC Quick Start Guide". Paddle Quantum. Retrieved 29 June 2022.
31. "Measurement-Based Quantum Computation Module". Paddle Quantum. Retrieved 1 July 2022.
32. K. Fujii (2015). Quantum Computation with Topological Codes: from qubit to topological fault-tolerance. Springer. p. 28. arXiv: 1504.01444 . ISBN   978-981-287-996-7.
33. D. Gottesman (1998). "The Heisenberg Representation of Quantum Computers". arXiv: quant-ph/9807006 .
34. M. Hein; W. Dur; J. Eisert; R. Raussendorf; M. Van den Nest; H. Jurgen Briegel (2006). "Entanglement in Graph States and its Applications". arXiv: quant-ph/0602096 .
35. R. Raussendorf; J. Harrington; K. Goyal (2006). "A fault-tolerant one-way quantum computer". Annals of Physics. 321 (9): 2242–2270. arXiv: quant-ph/0510135 . Bibcode:2006AnPhy.321.2242R. doi:10.1016/j.aop.2006.01.012. S2CID   14422769.
36. M. Rossi; M. Huber; D. Bruß; C. Macchiavello (2013). "Quantum Hypergraph States". New Journal of Physics. 15 (11): 113022. arXiv: 1211.5554 . Bibcode:2013NJPh...15k3022R. doi:10.1088/1367-2630/15/11/113022. S2CID   40507835.
37. M.E. Cuffaro (2013). "On the Significance of the Gottesman–Knill Theorem". The British Journal for the Philosophy of Science. 68 (1): 91–121. arXiv: 1310.0938 . doi:10.1093/bjps/axv016.
38. K. Fujii (2015). Quantum Computation with Topological Codes: from qubit to topological fault-tolerance. Springer. p. 30. arXiv: 1504.01444 . ISBN   978-981-287-996-7.
39. K. Fujii (2015). Quantum Computation with Topological Codes: from qubit to topological fault-tolerance. Springer. p. 34. arXiv: 1504.01444 . ISBN   978-981-287-996-7.
40. M.A. Nielsen; I.L. Chuang (2000). Quantum Computation and Quantum Information. Cambridge University Press. p. 464. ISBN   978-1-107-00217-3.
41. M. Van den Nest (2008). "Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond". Quantum Information & Computation. 10 (3). arXiv: 0811.0898 .
42. Robert Raussendorf; Jim Harrington; Kovid Goyal (2007). "Topological fault-tolerance in cluster state quantum computation". New Journal of Physics. 9 (6): 199. arXiv: quant-ph/0703143 . Bibcode:2007NJPh....9..199R. doi:10.1088/1367-2630/9/6/199. S2CID   13811487.
43. Robert Raussendorf; Jim Harrington (2007). "Fault-tolerant quantum computation with high threshold in two dimensions". Physical Review Letters. 98 (19): 190504. arXiv: quant-ph/0610082 . Bibcode:2007PhRvL..98s0504R. doi:10.1103/physrevlett.98.190504. PMID   17677613. S2CID   39504821.
44. P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer and A. Zeilinger (2005). "Experimental one-way quantum computing". Nature. 434 (7030): 169–76. arXiv: quant-ph/0503126 . Bibcode:2005Natur.434..169W. doi:10.1038/nature03347. PMID   15758991. S2CID   119329998.
45. Robert Prevedel; Philip Walther; Felix Tiefenbacher; Pascal Böhi; Rainer Kaltenbaek; Thomas Jennewein; Anton Zeilinger (2007). "High-speed linear optics quantum computing using active feed-forward". Nature. 445 (7123): 65–69. arXiv: quant-ph/0701017 . Bibcode:2007Natur.445...65P. doi:10.1038/nature05346. PMID   17203057. S2CID   4416906.
46. Daniel E. Browne; Terry Rudolph (2005). "Resource-efficient linear optical quantum computation". Physical Review Letters. 95 (1): 010501. arXiv: quant-ph/0405157 . Bibcode:2005PhRvL..95a0501B. doi:10.1103/PhysRevLett.95.010501. PMID   16090595. S2CID   27224760.
47. Olaf Mandel; Markus Greiner; Artur Widera; Tim Rom; Theodor W. Hänsch; Immanuel Bloch (2003). "Controlled collisions for multi-particle entanglement of optically trapped atoms". Nature. 425 (6961): 937–40. arXiv: quant-ph/0308080 . Bibcode:2003Natur.425..937M. doi:10.1038/nature02008. PMID   14586463. S2CID   4408587.
48. Tzu-Chieh Wei; Ian Affleck & Robert Raussendorf (2012). "Two-dimensional Affleck-Kennedy-Lieb-Tasaki state on the honeycomb lattice is a universal resource for quantum computation". Physical Review A. 86 (32328): 032328. arXiv: 1009.2840 . Bibcode:2012PhRvA..86c2328W. doi:10.1103/PhysRevA.86.032328. S2CID   118128175.
49. Akimasa Miyake (2011). "Quantum computational capability of a 2D valence bond solid phase". Annals of Physics. 236 (7): 1656–1671. arXiv: 1009.3491 . Bibcode:2011AnPhy.326.1656M. doi:10.1016/j.aop.2011.03.006. S2CID   119243954.
50. Tzu-Chieh Wei; Poya Haghnegahdar; Robert Raussendorf (2014). "Spin mixture AKLT states for universal quantum computation". Physical Review A. 90 (4): 042333. arXiv: 1310.5100 . Bibcode:2014PhRvA..90d2333W. doi:10.1103/PhysRevA.90.042333. S2CID   118460519.

General

• D. Gross; J. Eisert; N. Schuch; D. Perez-Garcia (2007). "Measurement-based quantum computation beyond the one-way model". Physical Review A . 76 (5): 052315. arXiv: 0706.3401 . Bibcode:2007PhRvA..76e2315G. doi:10.1103/PhysRevA.76.052315. S2CID   53409763. Non-cluster resource states
• A. Trisetyarso & R. Van Meter (2010). "Circuit Design for A Measurement-Based Quantum Carry-Lookahead Adder". International Journal of Quantum Information . 8 (5): 843–867. arXiv: 0903.0748 . doi:10.1142/S0219749910006496. S2CID   2587811. Measurement-based quantum computation, quantum carry-lookahead adder