Method of quantum computing
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, 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. 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. Another key feature for quantum computing relies on the entanglement between the qubits.
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 formula_1 of input qubits with a cluster of formula_2 ancillary qubits, forming an overall source state of formula_3 qubits, and then measuring a number formula_4 of them. The remaining formula_5 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: in order to carry on the computation in a deterministic way, some correction operators, called byproducts, are introduced.
Preparing the source state.
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 formula_6 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 formula_7 state:
formula_8
where formula_9 and formula_10 are the quantum encoding for the classical formula_11 and formula_12 bits:
formula_13.
A register with formula_14 qubits will be therefore set as formula_15. Thereafter, the entanglement between two qubits can be performed by applying a (Controlled) formula_16 gate operation. The matrix representation of such two-qubits operator is given by
formula_17
The action of a formula_16 gate over two qubits can be described by the following system:
formula_19
When applying a formula_16 gate over two ancillae in the formula_21 state, the overall state 
formula_22
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 formula_16 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 formula_16 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 formula_25 with two possible eigenvectors, say formula_26 and formula_27, and suppose to deal with a multi-particle quantum system formula_28. Measuring the formula_29-th qubit by the formula_25 observable means to project the formula_28 state over the eigenvectors of formula_25:
formula_33.
The actual state of the formula_29-th qubit is now formula_35, which can turn to be formula_36 or formula_37, depending on the outcome from the measurement (which is probabilistic in quantum mechanics). The measurement projection can be performed over the eigenstates of the formula_38 observable:
formula_39,
where formula_40 and formula_41 belong to the Pauli matrices. The eigenvectors of formula_42 are formula_43. Measuring a qubit on the formula_40-formula_41 plane, i.e. by the formula_42 observable, means to project it over formula_47 or formula_48. 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 formula_49 notation, it is common to find formula_50 to indicate a projective measurement over the formula_29-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 formula_40-formula_41 plane, the output may change whether the outcome had been formula_54 or formula_55. 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. The byproduct operators which can be implemented are formula_40 and formula_57. Depending on the outcome of the measurement, a byproduct operator can be applied or not to the output state: a formula_40 correction over the formula_59-th qubit, depending on the outcome of the measurement performed over the formula_29-th qubit via the formula_42 observable, can be described as formula_62, where formula_63 is set to be formula_11 if the outcome of measurement was formula_65, otherwise is formula_12 if it was formula_67. In the first case, no correction will occur, in the latter one a formula_40 operator will be implemented on the formula_59-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. In the "CME" formalism, the operation of entanglement between the formula_29 and formula_59 qubits is referred to as formula_72. The measurement on the formula_29 qubit, in the formula_40-formula_41 plane, with respect to a formula_76 angle, is defined as formula_77. At last, the formula_40 byproduct over a formula_29 qubit, with respect to the measurement over a formula_59 qubit, is described as formula_81, where formula_82 is set to formula_11 if the outcome is the formula_65 state, formula_12 when the outcome is formula_67. The same notation holds for the formula_57 byproducts.
When performing a computation following the "CME" pattern, it may happen that two measurements formula_88 and formula_89 on the formula_40-formula_41 plane depend one on the outcome from the other. For example, the sign in front of the angle of measurement on the formula_59-th qubit can be flipped with respect to the measurement over the formula_29-th qubit: in such case, the notation will be written as formula_94, and therefore the two operations of measurement do commute each other no more. If formula_63 is set to formula_11, no flip on the formula_97 sign will occur, otherwise (when formula_98) the formula_97 angle will be flipped to formula_100. The notation formula_101 can therefore be rewritten as formula_102.
An example: Euler rotations.
As an illustrative example, consider the Euler rotation in the formula_103 basis: such operation, in the gate model of quantum computation, is described as
formula_104,
where formula_105 are the angles for the rotation, while formula_106 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:
formula_107,
where the input state formula_108 is the qubit formula_12, all the other qubits are auxiliary ancillae and therefore have to be prepared in the formula_110 state. In the first step, the input state formula_111 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 formula_72 between the qubits can be performed by the formula_16 gates.
In the second place, the first and the second qubits must be measured by the formula_42 observable, which means they must be projected onto the eigenstates formula_115 of such observable. When the formula_76 is zero, the formula_117 states reduce to formula_118 ones, i.e. the eigenvectors for the formula_40 Pauli operator. The first measurement formula_120 is performed on the qubit formula_12 with a formula_122 angle, which means it has to be projected onto the formula_123 states. The second measurement formula_124 is performed with respect to the formula_125 angle, i.e. the second qubit has to be projected on the formula_126 state. However, if the outcome from the previous measurement has been formula_127, the sign of the formula_128 angle has to be flipped, and the second qubit will be projected to the formula_129 state; if the outcome from the first measurement has been formula_130, no flip needs to be performed. The same operations have to be repeated for the third formula_131 and the fourth formula_132 measurements, according to the respective angles and sign flips. The sign over the formula_133 angle is set to be formula_134. Eventually the fifth qubit (the only one not to be measured) figures out to be the output state.
At last, the corrections formula_135 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 formula_136 and formula_137, no correction will be conducted by the formula_138 operator, as formula_139. The same result holds for a formula_140 formula_141 outcome, as formula_142 and thus the squared Pauli operator formula_143 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 formula_16 and the formula_145 operators: therefore, any circuit can be decomposed into a set of formula_16 and the formula_145 gates. The formula_145 single-qubit operator is defined as follows:
formula_149.
The formula_145 can be converted into a "CME" pattern as follows, with qubit 1 being the input and qubit 2 being the output:
formula_151
which means, to implement a formula_145 operator, the input qubits formula_153 must be entangled with an ancilla qubit formula_110, therefore the input must be measured on the formula_40-formula_41 plane, thereafter the output qubit is corrected by the formula_157 byproduct. Once every formula_145 gate has been decomposed into the "CME" pattern, the operations in the overall computation will consist of formula_72 entanglements, formula_160 measurements and formula_161 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 formula_72 entanglements