one-way quantum computer

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.{{cite journal |last1=S. S. Li |last2=G. L. Long |last3=F. S. Bai |last4=S. L. Feng |last5=H. Z. Zheng |title=Quantum computing |journal=Proceedings of the National Academy of Sciences |date=2001 |volume=98 |issue=21 |pages=11847–11848 |doi=10.1073/pnas.191373698|pmid=11562459 |pmc=59812 |bibcode=2001PNAS...9811847L |doi-access=free }}{{cite book |last1=E. Grumbling |last2=M. Horowitz |title=Quantum computing: progress and prospects. |date=2019 |publisher=National Academies of Sciences, Engineering, and Medicine. |page=2 |doi=10.17226/25196 |isbn=978-0-309-47969-1|s2cid=125635007 }}{{cite journal |last1=T. Sleator |last2=H. Weinfurter |title=Realizable Universal Quantum Logic Gates |journal=Physical Review Letters |date=1995 |volume=74 |issue=20 |pages=4087–4090 |doi=10.1103/PhysRevLett.74.4087|pmid=10058409 |bibcode=1995PhRvL..74.4087S }} Another key feature for quantum computing relies on the entanglement between the qubits.{{cite journal |last1=T. Hey |title=Quantum computing: An introduction |journal=Computing & Control Engineering Journal |date=1999 |volume=10 |issue=3 |pages=105–112 |doi=10.1049/cce:19990303|doi-broken-date=7 December 2024 }}{{cite book |last1=P. Shor |title=Quantum Computing |date=1998 |publisher=Documenta Mathematica |page=468 |url=http://nozdr.ru/data/media/biblio/kolxoz/M/ICM-1998,%20Berlin.%20Proceedings,%20Vol.%201%20Plenary%20lectures%20(no%20p.%2023-52)%20(Documenta%20Mathematica,%201998)(660s)_M_.pdf#page=434}}{{cite journal |last1=G.K. Brennen |last2=C.M. Caves |last3=P.S. Jessen |last4=I.H. Deutsch |title=Quantum Logic Gates in Optical Lattices |journal=Physical Review Letters |date=1999 |volume=82 |issue=5 |pages=1060–1063 |doi=10.1103/PhysRevLett.82.1060|arxiv=quant-ph/9806021 |bibcode=1999PhRvL..82.1060B |s2cid=15297433 }}

File:Bernstein Vazirani quantum circuit.pngs (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.{{cite journal |last1=A. Barenco |last2=C.H. Bennett |last3=R. Cleve |last4=D.P. DiVincenzo |last5=N. Margolus |last6=P. Shor |last7=T. Sleator |last8=J. Smolin |last9=H. Weinfurter |title=Elementary gates for quantum computation |journal=Physical Review A |date=1995 |volume=74 |issue=20 |pages=3457–3467 |arxiv=quant-ph/9503016 |doi=10.1103/PhysRevA.52.3457|pmid=9912645 |bibcode=1995PhRvA..52.3457B |s2cid=8764584 }}{{cite journal |last1=S. Lloyd |title=Almost Any Quantum Logic Gate is Universal |journal=Physical Review Letters |date=1995 |volume=75 |issue=2 |pages=346–349 |doi=10.1103/PhysRevLett.75.346|pmid=10059671 |bibcode=1995PhRvL..75..346L }} 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 $k$ of input qubits with a cluster of $a$ ancillary qubits, forming an overall source state of $a+k=n$ qubits, and then measuring a number $m$ of them.{{cite journal |last1=J. Joo |last2=C.W. Lee |last3=S. Kono |last4=J. Kim |title=Logical measurement-based quantum computation in circuit-QED |journal=Scientific Reports |date=2019 |volume=9 |issue=1 |page=16592 |arxiv=1808.07638 |doi=10.1038/s41598-019-52866-3|pmid=31719588 |pmc=6851091 |bibcode=2019NatSR...916592J |s2cid=119440765 }}{{cite journal |last1=M.S. Tame |last2=R. Prevedel |last3=M. Paternostro |last4=P. Bohi |last5=M.S. Kim |last6=A. Zeilinger |title=Experimental realization of Deutsch's algorithm in a one-way quantum computer. |journal=Physical Review Letters |date=2007 |volume=98 |issue=14 |page=140501 | arxiv=quant-ph/0611186 |doi=10.1103/PhysRevLett.98.140501|pmid=17501253 |bibcode=2007PhRvL..98n0501T |s2cid=21518741 }} The remaining $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.{{cite journal |author1=R. Raussendorf |author2=D. E. Browne |author3=H. J. Briegel |name-list-style=amp | title=Measurement-based quantum computation with cluster states |journal=Physical Review A| year=2003| volume=68 | issue=2 | pages=022312 |arxiv=quant-ph/0301052|doi=10.1103/PhysRevA.68.022312|bibcode = 2003PhRvA..68b2312R |s2cid=6197709 }}{{cite journal |last1=P. Walther |last2=K. J. Resch |last3=T. Rudolph |last4=E. Schenck |last5=H. Weinfurter |last6=V. Vedral |last7=M. Aspelmeyer |last8=A. Zeilinger |title=Experimental one-way quantum computing. |journal=Nature |date=2005 |volume=434 |issue=7030 |pages=169–176 |arxiv=quant-ph/0503126 |doi=10.1038/nature03347|pmid=15758991 |bibcode=2005Natur.434..169W |s2cid=119329998 }}{{cite journal |author1=R. Raussendorf |author2=H. J. Briegel |name-list-style=amp | title=A One-Way Quantum Computer | year=2006 |journal=Physical Review Letters |volume=86 |pages=5188–91 | doi=10.1103/PhysRevLett.86.5188 | pmid=11384453 | issue=22 | bibcode=2001PhRvL..86.5188R|arxiv=quant-ph/0510135 }}

The standard process of measurement-based quantum computing consists of three steps:{{cite journal |last1=V. Danos |last2=E. Kashefi |last3=P. Panangaden |title=The measurement calculus |journal=Journal of the ACM |date=2007 |volume=54 |issue=2 |page=8 |arxiv=0704.1263 |doi=10.1145/1219092.1219096|s2cid=5851623 }}{{cite thesis |last1=E. Pius |title=Automatic Parallelisation of Quantum Circuits Using the Measurement Based Quantum Computing Model |date=2010 |url=https://static.epcc.ed.ac.uk/dissertations/hpc-msc/2009-2010/Einar%20Pius.pdf |publisher=University of Edinburgh |type=MSc thesis}} 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: in order to carry on the computation in a deterministic way, some correction operators, called byproducts, are introduced.

File:Qcircuit CC.svg

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 $|\; \backslash psi\; \backslash rangle\; =\; \backslash alpha\; |0\backslash rangle\; +\; \backslash beta\; |1\; \backslash 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 $|+\backslash rangle$ state:{{cite journal |last1=A. Mantri |last2=T.F. Demarie |last3=J.F. Fitzsimons |title=Universality of quantum computation with cluster states and (X, Y)-plane measurements |journal=Scientific Reports |date=2017 |volume=7 |issue=1 |page=42861 |arxiv=1607.00758 |doi=10.1038/srep42861|pmid=28216652 |pmc=5316959 |bibcode=2017NatSR...742861M }}

:$|+\backslash rangle\; =\; \backslash tfrac\{|\; 0\; \backslash rangle\; +\; |\; 1\; \backslash rangle\}\{\backslash sqrt\{2\}\},$

where $|\; 0\; \backslash rangle$ and $|\; 1\; \backslash rangle$ are the quantum encoding for the classical $0$ and $1$ bits:

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

A register with $n$ qubits will be therefore set as $|\; +\; \backslash rangle^\{\backslash otimes\; n\}$. Thereafter, the entanglement between two qubits can be performed by applying a (Controlled) $CZ$ gate operation.{{cite journal |last1=S. Anders |last2=H.J. Briegel |title=Fast simulation of stabilizer circuits using a graph state representation |journal=Physical Review A |date=2006 |volume=73 |issue=2 |page=022334 |arxiv=quant-ph/0504117 |doi=10.1103/PhysRevA.73.022334|bibcode=2006PhRvA..73b2334A |s2cid=12763101 }} The matrix representation of such two-qubits operator is given by

:

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

:$$

\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 $CZ$ gate over two ancillae in the $|+\; \backslash rangle$ state, the overall state

:$CZ|\; ++\; \backslash rangle\; =\; \backslash frac\{|\; 0+\; \backslash rangle\; +\; |\; 1-\; \backslash rangle\}\{\backslash 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 $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.{{cite journal |last1=T. Nutz |last2=A. Milne |last3=P. Shadbolt |last4=T. Rudolph |title=Proposal for demonstration of long-range cluster state entanglement in the presence of photon loss |journal=APL Photonics |date=2017 |volume=2 |issue=6 |page=066103 |doi=10.1063/1.4983822|arxiv=1702.01958 |bibcode=2017APLP....2f6103N |s2cid=125732242 }}{{cite journal |last1=M. Gimeno-Segovia |last2=P. Shadbolt |last3=D.E. Browne |last4=T. Rudolph |title=From Three-Photon Greenberger-Horne-Zeilinger States to Ballistic Universal Quantum Computation |journal=Physical Review Letters |date=2015 |volume=115 |issue=2 |page=020502 |doi=10.1103/PhysRevLett.115.020502|pmid=26207455 |arxiv=1410.3720 |bibcode=2015PhRvL.115b0502G |s2cid=45848374 }}{{cite journal |last1=J.R. Scott |last2=K.C. Balram |title=Timing Constraints Imposed by Classical Digital Control Systems on Photonic Implementations of Measurement-Based Quantum Computing |journal=IEEE Transactions on Quantum Engineering |date=2022 |volume=3 |pages=1–20 |arxiv=2109.04792 |doi=10.1109/TQE.2022.3175587|s2cid=237485449 }} However, deterministic $CZ$ gates between photons are difficult to realize. Therefore, probabilistic entangling gates such as Bell state measurements are typically considered.{{cite journal | last1=Browne | first1=Daniel E. | last2=Rudolph | first2=Terry | title=Resource-Efficient Linear Optical Quantum Computation | journal=Physical Review Letters |volume=95 | issue=1 | date=2005-06-27 | issn=0031-9007 | doi=10.1103/physrevlett.95.010501 | doi-access=free | page=010501| pmid=16090595 | arxiv=quant-ph/0405157 | bibcode=2005PhRvL..95a0501B }} Furthermore, quantum emitters such as atoms{{cite journal | last1=Thomas | first1=Philip | last2=Ruscio | first2=Leonardo | last3=Morin | first3=Olivier | last4=Rempe | first4=Gerhard | title=Efficient generation of entangled multiphoton graph states from a single atom | journal=Nature | volume=608 | issue=7924 | date=2022-08-24 | issn=0028-0836 | doi=10.1038/s41586-022-04987-5 | doi-access=free | pages=677–681| pmid=36002484 | pmc=9402438 | arxiv=2205.12736 | bibcode=2022Natur.608..677T }} or quantum dots{{cite journal | last1=Cogan | first1=Dan | last2=Su | first2=Zu-En | last3=Kenneth | first3=Oded | last4=Gershoni | first4=David | title=Deterministic generation of indistinguishable photons in a cluster state | journal=Nature Photonics | date=2023-02-09 | volume=17 | issue=4 | pages=324–329 | issn=1749-4885 | doi=10.1038/s41566-022-01152-2 | doi-access=free | pmid=37064524 | bibcode=2023NaPho..17..324C | pmc=10091623 }} can be used to create deterministic entanglement between photonic qubits.{{cite journal | last1=Lindner | first1=Netanel H. | last2=Rudolph | first2=Terry | title=Proposal for Pulsed On-Demand Sources of Photonic Cluster State Strings | journal=Physical Review Letters | volume=103 | issue=11 | date=2009-09-08 | issn=0031-9007 | doi=10.1103/physrevlett.103.113602 | doi-access=free | page=113602| pmid=19792371 | arxiv=0810.2587 | bibcode=2009PhRvL.103k3602L }}

File:X-Z gates.png

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 $O$ with two possible eigenvectors, say $|\; o\_1\; \backslash rangle$ and $|\; o\_2\; \backslash rangle$, and suppose to deal with a multi-particle quantum system $|\; \backslash Psi\; \backslash rangle$. Measuring the $i$-th qubit by the $O$ observable means to project the $|\; \backslash Psi\; \backslash rangle$ state over the eigenvectors of $O$:

:$|\; \backslash Psi\text{'}\; \backslash rangle\; =\; |o\_i\; \backslash rangle\; \backslash langle\; o\_i\; |\; \backslash Psi\; \backslash rangle$.

The actual state of the $i$-th qubit is now $|o\_i\; \backslash rangle$, which can turn to be $|\; o\_1\; \backslash rangle$ or $|\; o\_2\; \backslash 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 $M(\backslash theta)\; =\; \backslash cos(\backslash theta)X\; +\; \backslash sin(\backslash theta)Y$ observable:

:,

where $X$ and $Y$ belong to the Pauli matrices. The eigenvectors of $M(\backslash theta)$ are $|\backslash theta\_\backslash pm\; \backslash rangle\; =\; |0\; \backslash rangle\; \backslash pm\; e^\{i\; \backslash theta\}\; |1\; \backslash rangle$. Measuring a qubit on the $X$-$Y$ plane, i.e. by the $M(\backslash theta)$ observable, means to project it over $|\backslash theta\_+\; \backslash rangle$ or $|\backslash theta\_-\; \backslash 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 $|o\_i\; \backslash rangle\; \backslash langle\; o\_i\; |$ notation, it is common to find $\backslash langle\; o\_i\; |$ to indicate a projective measurement over the $i$-th qubit.

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 $X$-$Y$ plane, the output may change whether the outcome had been $|\; \backslash theta\_+\; \backslash rangle$ or $|\; \backslash theta\_-\; \backslash 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.{{cite journal |last1=R. Jozsa |title=An introduction to measurement based quantum computation |journal=NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment |date=2006 |volume=199 |arxiv=quant-ph/0508124}} The byproduct operators which can be implemented are $X$ and $Z$.{{cite arXiv |last1=R. Raussendorf |last2=H. J. Briegel |title=Computational model underlying the one-way quantum computer |date=2002 |eprint=quant-ph/0108067}} Depending on the outcome of the measurement, a byproduct operator can be applied or not to the output state: a $X$ correction over the $j$-th qubit, depending on the outcome of the measurement performed over the $i$-th qubit via the $M(\backslash theta)$ observable, can be described as $X\_j^\{s\_i\}$, where $s\_i$ is set to be $0$ if the outcome of measurement was $|\; \backslash theta\_+\; \backslash rangle$, otherwise is $1$ if it was $|\; \backslash theta\_-\; \backslash rangle$. In the first case, no correction will occur, in the latter one a $X$ operator will be implemented on the $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.

File:Mbqc-fig-single qubit pattern.jpg

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. In the CME formalism, the operation of entanglement between the $i$ and $j$ qubits is referred to as $E\_\{ij\}$. The measurement on the $i$ qubit, in the $X$-$Y$ plane, with respect to a $\backslash theta$ angle, is defined as $M\_i^\backslash theta$. At last, the $X$ byproduct over a $i$ qubit, with respect to the measurement over a $j$ qubit, is described as $X\_i^\{s\_j\}$, where $s\_j$ is set to $0$ if the outcome is the $|\; \backslash theta\_+\; \backslash rangle$ state, $1$ when the outcome is $|\; \backslash theta\_-\; \backslash rangle$. The same notation holds for the $Z$ byproducts.

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

As an illustrative example, consider the Euler rotation in the $XZX$ basis: such operation, in the gate model of quantum computation, is described as{{cite web |title=OneQubitEulerDecomposer |url=https://qiskit.org/documentation/stubs/qiskit.quantum_info.OneQubitEulerDecomposer.html |website=Qiskit |access-date=29 June 2022}}

:$e^\{i\; \backslash gamma\}R\_X(\backslash phi)\; R\_Z(\backslash theta)R\_X(\backslash lambda)$,

where $\backslash phi,\; \backslash theta,\; \backslash lambda$ are the angles for the rotation, while $\backslash 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:{{cite web |title=MBQC Quick Start Guide |url=https://qml.baidu.com/tutorials/measurement-based-quantum-computation/mbqc-quick-start-guide.html |website=Paddle Quantum |access-date=29 June 2022}}

:$Z\_5^\{s\_1+s\_3\}X\_5^\{s\_2+s\_4\}\; [M\_4^\{-\backslash phi\}]^\{s\_1+s\_3\}\; [M\_3^\{-\backslash theta\}]^\{s\_2\}\; [M\_2^\{-\backslash lambda\}]^\{s\_1\}\; M\_1^\{0\}\; E\_\{4,5\}\; E\_\{3,4\}\; E\_\{2,3\}\; E\_\{1,2\}$,

where the input state $|\; \backslash psi\; \backslash rangle\; =\; \backslash alpha\; |\; 0\; \backslash rangle\; +\; \backslash beta\; |\; 1\; \backslash rangle$ is the qubit $1$, all the other qubits are auxiliary ancillae and therefore have to be prepared in the $|\; +\; \backslash rangle$ state. In the first step, the input state $|\backslash psi\; \backslash 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 $E\_\{ij\}$ between the qubits can be performed by the $CZ$ gates.

In the second place, the first and the second qubits must be measured by the $M(\backslash theta)$ observable, which means they must be projected onto the eigenstates $|\; \backslash theta\; \backslash rangle$ of such observable. When the $\backslash theta$ is zero, the $|\; \backslash theta\_\backslash pm\; \backslash rangle$ states reduce to $|\backslash pm\; \backslash rangle$ ones, i.e. the eigenvectors for the $X$ Pauli operator. The first measurement $M\_1^\{0\}$ is performed on the qubit $1$ with a $\backslash theta=0$ angle, which means it has to be projected onto the $\backslash langle\; \backslash pm\; |$ states. The second measurement $[M\_2^\{-\backslash lambda\}]^\{s\_1\}$ is performed with respect to the $-\backslash lambda$ angle, i.e. the second qubit has to be projected on the $\backslash langle\; 0\; |\; \backslash pm\; e^\{i\; \backslash lambda\}\; \backslash langle\; 1\; |$ state. However, if the outcome from the previous measurement has been $\backslash langle\; -\; |$, the sign of the $\backslash lambda$ angle has to be flipped, and the second qubit will be projected to the $\backslash langle\; 0\; |\; +\; e^\{-i\; \backslash lambda\}\; \backslash langle\; 1\; |$ state; if the outcome from the first measurement has been $\backslash langle\; +\; |$, no flip needs to be performed. The same operations have to be repeated for the third $[M\_3^\{\backslash theta\}]^\{s\_2\}$ and the fourth $[M\_4^\{\backslash phi\}]^\{s\_1+s\_3\}$ measurements, according to the respective angles and sign flips. The sign over the $\backslash phi$ angle is set to be $(-)^\{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 $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 $\backslash langle\; \backslash phi\_+\; |$ and $\backslash langle\; \backslash lambda\_+\; |$, no correction will be conducted by the $X\_5$ operator, as $s\_2=s\_4=0$. The same result holds for a $\backslash langle\; \backslash phi\_-\; |$ $\backslash langle\; \backslash lambda\_-\; |$ outcome, as $s\_2=s\_4=1$ and thus the squared Pauli operator $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.

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.{{cite web |title=Measurement-Based Quantum Computation Module |url=https://qml.baidu.com/tutorials/measurement-based-quantum-computation/measurement-based-quantum-computation-module.html |website=Paddle Quantum |access-date=1 July 2022}}

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

:.

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

:$J(\backslash theta)\; =\; X\_2^\{s\_1\}\; M\_1^\{-\backslash theta\}\; E\_\{1,2\}$

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

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

:$E\_\{ij\}\; Z\_i^s\; =\; Z\_i^s\; E\_\{ij\}$

:$E\_\{ij\}\; X\_i^s\; =\; X\_i^s\; Z\_j^s\; E\_\{ij\}$

:$E\_\{ij\}\; A\_k\; =\; A\_k\; E\_\{ij\}$.

The entanglement operator $E\_\{ij\}$ commutes with the $Z$ Pauli operators and with any other operator $A\_k$ acting on a qubit $k\backslash neq\; i,j$, but not with the $X$ Pauli operators acting on the $i$-th or $j$-th qubits.

The measurement operations $M\_i^\backslash theta$ commute with the corrections in the following manner:

:$M\_i^\backslash theta\; X\_i^s\; =\; [M\_i^\backslash theta]^s$

:$M\_i^\backslash theta\; Z\_i^t\; =\; S\_i^t\; M\_i^\backslash theta$,

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

:$M\_i^0\; X\_i^s\; =\; M\_i^0$

:$M\_i^\{\backslash pi/2\}\; X\_i^s\; =\; M\_i^\{\backslash pi/2\}\; Z\_i^s$.

The action of the signal shifting operator $S\_i^t$ can be explained through its rules of commutation:

:$X\_i^\{s\}\; S\_i^t\; =\; S\_i^t\; X\_i^\{s[(s\_i+t)/s\_i]\}$

:$Z\_i^\{s\}\; S\_i^t\; =\; S\_i^t\; Z\_i^\{s[(s\_i+t)/s\_i]\}$.

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

{{Group theory sidebar |Basics}}

When preparing the source state of entangled qubits, a graph representation can be given by the stabilizer group. The stabilizer group $\backslash mathcal\{S\}\_n$ is an abelian subgroup from the Pauli group $\backslash mathcal\{P\}\_n$, which one can be described by its generators $\backslash \{\backslash pm\; 1,\; \backslash pm\; i\backslash \}\; \backslash times\; \backslash \{I,X,Y,Z\backslash \}^\{\backslash otimes\; n\}$.{{cite book |last1=K. Fujii |title=Quantum Computation with Topological Codes: from qubit to topological fault-tolerance |date=2015 |publisher=Springer |page=28 |arxiv=1504.01444 |isbn=978-981-287-996-7}}{{cite arXiv |last1=D. Gottesman |title=The Heisenberg Representation of Quantum Computers |date=1998 |eprint=quant-ph/9807006}} A stabilizer state is a $n$-qubit state $|\; \backslash Psi\; \backslash rangle$ which is a unique eigenstate for the generators $S\_i$ of the $\backslash mathcal\{S\}\_n$ stabilizer group:

:$S\_i\; |\; \backslash Psi\; \backslash rangle\; =\; |\; \backslash Psi\; \backslash rangle.$

Of course, $S\_i\; \backslash in\; \backslash mathcal\{S\}\_n\; \backslash ,\; \backslash forall\; i$.

File:Three Vertex Graph.png

It is therefore possible to define a $n$ qubit graph state $|\; G\; \backslash rangle$ as a quantum state associated with a graph, i.e. a set $G=(V,E)$ whose vertices $V$ correspond to the qubits, while the edges $E$ represent the entanglements between the qubits themselves. The vertices can be labelled by a $i$ index, while the edges, linking the $i$-th vertex to the $j$-th one, by two-indices labels, such as $(i,j)$.{{cite arXiv |last1=M. Hein |last2=W. Dur |last3=J. Eisert |last4=R. Raussendorf |last5=M. Van den Nest |last6=H. Jurgen Briegel |title=Entanglement in Graph States and its Applications |date=2006 |eprint=quant-ph/0602096}} In the stabilizer formalism, such graph structure can be encoded by the $K\_i$ generators of $\backslash mathcal\{S\}\_n$, defined as{{cite journal |last1=R. Raussendorf |last2=J. Harrington |last3=K. Goyal |title=A fault-tolerant one-way quantum computer. |journal=Annals of Physics |date=2006 |volume=321 |issue=9 |pages=2242–2270 |doi=10.1016/j.aop.2006.01.012 |arxiv=quant-ph/0510135|bibcode=2006AnPhy.321.2242R |s2cid=14422769 }}{{cite journal |last1=M. Rossi |last2=M. Huber |last3=D. Bruß |last4=C. Macchiavello |title=Quantum Hypergraph States |journal=New Journal of Physics |date=2013 |volume=15 |issue=11 |page=113022 |arxiv=1211.5554 |doi=10.1088/1367-2630/15/11/113022|bibcode=2013NJPh...15k3022R |s2cid=40507835 }}

:$K\_i\; =\; X\_i\; \backslash prod\_\{j\; \backslash in\; (i,j)\}\; Z\_j$,

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

:$\backslash langle\; K\_1,\; K\_2,\; ...,\; K\_n\backslash rangle$.

While the number of $X\_i$ is fixed for each $K\_i$ generator, the number of $Z\_j$ may differ, with respect to the connections implemented by the edges in the graph.

{{See also|Clifford gates}}

The Clifford group $\backslash mathcal\{C\}\_n$ is composed by elements which leave invariant the elements from the Pauli's group $\backslash mathcal\{P\}\_n$:{{cite journal |last1=M.E. Cuffaro |title=On the Significance of the Gottesman–Knill Theorem |journal=The British Journal for the Philosophy of Science |date=2013 |volume=68 |issue=1 |pages=91–121 |arxiv=1310.0938 |doi=10.1093/bjps/axv016}}

:$\backslash mathcal\{C\}\_n\; =\; \backslash \{\; U\; \backslash in\; SU(2^n)\; \backslash ;\; |\; \backslash ;\; U\; S\; U^\backslash dagger\; \backslash in\; \backslash mathcal\{P\}\_n,\; S\; \backslash in\; \backslash mathcal\{P\}\_n\; \backslash \}$.

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

:.

Consider a state $|\; G\; \backslash rangle$ which is stabilized by a set of stabilizers $S\_i$. Acting via an element $U$ from the Clifford group on such state, the following equalities hold:{{cite book |last1=K. Fujii |title=Quantum Computation with Topological Codes: from qubit to topological fault-tolerance. |date=2015 |publisher=Springer |page=30 |arxiv=1504.01444 |isbn=978-981-287-996-7}}

:$U|G\backslash rangle\; =\; U\; S\_i\; |G\backslash rangle\; =\; U\; S\_i\; U^\backslash dagger\; U\; |G\backslash rangle\; =\; S\text{'}\_i\; U\; |G\backslash rangle$.

Therefore, the $U$ operations map the $|G\backslash rangle$ state to $U\; |G\backslash rangle$ and its $S\_i$ stabilizers to $U\; S\_i\; U^\backslash dagger$. Such operation may give rise to different representations for the $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 $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 $P(x)$ for a given output $x$ from the circuit.{{cite book |last1=K. Fujii |title=Quantum Computation with Topological Codes: from qubit to topological fault-tolerance. |date=2015 |publisher=Springer |page=34 |arxiv=1504.01444 |isbn=978-981-287-996-7}}{{cite book |last1=M.A. Nielsen |last2=I.L. Chuang |title=Quantum Computation and Quantum Information |date=2000 |publisher=Cambridge University Press |isbn=978-1-107-00217-3 |page=464}}{{cite journal |last1=M. Van den Nest |title=Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond |journal=Quantum Information & Computation |date=2008 |volume=10 |issue=3 |arxiv=0811.0898}}

Measurement-based computation on a periodic 3D lattice cluster state can be used to implement topological quantum error correction.{{cite journal |author1=Robert Raussendorf |author2=Jim Harrington |author3=Kovid Goyal | title=Topological fault-tolerance in cluster state quantum computation | journal=New Journal of Physics | volume=9 |issue=6 | pages=199 | year=2007 |arxiv = quant-ph/0703143 |bibcode = 2007NJPh....9..199R |doi = 10.1088/1367-2630/9/6/199 |s2cid=13811487 }} 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.{{cite journal |author1=Robert Raussendorf |author2=Jim Harrington | title=Fault-tolerant quantum computation with high threshold in two dimensions | journal= Physical Review Letters| volume=98 |issue=19 | pages=190504 | year=2007 | arxiv=quant-ph/0610082| doi=10.1103/physrevlett.98.190504 | pmid=17677613| bibcode=2007PhRvL..98s0504R |s2cid=39504821 }}

One-way quantum computation has been demonstrated by running the 2 qubit Grover's algorithm on a 2x2 cluster state of photons.{{cite journal | author=P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer and A. Zeilinger| title=Experimental one-way quantum computing| journal=Nature| year=2005| volume=434| pages=169–76 |doi=10.1038/nature03347 | pmid=15758991 | issue=7030 |arxiv = quant-ph/0503126 |bibcode = 2005Natur.434..169W | s2cid=119329998}}{{cite journal |author1=Robert Prevedel |author2=Philip Walther |author3=Felix Tiefenbacher |author4=Pascal Böhi |author5=Rainer Kaltenbaek |author6-link=Thomas Jennewein |author6=Thomas Jennewein |author7=Anton Zeilinger | title=High-speed linear optics quantum computing using active feed-forward| journal=Nature| year=2007| volume=445 | pages=65–69 |doi=10.1038/nature05346 | pmid=17203057 | issue=7123|arxiv = quant-ph/0701017 |bibcode = 2007Natur.445...65P |s2cid=4416906 }} A linear optics quantum computer based on one-way computation has been proposed.{{cite journal |author1=Daniel E. Browne |author2=Terry Rudolph | title=Resource-efficient linear optical quantum computation| journal=Physical Review Letters| year=2005| volume=95 | pages=010501 |arxiv=quant-ph/0405157|doi=10.1103/PhysRevLett.95.010501 | pmid=16090595 | issue=1 | bibcode=2005PhRvL..95a0501B|s2cid=27224760 }}

Cluster states have also been created in optical lattices,{{cite journal |author1=Olaf Mandel |author2=Markus Greiner |author3=Artur Widera |author4=Tim Rom |author5=Theodor W. Hänsch |author6=Immanuel Bloch | title=Controlled collisions for multi-particle entanglement of optically trapped atoms| journal=Nature| year=2003| volume=425 | pages=937–40|doi=10.1038/nature02008 | pmid=14586463 | issue=6961|arxiv = quant-ph/0308080 |bibcode = 2003Natur.425..937M |s2cid=4408587 }} but were not used for computation as the atom qubits were too close together to measure individually.

It has been shown that the (spin $\backslash tfrac\{3\}\{2\}$) AKLT state on a 2D honeycomb lattice can be used as a resource for MBQC.{{cite journal |author1=Tzu-Chieh Wei |author2=Ian Affleck |author3=Robert Raussendorf |name-list-style=amp | title=Two-dimensional Affleck-Kennedy-Lieb-Tasaki state on the honeycomb lattice is a universal resource for quantum computation|journal= Physical Review A| year=2012| volume=86| issue=32328 |pages=032328 | arxiv=1009.2840| doi=10.1103/PhysRevA.86.032328 |bibcode=2012PhRvA..86c2328W|s2cid=118128175 }}{{cite journal | author = Akimasa Miyake | title=Quantum computational capability of a 2D valence bond solid phase | journal=Annals of Physics| year=2011| volume=236| issue=7| pages=1656–1671| arxiv=1009.3491 | doi=10.1016/j.aop.2011.03.006| bibcode=2011AnPhy.326.1656M| s2cid=119243954 }}

More recently it has been shown that a spin-mixture AKLT state can be used as a resource.{{cite journal| title=Spin mixture AKLT states for universal quantum computation| journal=Physical Review A| volume=90| issue=4| pages=042333| arxiv=1310.5100|author1=Tzu-Chieh Wei |author2=Poya Haghnegahdar |author3=Robert Raussendorf |bibcode=2014PhRvA..90d2333W|doi=10.1103/PhysRevA.90.042333| year=2014| s2cid=118460519}}

{{div col|colwidth=25em}}

• 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
• Hamiltonian quantum computation

{{div col end}}

{{reflist}}

;General

{{refbegin}}

• {{cite journal |author1=D. Gross |author2=J. Eisert |author3=N. Schuch |author4=D. Perez-Garcia | title=Measurement-based quantum computation beyond the one-way model| journal=Physical Review A| year=2007| volume=76 | issue=5 | pages=052315 |arxiv=0706.3401|doi=10.1103/PhysRevA.76.052315|bibcode = 2007PhRvA..76e2315G |s2cid=53409763 }} Non-cluster resource states
• {{cite journal |author1=A. Trisetyarso |author2=R. Van Meter |name-list-style=amp | title=Circuit Design for A Measurement-Based Quantum Carry-Lookahead Adder| journal=International Journal of Quantum Information | year=2010| volume=8 | issue=5| pages=843–867 |arxiv=0903.0748|doi=10.1142/S0219749910006496|s2cid=2587811 }} Measurement-based quantum computation, quantum carry-lookahead adder

{{refend}}

{{Quantum computing}}

Category:Quantum information science

Category:Information theory

Category:Models of computation