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. Another key feature for quantum computing relies on the entanglement between the qubits. s (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. 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. 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. General procedure The standard process of measurement-based quantum computing consists of three steps: 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: : |+\rangle = \tfrac{| 0 \rangle + | 1 \rangle}{\sqrt{2}}, where | 0 \rangle and | 1 \rangle are the quantum encoding for the classical 0 and 1 bits: : | 0 \rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix};\quad | 1 \rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} . A register with n qubits will be therefore set as | + \rangle^{\otimes n} . Thereafter, the entanglement between two qubits can be performed by applying a (Controlled) CZ gate operation. The matrix representation of such two-qubits operator is given by : 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 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 |+ \rangle state, the overall state :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 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. However, deterministic CZ gates between photons are difficult to realize. Therefore, probabilistic entangling gates such as Bell state measurements are typically considered. Furthermore, quantum emitters such as atoms or quantum dots can be used to create deterministic entanglement between photonic qubits. Measuring the qubits 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 \rangle and | o_2 \rangle, and suppose to deal with a multi-particle quantum system | \Psi \rangle. Measuring the i-th qubit by the O observable means to project the | \Psi \rangle state over the eigenvectors of O: The byproduct operators which can be implemented are X and Z. 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(\theta) observable, can be described as X_j^{s_i}, where s_i is set to be 0 if the outcome of measurement was | \theta_+ \rangle, otherwise is 1 if it was | \theta_- \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. ==CME pattern==

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. : e^{i \gamma}R_X(\phi) R_Z(\theta)R_X(\lambda) , where \phi, \theta, \lambda are the angles for the rotation, while \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: :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 | \psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle is the qubit 1, all the other qubits are auxiliary ancillae and therefore have to be prepared in the | + \rangle state. In the first step, the input state |\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 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(\theta) observable, which means they must be projected onto the eigenstates | \theta \rangle of such observable. When the \theta is zero, the | \theta_\pm \rangle states reduce to |\pm \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 \theta=0 angle, which means it has to be projected onto the \langle \pm | states. The second measurement [M_2^{-\lambda}]^{s_1} is performed with respect to the -\lambda angle, i.e. the second qubit has to be projected on the \langle 0 | \pm e^{i \lambda} \langle 1 | state. However, if the outcome from the previous measurement has been \langle - |, the sign of the \lambda angle has to be flipped, and the second qubit will be projected to the \langle 0 | + e^{-i \lambda} \langle 1 | state; if the outcome from the first measurement has been \langle + |, no flip needs to be performed. The same operations have to be repeated for the third [M_3^{\theta}]^{s_2} and the fourth [M_4^{\phi}]^{s_1+s_3} measurements, according to the respective angles and sign flips. The sign over the \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 \langle \phi_+ | and \langle \lambda_+ |, no correction will be conducted by the X_5 operator, as s_2=s_4=0. The same result holds for a \langle \phi_- | \langle \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. ==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. Such conversion can be carried on by using a universal set of logic gates composed by the CZ and the J(\theta) operators: therefore, any circuit can be decomposed into a set of CZ and the J(\theta) gates. The J(\theta) single-qubit operator is defined as follows: :J(\theta) = \frac{1}{\sqrt 2} \begin{pmatrix} 1 & e^{i \theta} \\ 1 & -e^{i\theta} \end{pmatrix}. The J(\theta) can be converted into a CME pattern as follows, with qubit 1 being the input and qubit 2 being the output: :J(\theta) = X_2^{s_1} M_1^{-\theta} E_{1,2} which means, to implement a J(\theta) operator, the input qubits | \psi \rangle must be entangled with an ancilla qubit | + \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(\theta) gate has been decomposed into the CME pattern, the operations in the overall computation will consist of E_{ij} entanglements, M_i^{-\theta_i} measurements and 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 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\neq i,j, but not with the X Pauli operators acting on the i-th or j-th qubits. Pauli simplification The measurement operations M_i^\theta commute with the corrections in the following manner: :M_i^\theta X_i^s = [M_i^\theta]^s :M_i^\theta Z_i^t = S_i^t M_i^\theta, where [M_i^\theta]^s=M_i^{(-)^s\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 \theta angles, some simplifications, called Pauli simplifications, can be introduced: :M_i^0 X_i^s = M_i^0 :M_i^{\pi/2} X_i^s = M_i^{\pi/2} Z_i^s. Signal shifting 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. ==Stabilizer formalism==

When preparing the source state of entangled qubits, a graph representation can be given by the stabilizer group. The stabilizer group \mathcal{S}_n is an abelian subgroup from the Pauli group \mathcal{P}_n, which one can be described by its generators \{\pm 1, \pm i\} \times \{I,X,Y,Z\}^{\otimes n}. A stabilizer state is a n-qubit state | \Psi \rangle which is a unique eigenstate for the generators S_i of the \mathcal{S}_n stabilizer group: In the stabilizer formalism, such graph structure can be encoded by the K_i generators of \mathcal{S}_n, defined as : K_i = X_i \prod_{j \in (i,j)} Z_j , where {j \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: :\langle K_1, K_2, ..., K_n\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. The Clifford group The Clifford group \mathcal{C}_n is composed by elements which leave invariant the elements from the Pauli's group \mathcal{P}_n: :\mathcal{C}_n = \{ U \in SU(2^n) \; | \; U S U^\dagger \in \mathcal{P}_n, S \in \mathcal{P}_n \}. 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): : 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 | G \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: :U|G\rangle = U S_i |G\rangle = U S_i U^\dagger U |G\rangle = S'_i U |G\rangle. Therefore, the U operations map the |G\rangle state to U |G\rangle and its S_i stabilizers to U S_i U^\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. ==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. 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. Implementations One-way quantum computation has been demonstrated by running the 2 qubit Grover's algorithm on a 2x2 cluster state of photons. A linear optics quantum computer based on one-way computation has been proposed. Cluster states have also been created in optical lattices, 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 \tfrac{3}{2}) AKLT state on a 2D honeycomb lattice can be used as a resource for MBQC. More recently it has been shown that a spin-mixture AKLT state can be used as a resource. ==See also==