The one-way or measurement-based quantum computer (MBQC) is a method of
quantum computing
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thou ...
that first prepares an
entangled ''resource state'', usually a
cluster state
In quantum information and quantum computing, a cluster state is a type of highly entangled state of multiple qubits. Cluster states are generated in lattices of qubits with Ising type interactions. A cluster ''C'' is a connected subset of a '' ...
or
graph state
In quantum computing, a graph state is a special type of multi-qubit state that can be represented by a graph. Each qubit is represented by a vertex of the graph, and there is an edge between every interacting pair of qubits. In particular, they a ...
, then performs single
qubit
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
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
Basis may refer to:
Finance and accounting
*Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting o ...
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 hardware implementation of MBQC mainly relies on
photonic devices, thanks to the properties of entanglement between the
photons. The process of entanglement and measurement can be described with the help of
graph tools and
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, 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
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, q ...
: instead of encoding a binary unit of information (
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented a ...
), 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
of input qubits with a cluster of
ancillary qubits, forming an overall source state of
qubits, and then measuring a number
of them.
The remaining
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 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 state:
:
where and are the quantum encoding for the classical and bits:
:.
A register with qubits will be therefore set as . Thereafter, the entanglement between two qubits can be performed by applying a gate operation. The matrix representation of such two-qubits operator is given by
:
The action of a gate over two qubits can be described by the following system:
:
When applying a gate over two ancillae in the state, the overall state
:
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 gates are represented in a diagonal form, they all commute each other, and no importance is given about which qubits to entangle first. Photons are the most common source to prepare entangled physical qubits.
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 with two possible eigenvectors, say and , and suppose to deal with a multi-particle quantum system . Measuring the -th qubit by the observable means to project the state over the eigenvectors of :[
:.
The actual state of the -th qubit is now , which can turn to be or , depending on the outcome from the measurement (which is probabilistic in quantum mechanics). The measurement projection can be performed over the eigenstates of the observable:
:,
where and belong to the ]Pauli matrices
In mathematical physics and mathematics, the Pauli matrices are a set of three complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma (), they are occasionally denoted by tau () when use ...
. The eigenvectors of are . Measuring a qubit on the - plane, i.e. by the observable, means to project it over or . 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 notation, it is common to find to indicate a projective measurement over the -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 - plane, the output may change whether the outcome had been or . 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 and . Depending on the outcome of the measurement, a byproduct operator can be applied or not to the output state: a correction over the -th qubit, depending on the outcome of the measurement performed over the -th qubit via the observable, can be described as , where is set to be if the outcome of measurement was , otherwise is if it was . In the first case, no correction will occur, in the latter one a operator will be implemented on the -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 and qubits is referred to as . The measurement on the qubit, in the - plane, with respect to a angle, is defined as . At last, the byproduct over a qubit, with respect to the measurement over a qubit, is described as , where is set to if the outcome is the state, when the outcome is . The same notation holds for the byproducts.
When performing a computation following the ''CME'' pattern, it may happen that two measurements and on the - plane depend one on the outcome from the other. For example, the sign in front of the angle of measurement on the -th qubit can be flipped with respect to the measurement over the -th qubit: in such case, the notation will be written as , and therefore the two operations of measurement do commute each other no more. If is set to , no flip on the sign will occur, otherwise (when ) the angle will be flipped to . The notation can therefore be rewritten as .
]
An example: Euler rotations
As an illustrative example, consider the Euler rotation in the basis: such operation, in the gate model of quantum computation, is described as
:,
where are the angles for the rotation, while 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:[
:]_2^
Caret is the name used familiarly for the character , provided on most QWERTY keyboards by typing . The symbol has a variety of uses in programming and mathematics. The name "caret" arose from its visual similarity to the original proofread ...
M_1^ E_ E_ E_ E_,
where the input state is the qubit , all the other qubits are auxiliary ancillae and therefore have to be prepared in the state. In the first step, the input state 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 between the qubits can be performed by the gates.
In the second place, the first and the second qubits must be measured by the observable, which means they must be projected onto the eigenstates of such observable. When the is zero, the states reduce to ones, i.e. the eigenvectors for the Pauli operator. The first measurement is performed on the qubit with a angle, which means it has to be projected onto the states. The second measurement _2^
Caret is the name used familiarly for the character , provided on most QWERTY keyboards by typing . The symbol has a variety of uses in programming and mathematics. The name "caret" arose from its visual similarity to the original proofread ...
is performed with respect to the angle, i.e. the second qubit has to be projected on the state. However, if the outcome from the previous measurement has been , the sign of the angle has to be flipped, and the second qubit will be projected to the state; if the outcome from the first measurement has been , no flip needs to be performed. The same operations have to be repeated for the third and the fourth measurements, according to the respective angles and sign flips. The sign over the angle is set to be . Eventually the fifth qubit (the only one not to be measured) figures out to be the output state.
At last, the corrections 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 and , no correction will be conducted by the operator, as . The same result holds for a outcome, as and thus the squared Pauli operator 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 and the operators: therefore, any circuit can be decomposed into a set of and the gates. The single-qubit operator is defined as follows:
:.
The can be converted into a ''CME'' pattern as follows:
:
which means, to implement a operator, the input qubits must be entangled with an ancilla qubit , therefore the input must be measured on the - plane, thereafter the output qubit is corrected by the byproduct. Once every gate has been decomposed into the ''CME'' pattern, the operations in the overall computation will consist of entanglements, measurements and 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 entanglements at the beginning of the process, some rules of commutation
Commute, commutation or commutative may refer to:
* Commuting, the process of travelling between a place of residence and a place of work
Mathematics
* Commutative property, a property of a mathematical operation whose result is insensitive to th ...
must be pointed out:
:
:
:.
The entanglement operator commutes with the Pauli operators and with any other operator acting on a qubit , but not with the Pauli operators acting on the -th or -th qubits.
Pauli simplification
The measurement operations commute with the corrections in the following manner:
:
:,
where . Such operation means that, when shifting the corrections at the end of the pattern, some dependencies between the measurements may occur. The operator is called signal shifting, whose action will be explained in the next paragraph. For particular angles, some simplifications, called Pauli simplifications, can be introduced:
:
:.
Signal shifting
The action of the signal shifting operator can be explained through its rules of commutation:
:
:.
The
Stabilizer formalism
When preparing the source state of entangled qubits, a graph representation can be given by the stabilizer group. The stabilizer group \mathcal_n is an abelian
Abelian may refer to:
Mathematics Group theory
* Abelian group, a group in which the binary operation is commutative
** Category of abelian groups (Ab), has abelian groups as objects and group homomorphisms as morphisms
* Metabelian group, a grou ...
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgrou ...
from the Pauli group
In physics and mathematics, the Pauli group G_1 on 1 qubit is the 16-element matrix group consisting of the 2 × 2 identity matrix I and all of the Pauli matrices
:X = \sigma_1 =
\begin
0&1\\
1&0
\end,\quad
Y = \sigma_2 =
\beg ...
\mathcal_n, which one can be described by its generators \ \times \^. A stabilizer state is a n-qubit state , \Psi \rangle which is a unique eigenstate for the generators S_i of the \mathcal_n stabilizer group:[
:S_i , \Psi \rangle = , \Psi \rangle.
Of course, S_i \in \mathcal_n \, \forall i.
]
It is therefore possible to define a n qubit graph state , G \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
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
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). In the stabilizer formalism, such graph structure can be encoded by the K_i generators of \mathcal_n, defined as[
: K_i = X_i \prod_ Z_j ,
where 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_n is composed by elements which leave invariant the elements from the Pauli's group \mathcal_n:[
:\mathcal_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 \begin 1 & 1 \\ 1 & -1 \end, \quad S = \begin 1 & 0 \\ 0 & i \end, \quad CNOT = \begin 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end .
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 In quantum computing, the Gottesman–Knill theorem is a theoretical result by Daniel Gottesman and Emanuel Knill that states that stabilizer circuits, circuits that only consist of gates from the normalizer of the qubit Pauli group, also called ...
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 The toric code is a topological quantum error correcting code, and an example of a stabilizer code, defined on a two-dimensional spin lattice. It is the simplest and most well studied of the quantum double models. It is also the simplest example o ...
, 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
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output ...
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 lattice
An optical lattice is formed by the interference of counter-propagating laser beams, creating a spatially periodic polarization pattern. The resulting periodic potential may trap neutral atoms via the Stark shift. Atoms are cooled and congreg ...
s, 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
Spin or spinning most often refers to:
* Spinning (textiles), the creation of yarn or thread by twisting fibers together, traditionally by hand spinning
* Spin, the rotation of an object around a central axis
* Spin (propaganda), an intentionally b ...
\tfrac) AKLT
The AKLT model is an extension of the one-dimensional quantum Heisenberg spin model. The proposal and exact solution of this model by Ian Affleck, Elliott H. Lieb, Tom Kennedy and provided crucial insight into the physics of the spin-1 Heisen ...
state on a 2D honeycomb lattice
The hexagonal lattice or triangular lattice is one of the five two-dimensional Bravais lattice types. The symmetry category of the lattice is wallpaper group p6m. The primitive translation vectors of the hexagonal lattice form an angle of 120° ...
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
* Quantum gate teleportation
Quantum gate teleportation is a quantum circuit construction where a gate is applied to target qubits by first applying the gate to an entangled state and then teleporting the target qubits through that entangled state.
This separation of the ...
* Continuous-variable quantum information Continuous-variable (CV) quantum information is the area of quantum information science that makes use of physical observables, like the strength of an electromagnetic field, whose numerical values belong to continuous intervals. One primary appl ...
* Quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite seq ...
* Quantum logic gate
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, li ...
* Linear optical quantum computing
Linear optical quantum computing or linear optics quantum computation (LOQC) is a paradigm of quantum computation, allowing (under certain conditions, described below) universal quantum computation. LOQC uses photons as information carriers, main ...
* Quantum optics
Quantum optics is a branch of atomic, molecular, and optical physics dealing with how individual quanta of light, known as photons, interact with atoms and molecules. It includes the study of the particle-like properties of photons. Photons have ...
* Quantum error correction
Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is theorised as essential to achieve fault tolerant quantum computing tha ...
* Quantum Turing machine
A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorith ...
* Adiabatic quantum computation
Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to do calculations and is closely related to quantum annealing.
Description
First, a (potentially complicated) Hamiltonian is found whose ...
References
;General
* Non-cluster resource states
* Measurement-based quantum computation, quantum carry-lookahead adder
{{Quantum computing
Quantum information science
Information theory
Models of computation