The Measurement Calculus
Vincent Danos
Université Paris 7 & CNRS
vincent.danos@pps.jussieu.fr
Elham Kashefi
IQC - University of Waterloo
Christ Church - Oxford
elham.kashefi@comlab.ox.ac.uk
Prakash Panangaden
McGill University
prakash@cs.mcgill.ca
Abstract
Measurement-based quantum computation has emerged from the physics community as a
new approach to quantum computation where the notion of measurement is the main driving
force of computation. This is in contrast with the more traditional circuit model which is based
on unitary operations. Among measurement-based quantum computation methods, the recently
introduced one-way quantum computer [RB01] stands out as fundamental.
We develop a rigorous mathematical model underlying the one-way quantum computer and
present a concrete syntax and operational semantics for programs, which we call patterns, and an
algebra of these patterns derived from a denotational semantics. More importantly, we present
a calculus for reasoning locally and compositionally about these patterns. We present a rewrite
theory and prove a general standardization theorem which allows all patterns to be put in a
semantically equivalent standard form. Standardization has far-reaching consequences: a new
physical architecture based on performing all the entanglement in the beginning, parallelization
by exposing the dependency structure of measurements and expressiveness theorems.
Furthermore we formalize several other measurement-based models e.g.Teleportation, Phase
and Pauli models and present compositional embeddings of them into and from the one-way
model. This allows us to transfer all the theory we develop for the one-way model to these mod-
els. This shows that the framework we have developed has a general impact on measurement-
based computation and is not just particular to the one-way quantum computer.
1 Introduction
The emergence of quantum computation has changed our perspective on many fundamental aspects
of computing: the nature of information and how it flows, new algorithmic design strategies and
complexity classes and the very structure of computational models [NC00]. New challenges have
been raised in the physical implementation of quantum computers. This paper is a contribution to
a nascent discipline: quantum programming languages.
This is more than a search for convenient notation, it is an investigation into the structure,
scope and limits of quantum computation. The main issues are questions about how quantum
processes are defined, how quantum algorithms compose, how quantum resources are used and how
classical and quantum information interact.
Quantum computation emerged in the early 1980s with Feynman’s observations about the dif-
ficulty of simulating quantum systems on a classical computer. This hinted at the possibility of
turning around the issue and exploiting the power of quantum systems to perform computational
tasks more efficiently than was classically possible. In the mid 1980s Deutsch [Deu87] and later
http://arxiv.org/abs/0704.1263v1
Deutsch and Jozsa [DJ92] showed how to use superposition – the ability to produce linear combi-
nations of quantum states – to obtain computational speedup. This led to interest in algorithm
design and the complexity aspects of quantum computation by computer scientists. The most
dramatic results were Shor’s celebrated polytime factorization algorithm [Sho94] and Grover’s sub-
linear search algorithm [Gro98]. Remarkably one of the problematic aspects of quantum theory,
the presence of non-local correlation – an example of which is called “entanglement” – turned out
to be crucial for these algorithmic developments.
If efficient factorization is indeed possible in practice, then much of cryptography becomes
insecure as it is based on the difficulty of factorization. However, entanglement makes it possible
to design unconditionally secure key distribution [BB84, Eke91]. Furthermore, entanglement led
to the remarkable – but simple – protocol for transferring quantum states using only classical
communication [BBC+93]; this is the famous so-called “teleportation” protocol. There continues to
be tremendous activity in quantum cryptography, algorithmic design, complexity and information
theory. Parallel to all this work there has been intense interest from the physics community to
explore possible implementations, see, for example, [NC00] for a textbook account of some of these
ideas.
On the other hand, only recently has there been significant interest in quantum programming
languages; i.e. the development of formal syntax and semantics and the use of standard machinery
for reasoning about quantum information processing. The first quantum programming languages
were variations on imperative probabilistic languages and emphasized logic and program develop-
ment based on weakest preconditions [SZ00, Ö01]. The first definitive treatment of a quantum
programming language was the flowchart language of Selinger [Sel04b]. It was based on combining
classical control, as traditionally seen in flowcharts, with quantum data. It also gave a denotational
semantics based on completely positive linear maps. The notion of quantum weakest preconditions
was developed in [DP06]. Later people proposed languages based on quantum control [AG05]. The
search for a sensible notion of higher-type computation [SV05, vT04] continues, but is problem-
atic [Sel04c].
A related recent development is the work of Abramsky and Coecke [AC04, Coe04] where they
develop a categorical axiomatization of quantum mechanics. This can be used to verify the correct-
ness of quantum communication protocols. It is very interesting from a foundational point of view
and allows one to explore exactly what mathematical ingredients are required to carry out certain
quantum protocols. This has also led to work on a categorical quantum logic [AD04].
The study of quantum communication protocols has led to formalizations based on process
algebras [GN05, JL04] and to proposals to use model checking for verifying quantum protocols. A
survey and a complete list of references on this subject up to 2005 is available [Gay05].
These ideas have proven to be of great utility in the world of classical computation. The use of
logics, type systems, operational semantics, denotational semantics and semantic-based inference
mechanisms have led to notable advances such as: the use of model checking for verification,
reasoning compositionally about security protocols, refinement-based programming methodology
and flow analysis.
The present paper applies this paradigm to a very recent development: measurement-based
quantum computation. None of the cited research on quantum programming languages is aimed
at measurement-based computation. On the other hand, the work in the physics literature does
not clearly separate the conceptual layers of the subject from implementation issues. A formal
treatment is necessary to analyze the foundations of measurement-based computation.
So far the main framework to explore quantum computation has been the circuit model [Deu89],
based on unitary evolution. This is very useful for algorithmic development and complexity analysis
[BV97]. There are other models such as quantum Turing machines [Deu85] and quantum cellular
automata [Wat95, vD96, DS96, SW04]. Although they are all proved to be equivalent from the
point of view of expressive power, there is no agreement on what is the canonical model for exposing
the key aspects of quantum computation.
Recently physicists have introduced novel ideas based on the use of measurement and entangle-
ment to perform computation [GC99, RB01, RBB03, Nie03]. This is very different from the circuit
model where measurement is done only at the end to extract classical output. In measurement-based
computation the main operation to manipulate information and control computation is measure-
ment. This is surprising because measurement creates indeterminacy, yet it is used to express
deterministic computation defined by a unitary evolution.
The idea of computing based on measurements emerged from the teleportation protocol [BBC+93].
The goal of this protocol is for an agent to transmit an unknown qubit to a remote agent without
actually sending the qubit. This protocol works by having the two parties share a maximally en-
tangled state called a Bell pair. The parties perform local operations – measurements and unitaries
– and communicate only classical bits. Remarkably, from this classical information the second
party can reconstruct the unknown quantum state. In fact one can actually use this to com-
pute via teleportation by choosing an appropriate measurement [GC99]. This is the key idea of
measurement-based computation.
It turns out that the above method of computing is actually universal. This was first shown
by Gottesman and Chuang [GC99] who used two-qubit measurements and given Bell pairs. Later
Nielsen [Nie03] showed that one could do this with only 4-qubit measurements with no prior Bell
pairs, however this works only probabilistically. Leung [Leu04] improved this to two qubits, but her
method also works only probabilistically. Later Perdrix and Jorrand [Per03, PJ04] gave the minimal
set measurements to perform universal quantum computing – but still in the probabilistic setting
– and introduced the state-transfer and measurement-based quantum Turing machine. Finally
the one-way computer was invented by Raussendorf and Briegel [RB01, RB02] which used only
single-qubit measurements with a particular multi-party entangled state, the cluster state.
More precisely, a computation consists of a phase in which a collection of qubits are set up in a
standard entangled state. Then measurements are applied to individual qubits and the outcomes of
the measurements may be used to determine further measurements. Finally – again depending on
measurement outcomes – local unitary operators, called corrections, are applied to some qubits; this
allows the elimination of the indeterminacy introduced by measurements. The phrase “one-way”
is used to emphasize that the computation is driven by irreversible measurements.
There are at least two reasons to take measurement-based models seriously: one conceptual
and one pragmatic. The main pragmatic reason is that the one-way model is believed by physicists
to lend itself to easier implementations [Nie04, CAJ05, BR05, TPKV04, TPKV06, WkJRR+05,
KPA06, BES05, CCWD06, BBFM06]. Physicists have investigated various properties of the cluster
state and have accrued evidence that the physical implementation is scalable and robust against
decoherence [Sch03, HEB04, DAB03, dNDM04b, dNDM04a, MP04, GHW05, HDB05, DHN06].
Conceptually the measurement-based model highlights the role of entanglement and separates the
quantum and classical aspects of computation; thus it clarifies, in particular, the interplay between
classical control and the quantum evolution process.
Our approach to understanding the structural features of measurement-based computation is to
develop a formal calculus. One can think of this as an “assembly language” for measurement-based
computation. Ours is the first programming framework specifically based on the one-way model. We
first develop a notation for such classically correlated sequences of entanglements, measurements,
and local corrections. Computations are organized in patterns1, and we give a careful treatment
of the composition and tensor product (parallel composition) of patterns. We show next that such
pattern combinations reflect the corresponding combinations of unitary operators. An easy proof
of universality follows.
So far, this is primarily a clarification of what was already known from the series of papers
introducing and investigating the properties of the one-way model [RB01, RB02, RBB03]. However,
we work here with an extended notion of pattern, where inputs and outputs may overlap in any
way one wants them to, and this results in more efficient – in the sense of using fewer qubits –
implementations of unitaries. Specifically, our universal set consists of patterns using only 2 qubits.
From it we obtain a 3 qubit realization of the Rz rotations and a 14 qubit realization for the
controlled-U family: a significant reduction over the hitherto known implementations.
The main point of this paper is to introduce a calculus of local equations over patterns that
exploits some special algebraic properties of the entanglement, measurement and correction op-
erators. More precisely, we use the fact that that 1-qubit XY measurements are closed under
conjugation by Pauli operators and the entanglement command belongs to the normalizer of the
Pauli group; these terms are explained in the appendix. We show that this calculus is sound in that
it preserves the interpretation of patterns. Most importantly, we derive from it a simple algorithm
by which any general pattern can be put into a standard form where entanglement is done first,
then measurements, then corrections. We call this standardization.
The consequences of the existence of such a procedure are far-reaching. Since entangling comes
first, one can prepare the entire entangled state needed during the computation right at the start:
one never has to do “on the fly” entanglements. Furthermore, the rewriting of a pattern to stan-
dard form reveals parallelism in the pattern computation. In a general pattern, one is forced to
compute sequentially and to strictly obey the command sequence, whereas, after standardization,
the dependency structure is relaxed, resulting in lower computational depth complexity. Last, the
existence of a standard form for any pattern also has interesting corollaries beyond implementation
and complexity matters, as it follows from it that patterns using no dependencies, or using only the
restricted class of Pauli measurements, can only realize a unitary belonging to the Clifford group,
and hence can be efficiently simulated by a classical computer [Got97].
As we have noted before, there are other methods for measurement-based quantum comput-
ing: the teleportation technique based on two-qubit measurements and the state-transfer approach
based on single qubit measurements and incomplete two-qubit measurements. We will analyze the
teleportation model and its relation to the one-way model. We will show how our calculus can be
smoothly extended to cover this case as well as new models that we introduce in this paper. We
get several benefits from our treatment. We get a workable syntax for handling the dependencies of
operators on previous measurement outcomes just by mimicking the one obtained in the one-way
model. This has never been done before for the teleportation model. Furthermore, we can use this
embedding to obtain a standardization procedure for the models. Finally these extended calculi
can be compositionally embedded back in the original one-way model. This clarifies the relation
between different measurement-based models and shows that the one-way model of Raussendorf
1We use the word “pattern” rather than “program”, because this corresponds to the commonly used terminology
in the physics literature.
and Briegel is the canonical one.
This paper develops the one-way model ab initio but certain concepts that the reader may be
unfamiliar with: qubits, unitaries, measurements, Pauli operators and the Clifford group are in
an appendix. These are also readily accessible through the very thorough book of Nielsen and
Chuang [NC00].
In the next section we define the basic model, followed by its operational and denotational
semantics, for completeness a simple proof of universality is given in section 4, this has appeared
earlier in the physics literature [DKP05], in section 5 we develop the rewrite theory and prove the
fundamental standardization theorem. In section 6 we develop several examples that illustrate the
use of our calculus in designing efficient patterns. In section 7 we prove some theorems about the
expressive power of the calculus in the absence of adaptive measurements. In section 8 we discuss
other measurement-based models and their compositional embedding to and from the one-way
model. In section 9 we discuss further directions and some more related work. In the appendix we
review basic notions of quantum mechanics and quantum computation.
2 Measurement Patterns
We first develop a notation for 1-qubit measurement based computations. The basic commands
one can use in a pattern are:
• 1-qubit auxiliary preparation Ni
• 2-qubit entanglement operators Eij
• 1-qubit measurements Mαi
• and 1-qubit Pauli operators corrections Xi and Zi
The indices i, j represent the qubits on which each of these operations apply, and α is a
parameter in [0, 2π]. Expressions involving angles are always evaluated modulo 2π. These types of
command will be referred to as N , E, M and C. Sequences of such commands, together with two
distinguished – possibly overlapping – sets of qubits corresponding to inputs and outputs, will be
called measurement patterns, or simply patterns. These patterns can be combined by composition
and tensor product.
Importantly, corrections and measurements are allowed to depend on previous measurement
outcomes. We shall prove later that patterns without these classical dependencies can only realize
unitaries that are in the Clifford group. Thus, dependencies are crucial if one wants to define a
universal computing model; that is to say, a model where all unitaries over ⊗nC2 can be realized.
It is also crucial to develop a notation that will handle these dependencies. This is what we do
2.1 Commands
Preparation Ni prepares qubit i in state |+〉i. The entanglement commands are defined as Eij :=
∧Zij (controlled-Z), while the correction commands are the Pauli operators Xi and Zi.
Measurement Mαi is defined by orthogonal projections on
|+α〉 := 1√
(|0〉+ eiα|1〉)
|−α〉 := 1√
(|0〉 − eiα|1〉)
followed by a trace-out operator. The parameter α ∈ [0, 2π] is called the angle of the mea-
surement. For α = 0, α = π
, one obtains the X and Y Pauli measurements. Operationally,
measurements will be understood as destructive measurements, consuming their qubit. The out-
come of a measurement done at qubit i will be denoted by si ∈ Z2. Since one only deals here with
patterns where qubits are measured at most once (see condition (D1) below), this is unambiguous.
We take the specific convention that si = 0 if under the corresponding measurement the state
collapses to |+α〉, and si = 1 if to |−α〉.
Outcomes can be summed together resulting in expressions of the form s =
i∈I si which we
call signals, and where the summation is understood as being done in Z2. We define the domain
of a signal as the set of qubits on which it depends.
As we have said before, both corrections and measurements may depend on signals. Depen-
dent corrections will be written Xsi and Z
i and dependent measurements will be written
t[Mαi ]
where s, t ∈ Z2 and α ∈ [0, 2π]. The meaning of dependencies for corrections is straightforward:
X0i = Z
i = I, no correction is applied, while X
i = Xi and Z
i = Zi. In the case of dependent
measurements, the measurement angle will depend on s, t and α as follows:
t[Mαi ]
s := M
(−1)sα+tπ
i (1)
so that, depending on the parities of s and t, one may have to modify the α to one of −α, α + π
and −α+ π. These modifications correspond to conjugations of measurements under X and Z:
i Xi = M
i (2)
i Zi = M
i (3)
accordingly, we will refer to them as the X and Z-actions. Note that these two actions commute,
since −α+ π = −α− π up to 2π, and hence the order in which one applies them does not matter.
As we will see later, relations (2) and (3) are key to the propagation of dependent corrections,
and to obtaining patterns in the standard entanglement, measurement and correction form. Since
the measurements considered here are destructive, the above equations actually simplify to
Mαi Xi = M
i (4)
Mαi Zi = M
i (5)
Another point worth noticing is that the domain of the signals of a dependent command, be it a
measurement or a correction, represents the set of measurements which one has to do before one
can determine the actual value of the command.
We have completed our catalog of basic commands, including dependent ones, and we turn
now to the definition of measurement patterns. For convenient reference, the language syntax is
summarized in Figure 1.
2.2 Patterns
Definition 1 Patterns consists of three finite sets V , I, O, together with two injective maps ι :
I → V and o : O → V and a finite sequence of commands An . . . A1, read from right to left, applying
to qubits in V in that order, i.e. A1 first and An last, such that:
(D0) no command depends on an outcome not yet measured;
S := 0, 1, si, S + S Signals
A := Ni Preparations
Eij Entanglements
t[Mαi ]
s Measurements
Xsi , Z
i Corrections
Figure 1: 1-qubit based measurement language syntax
(D1) no command acts on a qubit already measured;
(D2) no command acts on a qubit not yet prepared, unless it is an input qubit;
(D3) a qubit i is measured if and only if i is not an output.
The set V is called the pattern computation space, and we write HV for the associated quantum
state space ⊗i∈V C2. To ease notation, we will omit the maps ι and o, and write simply I, O instead
of ι(I) and o(O). Note, however, that these maps are useful to define classical manipulations of
the quantum states, such as permutations of the qubits. The sets I, O are called respectively the
pattern inputs and outputs, and we write HI , and HO for the associated quantum state spaces. The
sequence An . . . A1 is called the pattern command sequence, while the triple (V, I,O) is called the
pattern type.
To run a pattern, one prepares the input qubits in some input state ψ ∈ HI , while the non-input
qubits are all set to the |+〉 state, then the commands are executed in sequence, and finally the result
of the pattern computation is read back from outputs as some φ ∈ HO. Clearly, for this procedure
to succeed, we had to impose the (D0), (D1), (D2) and (D3) conditions. Indeed if (D0) fails, then
at some point of the computation, one will want to execute a command which depends on outcomes
that are not known yet. Likewise, if (D1) fails, one will try to apply a command on a qubit that
has been consumed by a measurement (recall that we use destructive measurements). Similarly, if
(D2) fails, one will try to apply a command on a non-existent qubit. Condition (D3) is there to
make sure that the final state belongs to the output space HO, i.e., that all non-output qubits, and
only non-output qubits, will have been consumed by a measurement when the computation ends.
We write (D) for the conjunction of our definiteness conditions (D0), (D1), (D2) and (D3).
Whether a given pattern satisfies (D) or not is statically verifiable on the pattern command se-
quence. We could have imposed a simple type system to enforce these constraints but, in the
interests of notational simplicity, we chose not to do so.
Here is a concrete example:
H := ({1, 2}, {1}, {2},Xs12 M01E12N2)
with computation space {1, 2}, inputs {1}, and outputs {2}. To run H, one first prepares the first
qubit in some input state ψ, and the second qubit in state |+〉, then these are entangled to obtain
∧Z12(ψ1 ⊗ |+〉2). Once this is done, the first qubit is measured in the |+〉, |−〉 basis. Finally an X
correction is applied on the output qubit, if the measurement outcome was s1 = 1. We will do this
calculation in detail later, and prove that this pattern implements the Hadamard operator H.
In general, a given pattern may use auxiliary qubits that are neither input nor output qubits.
Usually one tries to use as few such qubits as possible, since these contribute to the space complexity
of the computation.
A last thing to note is that one does not require inputs and outputs to be disjoint subsets of
V . This, seemingly innocuous, additional flexibility is actually quite useful to give parsimonious
implementations of unitaries [DKP05]. While the restriction to disjoint inputs and outputs is
unnecessary, it has been discussed whether imposing it results in patterns that are easier to realize
physically. Recent work [HEB04, BR05, CAJ05] however, seems to indicate it is not the case.
2.3 Pattern combination
We are interested in how one can combine patterns in order to obtain bigger ones.
The first way to combine patterns is by composing them. Two patterns P1 and P2 may be
composed if V1 ∩ V2 = O1 = I2. Provided that P1 has as many outputs as P2 has inputs, by
renaming the pattern qubits, one can always make them composable.
Definition 2 The composite pattern P2P1 is defined as:
— V := V1 ∪ V2, I = I1, O = O2,
— commands are concatenated.
The other way of combining patterns is to tensor them. Two patterns P1 and P2 may be tensored
if V1 ∩ V2 = ∅. Again one can always meet this condition by renaming qubits in a way that these
sets are made disjoint.
Definition 3 The tensor pattern P1 ⊗ P2 is defined as:
— V = V1 ∪ V2, I = I1 ∪ I2, and O = O1 ∪O2,
— commands are concatenated.
In contrast to the composition case, all the unions involved here are disjoint. Therefore commands
from distinct patterns freely commute, since they apply to disjoint qubits, and when we say that
commands have to be concatenated, this is only for definiteness. It is routine to verify that the
definiteness conditions (D) are preserved under composition and tensor product.
Before turning to this matter, we need a clean definition of what it means for a pattern to
implement or to realize a unitary operator, together with a proof that the way one can combine
patterns is reflected in their interpretations. This is key to our proof of universality.
3 The semantics of patterns
In this section we give a formal operational semantics for the pattern language as a probabilistic
labeled transition system. We define deterministic patterns and thereafter concentrate on them.
We show that deterministic patterns compose. We give a denotational semantics of deterministic
patterns; from the construction it will be clear that these two semantics are equivalent.
Besides quantum states, which are non-zero vectors in some Hilbert space HV , one needs a
classical state recording the outcomes of the successive measurements one does in a pattern. If we
let V stand for the finite set of qubits that are still active (i.e. not yet measured) and W stands
for the set of qubits that have been measured (i.e. they are now just classical bits recording the
measurement outcomes), it is natural to define the computation state space as:
S := ΣV,WHV × ZW2 .
In other words the computation states form a V,W -indexed family of pairs2 q, Γ, where q is a
quantum state from HV and Γ is a map from some W to the outcome space Z2. We call this
classical component Γ an outcome map, and denote by ∅ the empty outcome map in Z∅2 . We will
treat these states as pairs unless it becomes important to show how V and W are altered during a
computation, as happens during a measurement.
3.1 Operational semantics
We need some preliminary notation. For any signal s and classical state Γ ∈ ZW2 , such that the
domain of s is included in W , we take sΓ to be the value of s given by the outcome map Γ. That is
to say, if s =
I si, then sΓ :=
I Γ(i) where the sum is taken in Z2. Also if Γ ∈ ZW2 , and x ∈ Z2,
we define:
Γ[x/i](i) = x, Γ[x/i](j) = Γ(j) for j 6= i
which is a map in Z
W∪{i}
We may now view each of our commands as acting on the state space S, we have suppressed V
and W in the first 4 commands:
Ni−→ q ⊗ |+〉i,Γ
Eij−→ ∧Zijq,Γ
i−→ XsΓi q,Γ
i−→ ZsΓi q,Γ
V ∪ {i},W, q,Γ
−→ V,W ∪ {i}, 〈+αΓ |iq,Γ[0/i]
V ∪ {i},W, q,Γ
−→ V,W ∪ {i}, 〈−αΓ |iq,Γ[1/i]
where αΓ = (−1)sΓα + tΓπ following equation (1). Note how the measurement moves an index
from V to W ; a qubit once measured cannot be neasured again. Suppose q ∈ HV , for the above
relations to be defined, one needs the indices i, j on which the various command apply to be in V .
One also needs Γ to contain the domains of s and t, so that sΓ and tΓ are well-defined. This will
always be the case during the run of a pattern because of condition (D).
All commands except measurements are deterministic and only modify the quantum part of
the state. The measurement actions on S are not deterministic, so that these are actually binary
relations on S, and modify both the quantum and classical parts of the state. The usual convention
has it that when one does a measurement the resulting state is renormalized and the probabilities
are associated with the transition. We do not adhere to this convention here, instead we leave the
states unnormalized. The reason for this choice of convention is that this way, the probability of
reaching a given state can be read off its norm, and the overall treatment is simpler. As we will
show later, all the patterns implementing unitary operators will have the same probability for all
the branches and hence we will not need to carry these probabilities explicitly.
2These are actually quadruples of the form (V,W, q,Γ), unless necessary we will suppress the V and the W .
We introduce an additional command called signal shifting :
i−→ q,Γ[Γ(i) + sΓ/i]
It consists in shifting the measurement outcome at i by the amount sΓ. Note that the Z-action leaves
measurements globally invariant, in the sense that |+α+π〉, |−α+π〉 = |−α〉, |+α〉. Thus changing α
to α+ π amounts to swapping the outcomes of the measurements, and one has:
t[Mαi ]
s = Sti
0[Mαi ]
s (6)
and signal shifting allows to dispose of the Z action of a measurement, resulting sometimes in
convenient optimizations of standard forms.
3.2 Denotational semantics
Let P be a pattern with computation space V , inputs I, outputs O and command sequence
An . . . A1. To execute a pattern, one starts with some input state q in HI , together with the
empty outcome map ∅. The input state q is then tensored with as many |+〉s as there are non-
inputs in V (the N commands), so as to obtain a state in the full space HV . Then E, M and
C commands in P are applied in sequence from right to left. We can summarize the situation as
follows:
// HO
HI × Z∅2
prep // HV × Z∅2
A1...An // HO × ZVrO2
If m is the number of measurements, which is also the number of non outputs, then the run may
follow 2m different branches. Each branch is associated with a unique binary string s of length m,
representing the classical outcomes of the measurements along that branch, and a unique branch
map As representing the linear transformation from HI to HO along that branch. This map is
obtained from the operational semantics via the sequence (qi,Γi) with 1 ≤ i ≤ n+ 1, such that:
q1,Γ1 = q ⊗ |+ . . .+〉,∅
qn+1 = q
′ 6= 0
and for all i ≤ n : qi,Γi
Ai−→ qi+1,Γi+1.
Definition 4 A pattern P realizes a map on density matrices ρ given by ρ 7→
s(ρ)As. We
write [[P]] for the map realized by P.
Proposition 5 Each pattern realizes a completely positive trace preserving map.
Proof. Later on we will show that every pattern can be put in a semantically equivalent form
where all the preparations and entanglements appear first, followed by a sequence of measurements
and finally local Pauli corrections. Hence branch maps decompose as As = CsΠsU , where Cs is a
unitary map over HO collecting all corrections on outputs, Πs is a projection from HV to HO rep-
resenting the particular measurements performed along the branch, and U is a unitary embedding
from HI to HV collecting the branch preparations, and entanglements. Note that U is the same on
all branches. Therefore,
sAs =
U †Π†sC
sCsΠsU
U †Π†sΠsU
= U †(
= U †U = I
where we have used the fact that Cs is unitary, Πs is a projection and U is independent of
the branches and is also unitary. Therefore the map T (ρ) :=
As(ρ)A
s is a trace-preserving
completely-positive map (cptp-map), explicitly given as a Kraus decomposition. ✷
Hence the denotational semantics of a pattern is a cptp-map. In our denotational semantics we
view the pattern as defining a map from the input qubits to the output qubits. We do not explicitly
represent the result of measuring the final qubits; these may be of interest in some cases. Techniques
for dealing with classical output explicitly are given by Selinger [Sel04b] and Unruh [Unr05].
Definition 6 A pattern is said to be deterministic if it realizes a cptp-map that sends pure states
to pure states. A pattern is said to be strongly deterministic when branch maps are equal.
This is equivalent to saying that for a deterministic pattern branch maps are proportional, that
is to say, for all q ∈ HI and all s1, s2 ∈ Zn2 , As1(q) and As2(q) differ only up to a scalar. For a
strongly deterministic pattern we have for all s1, s2 ∈ Zn2 , As1 = As2 .
Proposition 7 If a pattern is strongly deterministic, then it realizes a unitary embedding.
Proof. Define T to be the map realized by the pattern. We have T =
sAs. Since the pattern
in strongly deterministic all the branch maps are the same. Define A to be 2n/2As, then A must
be a unitary embedding, because A†A = I. ✷
3.3 Short examples
For the rest of paper we assume that all the non-input qubits are prepared in the state |+〉 and
hence for simplicity we omit the preparation commands NIc .
First we give a quick example of a deterministic pattern that has branches with different proba-
bilities. Its type is V = {1, 2}, I = O = {1}, and its command sequence is Mα2 . Therefore, starting
with input q, one gets two branches:
q ⊗ |+〉,∅
(1 + e−iα)q,∅[0/2]
(1− e−iα)q,∅[1/2]
Thus this pattern is indeed deterministic, and implements the identity up to a global phase, and
yet the two branches have respective probabilities (1 + cosα)/2 and (1 − cosα)/2, which are not
equal in general and hence this pattern is not strongly deterministic.
There is an interesting variation on this first example. The pattern of interest, call it T , has
the same type as above with command sequence X
2E12. Again, T is deterministic, but not
strongly deterministic: the branches have different probabilities, as in the preceding example. Now,
however, these probabilities may depend on the input. The associated transformation is a cptp-map,
T (ρ) := AρA† +BρB† with:
, B :=
One has A†A+B†B = I, so T is indeed a completely positive and trace-preserving linear map and
T (|ψ〉〈ψ|) = 〈ψ,ψ〉|0〉〈0| and clearly for no unitary U does one have T (ρ) := UρU †.
For our final example, we return to the pattern H, already defined above. Consider the pattern
with the same qubit space {1, 2}, and the same inputs and outputs I = {1}, O = {2}, as H, but
with a shorter command sequence namely M01E12. Starting with input q = (a|0〉 + b|1〉)|+〉, one
has two computation branches, branching at M01 :
(a|0〉+ b|1〉)|+〉,∅ E12−→ 1√
(a|00〉 + a|01〉+ b|10〉 − b|11〉),∅
((a+ b)|0〉 + (a− b)|1〉),∅[0/1]
((a− b)|0〉 + (a+ b)|1〉),∅[1/1]
and since ‖a+ b‖2 + ‖a− b‖2 = 2(‖a‖2 + ‖b‖2), both transitions happen with equal probabilities 1
Both branches end up with non proportional outputs, so the pattern is not deterministic. However,
if one applies the local correction X2 on either of the branches’ ends, both outputs will be made to
coincide. If we choose to let the correction apply to the second branch, we obtain the pattern H,
already defined. We have just proved H = UH, that is to say H realizes the Hadamard operator.
3.4 Compositionality of the Denotational Semantics
With our definitions in place, we will show that the denotational semantics is compositional.
Theorem 1 For two patterns P1 and P2 we have [[P1P2]] = [[P2]][[P1]] and [[P1⊗P2]] = [[P2]]⊗ [[P1]].
Proof. Recall that two patterns P1, P2 may be combined by composition provided P1 has as many
outputs as P2 has inputs. Suppose this is the case, and suppose further that P1 and P2 respectively
realize some cptp-maps T1 and T2. We need to show that the composite pattern P2P1 realizes T2T1.
Indeed, the two diagrams representing branches in P1 and P2:
// HO1 HI2
// HO2
HI1 × Z
p1// HV1 × Z
// HO1 × Z
V1rO1
HI2 × Z
p2// HV2 × Z
// HO2 × Z
V2rO2
can be pasted together, since O1 = I2, and HO1 = HI2 . But then, it is enough to notice 1) that
preparation steps p2 in P2 commute with all actions in P1 since they apply on disjoint sets of qubits,
and 2) that no action taken in P2 depends on the measurements outcomes in P1. It follows that
the pasted diagram describes the same branches as does the one associated to the composite P2P1.
A similar argument applies to the case of a tensor combination, and one has that P2 ⊗ P1
realizes T2 ⊗ T1. ✷
If one wanted to give a categorical treatment3 one can define a category where the objects are
finite sets representing the input and output qubits and the morphisms are the patterns. This is
clearly a monoidal category with our tensor operation as the monoidal structure. One can show that
the denotational semantics gives a monoidal functor into the category of superoperators or into any
suitably enriched strongly compact closed category [AC04] or dagger category [Sel05a]. It would be
very interesting to explore exactly what additional categorical structures are required to interpret
the measurement calculus presented below. Duncan Ross[Dun05] has skectched a polycategorical
presentation of our measurement calculus.
4 Universality
Define the two following patterns on V = {1, 2}:
J (α) := Xs12 M
1 E12 (7)
∧Z := E12 (8)
with I = {1}, O = {2} in the first pattern, and I = O = {1, 2} in the second. Note that the second
pattern does have overlapping inputs and outputs.
Proposition 8 The patterns J (α) and ∧Z are universal.
Proof. First, we claim J (α) and ∧Z respectively realize J(α) and ∧Z, with:
J(α) := 1√
1 eiα
1 −eiα
We have already seen in our example that J (0) = H implements H = J(0), thus we already know
this in the particular case where α = 0. The general case follows by the same kind of computation.4
The case of ∧Z is obvious.
Second, we know that these unitaries form a universal set for ⊗nC2 [DKP05]. Therefore, from
the preceding section, we infer that combining the corresponding patterns will generate patterns
realizing any unitary in ⊗nC2. ✷
These patterns are indeed among the simplest possible. As a consequence, in the section devoted
to examples, we will find that our implementations often have lower space complexity than the
traditional implementations.
Remarkably, in our set of generators, one finds a single measurement and a single dependency,
which occurs in the correction phase of J (α). Clearly one needs at least one measurement, since
patterns without measurements can only implement unitaries in the Clifford group. It is also true
that dependencies are needed for universality, but we have to wait for the development of the
measurement calculus in the next section to give a proof of this fact.
3The rest of the paragraph can be omitted without loss of continuity.
4Equivalently, this follows from J(α) = HP (α), with P (α) =
0 eiα
1 E12 = X
1P (α)1E12 = HP (α)1.
5 The measurement calculus
We turn to the next important matter of the paper, namely standardization. The idea is quite
simple. It is enough to provide local pattern-rewrite rules pushing Es to the beginning of the
pattern and Cs to the end. The crucial point is to justify using the equations as rewrite rules.
5.1 The equations
The expressions appearing as commands are all linear operators on Hilbert space. At first glance,
the appropriate equality between commands is equality as operators. For the deterministic com-
mands, the equality that we consider is indeed equality as operators. This equality implies equality
in the denotational semantics. However, for measurement commands one needs a stricter definition
for equality in order to be able to apply them as rewriting rules. Essentially we have to take into
the account the effect of different branches that might result from the measurement process. The
precise definition is below.
Definition 9 Consider two patterns P and P ′ we define P = P ′ if and only if for any branch s,
we have APs = A
s , where A
s and A
s are the branch map As defined in Section 3.2.
The first set of equations gives the means to propagate local Pauli corrections through the
entangling operator Eij.
i = X
jEij (9)
j = X
iEij (10)
i = Z
iEij (11)
j = Z
jEij (12)
These equations are easy to verify and are natural since Eij belongs to the Clifford group, and
therefore maps under conjugation the Pauli group to itself. Note that, despite the symmetry of the
Eij operator qua operator, we have to consider all the cases, since the rewrite system defined below
does not allow one to rewrite Eij to Eji. If we did allow this the reqrite process could loop forever.
A second set of equations allows one to push corrections through measurements acting on the
same qubit. Again there are two cases:
t[Mαi ]
sXri =
t[Mαi ]
s+r (13)
t[Mαi ]
sZri =
t+r[Mαi ]
s (14)
These equations follow easily from equations (4) and (5). They express the fact that the measure-
ments Mαi are closed under conjugation by the Pauli group, very much like equations (9),(10),(11)
and (12) express the fact that the Pauli group is closed under conjugation by the entanglements
Eij .
Define the following convenient abbreviations:
[Mαi ]
s := 0[Mαi ]
s, t[Mαi ] :=
t[Mαi ]
0, Mαi :=
0[Mαi ]
Mxi :=M
i , M
i :=M
Particular cases of the equations above are:
Mxi X
i = M
i = [M
s = s[M
i ] = M
The first equation, follows from the fact that −0 = 0, so the X action on Mxi is trivial; the second
equation, is because −π
is equal π
+ π modulo 2π, and therefore the X and Z actions coincide on
i . So we obtain the following:
t[Mxi ]
s = t[Mxi ] (15)
s = s+t[M
i ] (16)
which we will use later to prove that patterns with measurements of the form Mx and My may
only realize unitaries in the Clifford group.
5.2 The rewrite rules
We now define a set of rewrite rules, obtained by orienting the equations above5:
i ⇒ Xsi ZsjEij EX
j ⇒ XsjZsiEij EX
i ⇒ ZsiEij EZ
j ⇒ ZsjEij EZ
t[Mαi ]
sXri ⇒ t[Mαi ]s+r MX
t[Mαi ]
sZri ⇒ r+t[Mαi ]s MZ
to which we need to add the free commutation rules, obtained when commands operate on disjoint
sets of qubits:
EijA~k ⇒ A~kEij where A is not an entanglement
i ⇒ XsiA~k where A is not a correction
i ⇒ ZsiA~k where A is not a correction
where ~k represent the qubits acted upon by command A, and are supposed to be distinct from i
and j. Clearly these rules could be reversed since they hold as equations but we are orienting them
this way in order to obtain termination.
Condition (D) is easily seen to be preserved under rewriting.
Under rewriting, the computation space, inputs and outputs remain the same, and so do the
entanglement commands. Measurements might be modified, but there is still the same number
of them, and they still act on the same qubits. The only induced modifications concern local
corrections and dependencies. If there was no dependency at the start, none will be created in the
rewriting process.
In order to obtain rewrite rules, it was essential that the entangling command (∧Z) belongs
to the normalizer of the Pauli group. The point is that the Pauli operators are the correction
operators and they can be dependent, thus we can commute the entangling commands to the
beginning without inheriting any dependency. Therefore the entanglement resource can indeed be
prepared at the outset of the computation.
5Recall that patterns are executed from right to left.
5.3 Standardization
Write P ⇒ P ′, respectively P ⇒⋆ P ′, if both patterns have the same type, and one obtains the
command sequence of P ′ from the command sequence of P by applying one, respectively any
number, of the rewrite rules of the previous section. We say that P is standard if for no P ′, P ⇒ P ′
and the procedure of writing a pattern to standard form is called standardization6.
One of the most important results about the rewrite system is that it has the desirable properties
of determinacy (confluence) and termination (standardization). In other words, we will show that
for all P, there exists a unique standard P ′, such that P ⇒⋆ P ′. It is, of course, crucial that the
standardization process leaves the semantics of patterns invariant. This is the subject of the next
simple, but important, proposition,
Proposition 10 Whenever P ⇒⋆ P ′, [[P]] = [[P ′]].
Proof. It is enough to prove it when P ⇒ P ′. The first group of rewrites has been proved to be
sound in the preceding subsections, while the free commutation rules are obviously sound. ✷
We now begin the main proof of this section. First, we prove termination.
Theorem 2 (Termination) All rewriting sequences beginning with a pattern P terminate after
finitely many steps. For our rewrite system, this implies that for all P there exist finitely many P ′
such that P ⇒⋆ P ′ where the P ′ are standard.
Proof. Suppose P has command sequence An . . . A1; so the number of commands is n. Let
e ≤ n be the number of E commands in P. As we have noted earlier, this number is invariant
under ⇒. Moreover E commands in P can be ordered by increasing depth, read from right to left,
and this order, written <E, is also invariant, since EE commutations are forbidden explicitly in
the free commutation rules.
Define the following depth function d on E and C commands in P:
d(Ai) =
i if Ai = Ejk
n− i if Ai = Cj
Define further the following sequence of length e, dE(P)(i) is the depth of the E-command of rank
i according to <E. By construction this sequence is strictly increasing. Finally, we define the
measure m(P) := (dE(P), dC (P)) with:
dC(P) =
C∈P d(C)
We claim the measure we just defined decreases lexicographically under rewriting, in other words
P ⇒ P ′ implies m(P) > m(P ′), where < is the lexicographic ordering on Ne+1.
To clarify these definitions, consider the following example. Suppose P’s command sequence is
of the form EXZE, then e = 2, dE(P) = (1, 4), and m(P) = (1, 4, 3). For the command sequence
EEX we get that e = 2, dE(P) = (2, 3) and m(P) = (2, 3, 2). Now, if one considers the rewrite
EEX ⇒ EXZE, the measure of the left hand side is (2, 3, 2), while the measure of the right hand
side, as said, is (1, 4, 3), and indeed (2, 3, 2) > (1, 4, 3). Intuitively the reason is clear: the Cs are
being pushed to the left, thus decreasing the depths of Es, and concomitantly, the value of dE .
6We use the word “standardization” instead of the more usual “normalization” in order not to cause terminological
confusion with the physicists’ notion of normalization.
Let us now consider all cases starting with an EC rewrite. Suppose the E command under
rewrite has depth d and rank i in the order <E. Then all Es of smaller rank have same depth in
the right hand side, while E has now depth d − 1 and still rank i. So the right hand side has a
strictly smaller measure. Note that when C = X, because of the creation of a Z (see the example
above), the last element of m(P) may increase, and for the same reason all elements of index j > i
in dE(P) may increase. This is why we are working with a lexicographical ordering.
Suppose now one does an MC rewrite, then dC(P) strictly decreases, since one correction is
absorbed, while all E commands have equal or smaller depths. Again the measure strictly decreases.
Next, suppose one does an EA rewrite, and the E command under rewrite has depth d and rank
i. Then it has depth d− 1 in the right hand side, and all other E commands have invariant depths,
since we forbade the case when A is itself an E. It follows that the measure strictly decreases.
Finally, upon an AC rewrite, all E commands have invariant depth, except possibly one which
has smaller depth in the case A = E, and dC(P) decreases strictly because we forbade the case
where A = C. Again the claim follows.
So all rewrites decrease our ordinal measure, and therefore all sequences of rewrites are finite,
and since the system is finitely branching (there are no more than n possible single step rewrites
on a given sequence of length n), we get the statement of the theorem.
The final statement of the theorem follows from the fact that we have finitely many rules so the
system is finitely branching. In any finitely branching rewrite system with the property that every
rewrite sequence terminates, it is clearly true that there can be only finitely many standard forms.
The next theorem establishes the important determinacy property and furthermore shows that
the standard patterns have a certain canonical form which we call the NEMC form. The precise
definition is:
Definition 11 A pattern has a NEMC form if its commands occur in the order of Ns first, then
Es , then Ms, and finally Cs.
We will usually just say “EMC” form since we can assume that all the auxiliary qubits are prepared
in the |+〉 state we usually just elide these N commands.
Theorem 3 (Confluence) For all P, there exists a unique standard P ′, such that P ⇒⋆ P ′, and
P ′ is in EMC form.
Proof. Since the rewriting system is terminating, confluence follows from local confluence 7 by
Newman’s lemma, see, for example, [Bar84]. The uniqueness of the standard is form an immediate
consequence.
We look for critical pairs, that is occurrences of three successive commands where two rules can
be applied simultaneously. One finds that there are only five types of critical pairs, of these the
three involve the N command, these are of the form: NMC, NEC and NEM ; and the remaining
two are: EijMkCk with i, j and k all distinct, EijMkCl with k and l distinct. In all cases local
confluence is easily verified.
Suppose now P ′ does not satisfy the EMC form conditions. Then, either there is a pattern EA
with A not of type E, or there is a pattern AC with A not of type C. In the former case, E and
7This means that whenever two rewrite rules can be applied to a term t yielding t1 and t2, one can rewrite both
t1 and t2 to a common third term t3, possibly in many steps.
A must operate on overlapping qubits, else one may apply a free commutation rule, and A may
not be a C since in this case one may apply an EC rewrite. The only remaining case is when A
is of type M , overlapping E’s qubits, but this is what condition (D1) forbids, and since (D1) is
preserved under rewriting, this contradicts the assumption. The latter case is even simpler. ✷
We have shown that under rewriting any pattern can be put in EMC form, which is what we
wanted. We actually proved more, namely that the standard form obtained is unique. However,
one has to be a bit careful about the significance of this additional piece of information. Note first
that uniqueness is obtained because we dropped the CC and EE free commutations, thus having a
rigid notion of command sequence. One cannot put them back as rewrite rules, since they obviously
ruin termination and uniqueness of standard forms.
A reasonable thing to do, would be to take this set of equations as generating an equivalence
relation on command sequences, call it ≡, and hope to strengthen the results obtained so far, by
proving that all reachable standard forms are equivalent.
But this is too naive a strategy, since E12X1X2 ≡ E12X2X1, and:
2 ⇒⋆ Xs1Zs2Xt2Zt1E12
≡ Xs1Zt1Zs2Xt2E12
obtaining an expression which is not symmetric in 1 and 2. To conclude, one has to extend ≡
to include the additional equivalence Xs1Z
1 ≡ Zt1Xs1 , which fortunately is sound since these two
operators are equal up to a global phase. Thus, these are all equivalent in our semantics of patterns.
We summarize this discussion as follows.
Definition 12 We define an equivalence relation ≡ on patterns by taking all the rewrite rules as
equations and adding the equation Xs1Z
1 ≡ Zt1Xs1 and generating the smallest equivalence relation.
With this definition we can state the following proposition.
Proposition 13 All patterns that are equivalent by ≡ are equal in the denotational semantics.
This≡ relation preserves both the type (the (V, I,O) triple) and the underlying entanglement graph.
So clearly semantic equality does not entail equality up to ≡. In fact, by composing teleportation
patterns one obtains infinitely many patterns for the identity which are all different up to ≡. One
may wonder whether two patterns with same semantics, type and underlying entanglement graph
are necessarily equal up to ≡. This is not true either. One has J(α)J(0)J(β) = J(α + β) =
J(β)J(0)J(α) (where J(α) is defined in Section 4), and this readily gives a counter-example.
We can now formally describe a simple standardization algorithm.
Algorithm 1 Input: A pattern P on |V | = N qubits with command sequence AM · · ·A1.
Output: An equivalent pattern P ′ in NEMC form.
1. Commute all the preparation commands (new qubits) to the right side.
2. Commute all the correction commands to the left side using the EC and MC rewriting rules.
3. Commute all the entanglement commands to the right side after the preparation commands.
Note that since each qubit can be entangled with at most N − 1 other qubits, and can be
measured or corrected only once, we have O(N2) entanglement commands and O(N) measurement
commands. According to the definiteness condition, no command acts on a qubit not yet prepared,
hence the first step of the above algorithm is based on trivial commuting rules; the same is true
for the last step as no entanglement command can act on a qubit that has been measured. Both
steps can be done in O(N2). The real complexity of the algorithm comes from the second step
and the EX commuting rule. In the worst case scenario, commuting an X correction to the left
might create O(N2) other Z corrections, each of which has to be commuted to the left themselves.
Thus one can have at most O(N3) new corrections, each of which has to be commuted past O(N2)
measurement or entanglement commands. Therefore the second step, and hence the algorithm, has
a worst case complexity of O(N5).
We conclude this subsection by emphasizing the importance of the EMC form. Since the
entanglement can always be done first, we can always derive the entanglement resource needed for
the whole computation right at the beginning. After that only local operations will be performed.
This will separate the analysis of entanglement resource requirements from the classical control.
Furthermore, this makes it possible to extract the maximal parallelism for the execution of the
pattern since the necessary dependecies are explicitly expressed, see the example in section 6 for
further discussion. Finally, the EMC form provides us with tools to prove general theorems about
patterns, such as the fact that they always compute cptp-maps and the expressiveness theorems of
section 7.
5.4 Signal shifting
One can extend the calculus to include the signal shifting command Sti . This allows one to dispose
of dependencies induced by the Z-action, and obtain sometimes standard patterns with smaller
computational depth complexity, as we will see in the next section which is devoted to examples.
t[Mαi ]
s ⇒ Sti [Mαi ]s
i ⇒ StiX
s[t+si/si]
i ⇒ StiZ
s[t+si/si]
t[Mαj ]
sSri ⇒ Sri t[r+si/si][Mαj ]s[r+si/si]
Ssi S
j ⇒ StjS
s[t+sj/sj ]
where s[t/si] denotes the substitution of si with t in s, s, t being signals. Note that when we write
a t explicitly on the upper left of an M , we mean that t 6= 0. The first additional rewrite rule was
already introduced as equation (6), while the other ones merely propagate the signal shift. Clearly
one can dispose of Sti when it hits the end of the pattern command sequence. We will refer to this
new set of rules as ⇒S. Note that we always apply first the standardization rules and then signal
shifting, hence we do not need any commutation rule for E and S commands.
It is important to note that both theorem 2 and 3 still hold for this extended rewriting system.
In order to prove termination one can start with the EMC form and then adapt the proof of
Theorem 2 by defining a depth function for a signal shift similar to the depth of a correction
command. As with the correction, signal shifts can also be commuted to the left hand side of a
command sequence. Now our measure can be modified to account for the new signal shifting terms
and shown to be decreasing under each step of signal shifting. Confluence can be also proved from
local confluence using again Newman’s Lemma [Bar84]. One typical critical pair is t[Mαj ]S
i where
i appears in the domain of signal t and hence the signal shifting command Ssi will have an effect on
the measurement. Now there are two possible ways to rewrite this pair, first, commute the signal
shifting command and then replace the left signal of the measurement with its own signal shifting
command:
t[Mαj ] S
i ⇒ Ssi t+s[Mαj ]
⇒ Ssi S
The other way is to first replace the left signal of the measurement and then commute the signal
shifting command:
t[Mαj ] S
i ⇒ StjMαj Ssi
⇒ Stj Ssi Mαj
Now one more step of rewriting on the last equation will give us the same result for both choices.
Stj S
j ⇒ Ssi S
All other critical terms can be dealt with similarly.
6 Examples
In this section we develop some examples illustrating pattern composition, pattern standardization,
and signal shifting. We compare our implementations with the implementations given in the refer-
ence paper [RBB03]. To combine patterns one needs to rename their qubits as we already noted.
We use the following concrete notation: if P is a pattern over {1, . . . , n}, and f is an injection,
we write P(f(1), . . . , f(n)) for the same pattern with qubits renamed according to f . We also
write P2 ◦ P1 for pattern composition, in order to make it more readable. Finally we define the
computational depth complexity to be the number of measurement rounds plus one final correction
round. More details on depth complexity, specially on the preparation depth, i.e. depth of the
entanglement commands, can be found in [BK06].
Teleportation.
Consider the composite pattern J (β)(2, 3)◦J (α)(1, 2) with computation space {1, 2, 3}, inputs {1},
and outputs {3}. We run our standardization procedure so as to obtain an equivalent standard
pattern:
J (β)(2, 3) ◦ J (α)(1, 2) = Xs23 M
2 E23X
1 E12
⇒EX Xs23 M
1 E23E12
⇒MX Xs23 Z
s1M−α1 E23E12
Let us call the pattern just obtained J (α, β). If we take as a special case α = β = 0, we get:
1E23E12
and since we know that J (0) implements H and H2 = I, we conclude that this pattern implements
the identity, or in other words it teleports qubit 1 to qubit 3. As it happens, this pattern obtained
by self-composition, is the same as the one given in the reference paper [RBB03, p.14].
x-rotation.
Here is the reference implementation of an x-rotation [RBB03, p.17], Rx(α):
Xs23 Z
s1Mx1E23E12
with type {1, 2, 3}, {1}, and {3}. There is a natural question which one might call the recognition
problem, namely how does one know this is implementing Rx(α) ? Of course there is the brute
force answer to that, which we applied to compute our simpler patterns, and which consists in
computing down all the four possible branches generated by the measurements at qubits 1 and 2.
Another possibility is to use the stabilizer formalism as explained in the reference paper [RBB03].
Yet another possibility is to use pattern composition, as we did before, and this is what we are
going to do.
We know that Rx(α) = J(α)H up to a global phase, hence the composite pattern J (α)(2, 3) ◦
H(1, 2) implements Rx(α). Now we may standardize it:
J (α)(2, 3) ◦ H(1, 2) = Xs23 M
2 E23X
⇒EX Xs23 Z
1E23E12
⇒MX Xs23 Z
s1Mx1E23E12
obtaining exactly the implementation above. Since our calculus preserves the semantics, we deduce
that the implementation is correct.
z-rotation.
Now, we have a method here for synthesizing further implementations. Let us replay it with another
rotation Rz(α). Again we know that Rz(α) = HRx(α)H, and we already know how to implement
both components H and Rx(α).
So we start with the pattern H(4, 5) ◦ Rx(α)(2, 3, 4) ◦ H(1, 2) and standardize it:
H(4, 5) ◦ Rx(α)(2, 3, 4) ◦ H(1, 2) =
H(4, 5)Xs34 Z
1+s2Mx2E34 E23X
1E12 ⇒EX
H(4, 5)Xs34 Z
1+s2Mx2X
2 E34Z
1E123 ⇒EZ
H(4, 5)Xs34 Z
1+s2Z
1E1234 ⇒MX
H(4, 5)Xs34 Z
1+s2Zs13 M
1E1234 ⇒MZ
4 E45X
s1 [Mα3 ]
1+s2Mx2M
1E1234 ⇒EX
Xs45 Z
s1 [Mα3 ]
1+s2Mx2M
1E12345 ⇒MX
s1 [Mα3 ]
1+s2Mx2M
1E12345 ⇒MZ
Xs45 Z
s2 [Mx4 ]
s3s1 [Mα3 ]
1+s2Mx2M
1E12345
To aid reading E23E12 is shortened to E123, E12E23E34 to E1234, and
t[Mαi ]
1+s is used as shorthand
for t[M−αi ]
Here for the first time, we see MZ rewritings, inducing the Z-action on measurements. The
resulting standardized pattern can therefore be rewritten further using the extended calculus:
Xs45 Z
s2 [Mx4 ]
s3s1 [Mα3 ]
1+s2Mx2M
1E12345 ⇒S
s2+s4
s1+s3
1+s2Mx2M
1E12345
obtaining the pattern given in the reference paper [RBB03, p.5].
However, just as in the case of the Rx rotation, we also have Rz(α) = HJ(α) up to a global
phase, hence the pattern H(2, 3)J (α)(1, 2) also implements Rz(α), and we may standardize it:
H(2, 3) ◦ J (α)(1, 2) = Xs23 Mx2 E23X
1 E12
⇒EX Xs23 Z
1 E123
⇒MX Xs23 Z
1 E123
obtaining a 3 qubit standard pattern for the z-rotation, which is simpler than the preceding one,
because it is based on the J (α) generators. Since the z-rotation Rz(α) is the same as the phase
operator:
P (α) =
0 eiα
up to a global phase, we also obtain with the same pattern an implementation of the phase oper-
ator. In particular, if α = π
, using the extended calculus, we get the following pattern for P (π
Xs23 Z
1E123.
General rotation.
The realization of a general rotation based on the Euler decomposition of rotations asRx(γ)Rz(β)Rx(α),
would results in a 7 qubit pattern. We get a 5 qubit implementation based on the J(α) decompo-
sition [DKP05]:
R(α, β, γ) = J(0)J(−α)J(−β)J(−γ)
(The parameter angles are inverted to make the computation below more readable.) The extended
standardization procedure yields:
J (0)(4, 5)J (−α)(3, 4)J (−β)(2, 3)J (−γ)(1, 2) =
Xs45 M
4E45X
3 E34X
2 E23X
1E12 ⇒EX
4E45X
3 E34X
1E123 ⇒MX
4E45X
3 E34X
1E123 ⇒EXZ
Xs45 M
4E45X
1E1234 ⇒MXZ
4 E45X
s1 [Mα3 ]
s2 [M
1E1234 ⇒EXZ
Xs45 M
s1 [Mα3 ]
s2 [M
1E12345 ⇒MXZ
s2 [M04 ]
s1 [Mα3 ]
s2 [M
1E12345 ⇒S
s2+s4
s1+s3
s2 [M
1E12345
CNOT (∧X).
This is our first example with two inputs and two outputs. We use here the trivial pattern I with
computation space {1}, inputs {1}, outputs {1}, and empty command sequence, which implements
the identity over H1.
One has ∧X = (I ⊗ H)∧Z(I ⊗ H), so we get a pattern using 4 qubits over {1, 2, 3, 4}, with
inputs {1, 2}, and outputs {1, 4}, where one notices that inputs and outputs intersect on the control
qubit {1}:
(I(1)⊗ 〈(3, 4))∧Z(1, 3)(I(1) ⊗ 〈(2, 3)) = Xs34 Mx3E34E13X
By standardizing:
3E34 E13X
2E23 ⇒EX
3 E34X
2E13E23 ⇒EX
Xs34 Z
2E13E23E34 ⇒MX
Xs34 Z
2E13E23E34
Note that, in this case, we are not using the E1234 abbreviation, because the underlying struc-
ture of entanglement is not a chain. This pattern was already described in Aliferis and Leung’s
paper [AL04]. In their original presentation the authors actually use an explicit identity pattern (us-
ing the teleportation pattern J (0, 0) presented above), but we know from the careful presentation
of composition that this is not necessary.
We present now a family of patterns preparing the GHZ entangled states |0 . . . 0〉 + |1 . . . 1〉. One
GHZ(n) = (Hn ∧Zn−1n . . . H2 ∧Z12)|+. . .+〉
and by combining the patterns for ∧Z and H, we obtain a pattern with computation space
{1, 2, 2′, . . . , n, n′}, no inputs, outputs {1, 2′, . . . , n′}, and the following command sequence:
MxnEnn′E(n−1)′n . . . X
Mx2E22′E12
With this form, the only way to run the pattern is to execute all commands in sequence. The
situation changes completely, when we bring the pattern to extended standard form:
MxnEnn′E(n−1)′n . . . X
Mx3E33′ E2′3X
Mx2E22′E12 ⇒
MxnEnn′E(n−1)′n . . . X
Mx3 Z
2E33′E2′3E22′E12 ⇒
MxnEnn′E(n−1)′n . . . X
s2 [Mx3 ]M
2E33′E2′3E22′E12 ⇒⋆
Xsnn′ . . . X
sn−1 [Mxn ] . . .
s2 [Mx3 ]M
2Enn′E(n−1)′n . . . E33′E2′3E22′E12 ⇒S
Xs2+s3+···+sn
. . . Xs2+s3
Mxn . . .M
2Enn′E(n−1)′n . . . E33′E2′3E22′E12
All measurements are now independent of each other, it is therefore possible after the entanglement
phase, to do all of them in one round, and in a subsequent round to do all local corrections. In
other words, the obtained pattern has constant computational depth complexity 2.
Controlled-U .
This final example presents another instance where standardization obtains a low computational
depth complexity, the proof of this fact can be found in [BK06]. For any 1-qubit unitary U , one
has the following decomposition of ∧U in terms of the generators J(α) [DKP05]:
∧U12 = J01Jα
2 ∧Z12J
−π−δ−β
2 ∧Z12J
−β+δ−π
with α′ = α + β+γ+δ
. By translating each J operator to its corresponding pattern, we get the
following wild pattern for ∧U :
BEBCX
A EABX
j EjkX
i Eij
h EhiX
g EghX
fEfgEAfX
e Eef
Xsde M
d EdeX
π+δ+β
c EcdX
bEbcEAbX
β−δ+π
a Eab
In order to run the wild form of the pattern one needs to follow the pattern commands in sequence.
It is easy to verify that, because of the dependent corrections, one needs at least 12 rounds to
complete the execution of the pattern. The situation changes completely after extended standard-
ization:
si+sg+se+sc+sa
sj+sh+sf+sd+sb
sA+se+sc
sh+sf+sd+sb [M
]sg+se+sc+sa [M
sf+sd+sb
M0f [M
sd+sb [M
sc+sa [M
π+δ+β
sbM0bM
β−δ+π
EBCEABEjkEijEhiEghEfgEAfEefEdeEcdEbcEabEAb
Now the order between measurements is relaxed, as one sees in Figure 2, which describes the depen-
dency structure of the standard pattern above. Specifically, all measurements can be completed in
7 rounds. This is just one example of how standardization lowers computational depth complexity,
and reveals inherent parallelism in a pattern.
Figure 2: The dependency graph for the standard ∧U pattern.
7 The no dependency theorems
From standardization we can also infer results related to dependencies. We start with a simple
observation which is a direct consequence of standardization.
Lemma 14 Let P be a pattern implementing some cptp-maps T , and suppose P’s command se-
quence has measurements only of the Mx and My kind, then U has a standard implementation,
having only independent measurements, all being of the Mx and My kind (therefore of computa-
tional depth complexity at most 2).
Proof. Write P ′ for the standard pattern associated to P. By equations (15) and (16), the X-
actions can be eliminated from P ′, and then Z-actions can be eliminated by using the extended
calculus. The final pattern still implements T , has no longer any dependent measurements, and
has therefore computational depth complexity at most 2. ✷
Theorem 4 Let U be a unitary operator, then U is in the Clifford group iff there exists a pattern
P implementing U , having measurements only of the Mx and My kind.
Proof. The “only if” direction is easy, since we have seen in the example section, standard patterns
for ∧X, H and P (π
) which had only independent Mx and My measurements. Hence any Clifford
operator can be implemented by a combination of these patterns. By the lemma above, we know
we can actually choose these patterns to be standard.
For the “if” direction, we prove that U belongs to the normalizer of the Pauli group, and hence
by definition to the Clifford group. In order to do so we use the standard form of P written as
P ′ = CP ′MP ′EP ′ which still implements U , and has only Mx and My measurements. Recall that,
because of equations (15) and (16), these measurements are independent.
Let i be an input qubit, and consider the pattern P ′′ = P ′Ci, where Ci is either Xi or Zi.
Clearly P ′′ implements UCi. First, one has:
CP ′MP ′EP ′Ci ⇒⋆EC CP ′MP ′C ′EP ′
for some non-dependent sequence of corrections C ′, which, up to free commutations can be written
uniquely as C ′OC
′′, where C ′O applies on output qubits, and therefore commutes to MP ′ , and C
applies on non-output qubits (which are therefore all measured in MP ′). So, by commuting C
both through MP ′ and CP ′ (up to a global phase), one gets:
CP ′MP ′C
′EP ′ ⇒⋆ C ′OCP ′MP ′C ′′EP ′
Using equations (15), (16), and the extended calculus to eliminate the remaining Z-actions, one
gets:
MP ′C
′′ ⇒⋆MC,S SMP ′
for some product S =
{j∈J} S
j of constant shifts
8, applying to some subset J of the non-output
qubits. So:
C ′OCP ′MP ′C
′′EP ′ ⇒⋆MC,S C ′OCP ′SMP ′EP ′
⇒⋆ C ′OC ′′OCP ′MP ′EP ′
where C ′′O is a further constant correction obtained by signal shifting CP ′ with S. This proves that
P ′′ also implements C ′OC ′′OU , and therefore UCi = C ′OC ′′OU which completes the proof, since C ′OC ′′O
is a non dependent correction. ✷
The “only if” part of this theorem already appears in previous work [RBB03, p.18]. The “if”
part can be construed as an internalization of the argument implicit in the proof of Gottesman-Knill
theorem [NC00, p.464].
We can further prove that dependencies are crucial for the universality of the model. Observe
first that if a pattern has no measurements, and hence no dependencies, then it follows from (D2)
that V = O, i.e., all qubits are outputs. Therefore computation steps involve only X, Z and
8Here we have used the trivial equations Za+1i = ZiZ
i and X
i = XiX
∧Z, and it is not surprising that they compute a unitary which is in the Clifford group. The
general argument essentially consists in showing that when there are measurements, but still no
dependencies, then the measurements are playing no part in the result.
Theorem 5 Let P be a pattern implementing some unitary U , and suppose P’s command sequence
doesn’t have any dependencies, then U is in the Clifford group.
Proof. Write P ′ for the standard pattern associated to P. Since rewriting is sound, P ′ still
implements U , and since rewriting never creates any dependency, it still has no dependencies. In
particular, the corrections one finds at the end of P ′, call them C, bear no dependencies. Erasing
them off P ′, results in a pattern P ′′ which is still standard, still deterministic, and implementing
U ′ := C†U .
Now how does the pattern P ′′ run on some input φ ? First φ⊗|+. . .+〉 goes by the entanglement
phase to some ψ ∈ HV , and is then subjected to a sequence of independent 1-qubit measurements.
Pick a basis B spanning the Hilbert space generated by the non-output qubits HVrO and associated
to this sequence of measurements.
Since HV = HO ⊗HVrO and HVrO = ⊕φb∈B[φb], where [φb] is the linear subspace generated by
φb, by distributivity, ψ uniquely decomposes as:
φb∈B xb ⊗ φb
where φb ranges over B, and xb ∈ HO. Now since P ′′ is deterministic, there exists an x, and scalars
λb such that xb = λbx. Therefore ψ can be written x ⊗ ψ′, for some ψ′. It follows in particular
that the output of the computation will still be x (up to a scalar), no matter what the actual
measurements are. One can therefore choose them to be all of the Mx kind, and by the preceding
theorem U ′ is in the Clifford group, and so is U = CU ′, since C is a Pauli operator. ✷
From this section, we conclude in particular that any universal set of patterns has to include
dependencies (by the preceding theorem), and also needs to use measurements Mα where α 6= 0
modulo π
(by the theorem before). This is indeed the case for the universal set J (α) and ∧Z.
8 Other Models
There are several other approaches to measurement-based computation as we have mentioned in
the introduction. However, it is only for the one-way model that the importance of having all
the entanglement in front has been emphasized. For example, Gottesman and Chuang describe
computing with teleportation in the setting of the circuit model and hence the computation is very
sequential [GC99]. What we will do is to give a general treatment of a variety of measurement-
based models – including some that appear here for the first time – in the setting of our calculus.
More precisely we would like to know other potential definitions for commands N , E, M and C
that lead to a model that still satisfies the properties of: (i) being closed under composition; (ii)
universality and (iii) standardization.
Moreover we are interested in obtaining a compositional embedding of these models into a single
one-qubit measurement-based model. The teleportation model can indeed be embedded into the
one-way model. There is, however, a new model, the Pauli model – formally defined here for the
first time – which is motivated by considerations of fault tolerance [RAB04, DK05b, DKOS06]. The
Pauli model can be embedded into a slight generalization of the one-way model called the phase
model; also given here for the first time. The one-way model will trivially embed in the phase
model so by composition all the measurement-based models will embed in the phase model. We
could have done everything ab initio in terms of the phase model but this would have made much
of the presentation unnecessarily complicated at the outset.
We recall the remark from the introduction that these embeddings have three advantages: first,
we get a workable syntax for handling the dependencies of operators on previous measurement
outcomes, second, one can use these embeddings to transfer the measurement calculus previously
developed for the one-way model to obtain a calculus for the new model including, of course, a
standardization procedure that we get automatically; lastly, one can embed the patterns from the
phase model into the new models and vice versa. In essence, these compositional embeddings will
allow us to exhibit the phase model as being a core calculus for measurement-based computation.
However different models are interesting from the point of view of implementation issues like fault-
tolerance and ease of preparation of entanglement resources. Our embeddings allow one to move
easily between these models and to concentrate on the one-way model for designing algorithms and
proving general theorems.
This section has been structured into several subsections, one for each model and its embedding.
8.1 Phase Model
In the one-way model the auxiliary qubits are initialized to be in the |+〉 state. We extend the
one-way model to allow the auxiliary qubits to be in a more general state. We define the extended
preparation command Nαi to be the preparation of the auxiliary qubit i in the state |+α〉. We
also add a new correction command Zαi , called a phase correction to guarantee that we can obtain
determinate patterns. The dependent phase correction is written as Z
i with Z
i = I and
0 eiα
. Under conjugation, the phase correction, defines a new action over measurement:
†Mαi Z
and since the measurement is destructive, it simplifies to Mαi Z
i = M
i . This action does
not commute with Pauli actions and hence one cannot write a compact notation for dependent
measurement, as we did before, and the computation of angle dependencies is a bit more compli-
cated. Thereafter, a measurement preceded by a sequence of corrections on the same qubit will be
called a dependent measurement. Note that, by the absorption equations, this indeed can be seen
as a measurement, where the angle depends on the outcomes of some other measurements made
beforehand.
To complete the extended calculus it remains to define the new rewrite rules:
i ⇒ Z
i Eij EP
Mαi X
i ⇒ M
(−1)sα
Mαi Z
i ⇒ M
Mαi Z
i ⇒ M
The above rules together with the rewriting rules of the one-way model described in Section 5, lead
to a standardization procedure for the model. It is trivial that the one-way model is a fragment of
this generalized model and hence universality immediately follows. It is also easy to check that the
model is closed under composition and all the semantical properties of the one-way model can be
extended to this general model as well.
The choice of extended preparations and its concomitant phase correction is actually quite
delicate. One wishes to keep the standardizability of the calculus which constrains what can be
added but one also wishes to have determinate patterns which forces us to put in appropriate
corrections. The phase model is only a slight extension of the original one-way model, but it allows
a discussion of the next model which is of great physical interest.
8.1.1 Pauli model
An interesting fragment of the phase model is defined by restricting the angles of measurements to
{0, π
, π,−π
} i.e. Pauli measurements and the angles of preparation to 0 and π
. Also the correction
commands are restricted to Pauli corrections X, Z and Phase correction Z
8 . One readily sees that
the subset of angles is closed under the actions of the corrections and hence the Pauli model is
closed under composition.
Proposition 15 The Pauli model is approximately universal.
Proof. We know that the set consisting of J(0) (which is H), J(π
), and ∧Z is approximately
universal. Hence, to prove the approximate universality of Pauli model, it is enough to exhibit a
pattern in the Pauli model for each of these three unitaries. We saw before that J(0) and ∧Z are
computed by the following 2-qubit patterns:
J (0) := Xs12 M01E12
∧Z := E12
where both belong also to the Pauli model. The pattern for Jπ
in the one-way model is expressed
as follows:
) := Xs12 M
1 E12
= Xs12 M
1E12Z
The above forms do not fit in the Pauli model, since the first one uses a measurement with an angle
and the second uses Z
4 . However by teleporting the input qubit and then applying the Z
4 and
finally running the standardization procedure we obtain the following pattern in the Pauli model
for J(π
1E12Z
3E34 Z
1E12E23
= Xs34 M
3E34Z
1E12E23 Z
3E34Z
1E12E23 Z
s3+s2
−(−1)s1s2 π2
1E12E23E34N
Approximate universality for the Pauli model is now immediate. ✷
Note that we cannot really expect universality (as we had for the phase model) because the
angles are restricted to a discrete set. On the other hand it is precisely this restriction that makes
the Pauli model interesting from the point of view of implementation. The other particular interest
behind this model, apart from its simple structure, is based on the existence of a novel fault tolerant
technique for computing within this framework [BK05, RAB04, DKOS06].
8.2 Teleportation
Another class of measurement-based models – older, in fact, than the one-way model – uses 2-
qubit measurements. These are collectively referred to as teleportation models [Leu04]. Several
papers that are concerned with the relation and possible unification of these models [CLN05,
AL04, JP05] have already appeared. One aspect of these models that stands in the way of a
complete understanding of this relation, is that, whereas in the one-way model one has a clearly
identified class of measurements, there is less agreement concerning which measurements are allowed
in teleportation models.
We propose here to take as our class of 2-qubit measurements a family obtained as the conjugate
under the operator ∧Z of tensors of 1-qubit measurements. We show that the resulting teleportation
model is universal. Moreover, almost by construction, it embeds into the one-way model, and thus
exposes completely the relation between the two models.
Before embarking on the specifics of our family of 2-qubit measurements, we remark that the
situation commented above is more general:
Lemma 16 Let A be an orthonormal basis in ⊗nC2, with associated n-qubit measurement MA,
and Ai with i = 1, . . . , n be orthonormal bases in C2, with associated 1-qubit measurements MAii .
Then there exists a unique (up to a permutation) n-qubit unitary operator U such that:
MA1···n = U1···n(⊗iM
1···n
Proof. Take U to map ⊗iAi to A. ✷
This simple lemma says that general n-qubit measurements can always be seen as conjugated
1-qubit measurements, provided one uses the appropriate unitary to do so. As an example consider
the orthogonal graph basis G = ∧Z12{|±〉 ⊗ |±〉} then the two-qubit graph basis measurements are
defined as MG12 = ∧Z12(M01 ⊗M02 )∧Z12. It is now natural to extend our definition of M
12 to obtain
the family of 2-qubit measurements of interest:
12 := ∧Z12(M
2 )∧Z12 (17)
corresponding to projections on the basis Gα,β := ∧Z12(P1(α)⊗P2(β))({|±〉 ⊗ |±〉}. This family of
two-qubit measurements together with the preparation, entanglement and corrections commands
of the one-way model define the teleportation model.
Before we carry on, a clarification about our choice of measurements in the teleportation model
is necessary. The usual teleportation protocol uses Bell basis measurement defined with
B = ∧X12{|±〉 ⊗ |0/1〉}
MB12 = ∧X12(Mz1 ⊗Mz2 )∧X12
where Mz is the computational-basis measurement. Note how similar these equations are to the
equations defining the graph basis measurements. This is a clear indication that everything that
follows can be transferred to the case where X replaces Z, and B replaces G. However, since the
methodology we adopt is to embed the 2-qubit measurement based model in the one-way model,
and the latter is based on ∧Z and G, we will work with the graph-basis measurements. Furthermore,
since ∧Z is symmetric, whereas ∧X (a.k.a. as C-NOT) is not, the algebra is usually nicer to work
with.
Now we prove that the family of measurements in Equation 17 leads to a universal model,
which embeds nicely into the one-way model, but first we need to describe the important notion
of dependent measurements. These will arise as a consequence of standardization; they were not
considered in the existing teleportation models.
In what follows we drop the subscripts on the ∧Z unless they are really necessary. We write
(s(i), s(j)) ∈ Z2 × Z2 to represent outcome of a 2-qubit measurement, with the specific convention
that (0, 0), (0, 1), (1, 0), and (1, 1), correspond respectively to the cases where the state collapses
to ∧Z|+α〉|+α〉, ∧Z|+α〉|−α〉, ∧Z|−α〉|+α〉, and ∧Z|−α〉|−α〉.
We will use two types of dependencies for measurements associated with X-action and Z-action:
(s,t) = M
(−1)sα,(−1)tβ
(u,v)[M
ij ] = M
α+uπ,β+vπ
where s, t, u and v are in Z2. The two actions commute, so the equations above define unambigu-
ously the full dependent measurement (u,v)[M
(s,t). Here are some useful abbreviations:
(0,0)[Mα,β ](s,t) := [Mα,β ](s,t)
(u,v)[Mα,β ](0,0) := (u,v)[Mα,β ]
(0,0)[Mα,β ](0,0) :=Mα,β
Mα,x := Mα,0
Mα,y :=Mα,
As in the 1-qubit measurement case we obtain the following rewriting rules for the teleportation
model:
i ⇒ Xsi ZsjEij EX
i ⇒ ZsiEij EZ
(u,v)[M
(s,t)Xri ⇒ (u,v+r)[M
(s+r,t) MX
(u,v)[M
(s,t)Xrj ⇒ (u+r,v)[M
(s,t+r) MX
(u,v)[M
(s,t)Zri ⇒ (u+r,v)[M
(s,t) MZ
(u,v)[M
(s,t)Zrj ⇒ (u,v+r)[M
(s,t) MZ
to which we add also the trivial commutation rewriting which are possible between commands that
don’t overlap (meaning, acting on disjoint sets of qubits).
8.2.1 Embedding
We describe how to translate 2-qubit EMC patterns to 1-qubit patterns and vice versa. The
following equation plays the central role in the translation:
ij = Eij(M
j )Eij (18)
Note that this immediately gives the denotational semantics of two-qubit measurements as cptp-
maps. Furthermore, all other commands in the teleportation model are the same as in the one-way
model, so we have right away a denotational semantics for the entire teleportation model in terms
of cptp-maps.
We write P for the collection of patterns in the one-way model and T for the collection of
patterns in the teleportation model.
Theorem 6 There exist functions [·]f : P → T and [·]b : T → P such that
1. ∀P ∈ P : [[P]] = [[[P]f ]];
2. ∀T ∈ T : [[T ]] = [[[T ]b]];
3. [·]f ◦ [·]b and [·]b ◦ [·]f are both identity maps.
Proof. We first define the forward map [·]f in stages as follows for any patterns P = (V, I,O,An . . . A1):
1. For any i ∈ V rO (i.e. measured qubits) we add an auxiliary qubit id called a dummy qubit
to the space V .
2. For any i ∈ V rO we replace any occurrence of Mαi with Mαi Mxid .
3. We then replace each of the newly created occurrences of Mαi M
Eiid .
Now we show that the first condition stated in the theorem holds; we do this stage wise. The
first two stages are clear because we are just adding qubits that have no effect on the pattern
because they are not entangled with any pre-existing qubit, and no other command depends on a
measurement applied to one of the dummy qubits. Furthermore, we add qubits in the state |+〉
and measure them in the |±〉 basis. The invariance of the semantics under stage 3 is an immediate
consequence of Equation 18 and the fact that all the measurements are destructive, and hence an
entanglement command on qubits appearing after a measurement of any of those qubits can just
be removed.
The map [·]b is defined similarly except that there is no need to add dummy qubits. One
only needs to replace any two-qubit measurement M
ij with M
j Eij . Again, this clearly pre-
serves the semantics of patterns because of Equation 18 and the above remark about destructive
measurements. Thus condition 2 of the theorem holds.
The fact that the two maps are mutual inverses follows easily. As all the steps in the translations
are local we can reason locally. Looking at the forward mapping followed by the backward mapping
we get the following sequence of transformations
Mαi ⇒stage 1,2 Mαi Mxid
⇒Equation 18 Mα,xiid Eiid
⇒Equation 18 Mαi MxidEiidEiid
⇒ Mαi Mxid
⇒ Mαi
This shows that we have the third condition of the theorem. ✷
Note that the translations are compositional since the denotational semantics is and also it fol-
lows immediately that the teleportation model is universal and admits a standardization procedure.
Example. Consider the teleportation pattern in the teleportation model given by the command
sequence: Xs13 Z
12 E23, we perform the above steps:
12 E23 ⇒Equation 18
Xs13 Z
2E12E23
and hence obtain the teleportation pattern with 1-qubit measurements.
Example. We saw before, the following EMC 1-qubit pattern for Rz(α) which can be embedded
to an EMC 2-qubit pattern using the above steps:
s1M−α1 E12E23 ⇒stage 1,2
s1Mx2dM
E12E23 ⇒Equation 18 and standardization
Xs23 Z
](s1,0)M
E11dE22dE12E23
Note that we have explicit algorithmic translations between the models and not just illustrative
examples. This is the main advantage of our approach in unifying these two models compared to
the extant work [CLN05, AL04, JP05].
9 Conclusion
We have presented a calculus for the one-way quantum computer. We have developed a syntax
of patterns and, much more important, an algebra of pattern composition. We have seen that
pattern composition allows for a structured proof of universality, which also results in parsimonious
implementations. We develop an operational and denotational semantics for this model; in this
simple first-order setting their equivalence is clear.
We have developed a rewrite system for patterns which preserves the semantics. We have
shown further that our calculus defines a polynomial-time standardization algorithm transforming
any pattern to a standard form where entanglement is done first, then measurements, then local
corrections. We have inferred from this procedure that the denotational semantics of any pattern is
a cptp-map and also proved that patterns with no dependencies, or using only Pauli measurements,
may only implement unitaries in the Clifford group.
In addition we introduced some variations of the one-way and teleportation models and pre-
sented compositional back-and-forth embeddings of these models into the one-way model. This
allows one to carry forward all the theory we have developed: semantics, rewrite rules, standard-
ization, no-dependency theorems and universality. In fact the result of making the connection
between the one-way model and the teleportation model is to introduce ideas: dependent mea-
surements, standard forms for patterns and a standardization procedure which had never been
considered before for the teleportation model. This shows the generality of our formalism: we
expect that any yet to be discovered measurement-based computation frameworks can be treated
in the same way.
Perhaps the most important aspect of standardization is the fact that now we can make patterns
maximally parallel and distributed because all the entanglement operators, i.e. non-local operators,
can be performed at the beginning of the computation. Then from the dependency structure that
can be obtained from the standard form of a pattern the measurements can be organized to be as
parallel as possible. This is the essence of the difference between measurement-based computation
and the quantum circuit model or the quantum Turing machine.
We feel that our measurement calculus has shown the power of the formalisms developed by
the programming languages community to analyze quantum computations. The ideas that we use:
rewriting theory, (primitive) type theory and above all, the importance of reasoning compositionally,
locally and modularly, are standard for the analysis of traditional programming languages. However,
for quantum computation these ideas are in their infancy. It is not merely a question of adapting
syntax to the quantum setting; there are fundamental new ideas that need to be confronted. What
we have done here is to develop such a theory in a new, physically-motivated setting.
There were prior discussions about putting patterns in a standard form [RB02] but these worked
only with strongly deterministic patterns, furthermore one needs to know which unitary is being
implemented. In our case the rewrite rules are entirely local and work equally well with all patterns.
An interesting question related to the measurement calculus is whether one can give sufficient
conditions – depending only on the entanglement structure of a pattern – that guarantee deter-
minacy. In a related paper the first two authors have solved this problem [DK05a]. In effect
given an entanglement structure with distinguished inputs and outputs one can enumerate all the
unitaries that can be implemented with it. This gives a precise handle on the entanglement re-
sources needed in the design of specific algorithms and protocols directly in the measurement-based
model [dBDK06].
Finally, there is also a compelling reading of dependencies as classical communications, while
local corrections can be thought of as local quantum operations in a multipartite scenario. From
this point of view, standardization pushes non-local operations to the beginning of a distributed
computation, and it seems the measurement calculus could prove useful in the analysis of dis-
tributed quantum protocols. To push this idea further, one needs first to articulate a definition of
a distributed version of the measurement calculus; this was done in a recent paper [DDKP05]. The
distributed version of the calculus was then used to analyze a variety of quantum protocols and to
examine the notion of knowledge flow in them [DP05].
Acknowledgments
We thank the anonymous referees for their helpful comments. We would like to thank Ellie D’Hondt
for implementing an interpreter for the measurement calculus and Daniel Gottesman for clarifying
the extent to which Theorem 4 was implicit in his own work. We have benefited from discus-
sions with Samson Abramsky, Hans Briegel, Dan Browne, Philippe Jorrand, Harold Olivier, Simon
Perdrix and Marcus Silva. Elham Kashefi was partially supported by the PREA, MITACS, OR-
DCF, CFI and ARDA projects during her stay at University of Waterloo where this work was
finished. Prakash Panangaden thanks EPSRC and NSERC for support and Samson Abramsky and
the Oxford University Computing Laboratory for hospitality at Oxford where this work was begun.
References
[AC04] S. Abramsky and B. Coecke. A categorical semantics of quantum protocols. In IEEE
Computer Science Press, editor, Proceedings of the 19th Annual IEEE Symposium
on Logic in Computer Science (LiCS), 2004.
[AD04] S. Abramsky and R. Duncan. A categorical quantum logic. In Selinger [Sel04a].
quant-ph/0512114.
[AG05] T. Altenkirch and J. Grattage. A functional quantum programming language. In
IEEE Computer Science Press, editor, Proceedings of the 20th Annual IEEE Sympo-
sium on Logic in Computer Science (LiCS), 2005.
[AL04] P. Aliferis and D. W. Leung. Computation by measurements: a unifying picture.
Physical Review A, 70, 2004.
[Bar84] H. P. Barendregt. The Lambda Calculus, Its Syntax and Semantics. Studies in Logic.
North-Holland, 1984.
[BB84] G. Brassard and C. H. Bennett. Public key distribution and coin tossing. In Pro-
ceedings of IEEE International Conference on Computers, Systems and Signal Pro-
cessing, 1984.
[BBC+93] C. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. Wootters. Tele-
porting an unknown quantum state via dual classical and EPR channels. Physical
Review Letters, 1993.
[BBFM06] S. C. Benjamin, D. E. Browne, J. Fitzsimons, and J. J. L. Morton. Brokered graph
state quantum computing. New Journal of Physics, 8, 2006.
[BES05] S.C. Benjamin, J. Eisert, and T. M. Stace. Optical generation of matter qubit graph
states. New Journal of Physics, 7, 2005.
[BK05] S. Bravyi and A. Kitaev. Universal quantum computation with ideal clifford gates
and noisy ancillas. Physical Review A, 71, 2005.
[BK06] A. Broadbent and E. Kashefi. On parallelizing quantum circuits. In Preparation,
2006.
[BR05] D. E. Browne and T. Rudolph. Resource-efficient linear optical quantum computa-
tion. Physical Review Letters, 95, 2005.
[BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal of Com-
puting, 5(26), 1997.
[CAJ05] S. R. Clark, C. Moura Alves, and D. Jaksch. Efficient generation of graph states for
quantum computation. New Journal of Physics, 7, 2005.
[CCWD06] Q. Chen, J. Cheng, K. L. Wang, and J. Du. Efficient construction of two-dimensional
cluster states with probabilistic quantum gates. Physical Review A, 73, 2006.
[Cho75] M. D. Choi. Completely positive linear maps on complex matrices. Linear Algebra
and Applications, 10, 1975.
[CLN05] A. M. Childs, D. W. Leung, and M. A. Nielsen. Unified derivations of measurement-
based schemes for quantum computation. Physical Review A, 71, 2005.
http://arxiv.org/abs/quant-ph/0512114
[Coe04] B. Coecke. The logic of entanglement. quant-ph/0402014, 2004.
[DAB03] W. Dür, H. Aschauer, and H. J. Briegel. Multiparticle entanglement purification for
graph state. Physical Review Letters, 91, 2003.
[dBDK06] N. de Beaudrap, V. Danos, and E. Kashefi. Phase map decomposition for unitaries.
quant-ph/0603266, 2006.
[DDKP05] V. Danos, E. D’Hondt, E. Kashefi, and P. Panangaden. Distributed measurement-
based quantum computation. In Selinger [Sel05b]. quant-ph/0506070.
[Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum
computer. In Proceedings of the Royal Society of London, volume A400, 1985.
[Deu87] D. Deutsch. Quantum computers. Computer Bulletin, 3(2), 1987.
[Deu89] D. Deutsch. Quantum computational networks. Proceedings of the Royal Society of
London, 425, 1989.
[DHN06] C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen. Noise thresholds for optical
cluster-state quantum computation. Physical Review A, 73, 2006.
[DJ92] D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. In
Proceedings of the Royal Society of London, volume 439, 1992.
[DK05a] V. Danos and E. Kashefi. Determinism in the one-way model. quant-ph/0506062,
2005.
[DK05b] V. Danos and E. Kashefi. Pauli measurements are universal. In Selinger [Sel05b].
[DKOS06] V. Danos, E. Kashefi, H. Olivier, and M. Silva. Pauli model, a new approach towards
fault tolerant quantum computing. In Preparation, 2006.
[DKP05] V. Danos, E. Kashefi, and P. Panangaden. Parsimonious and robust realizations of
unitary maps in the one-way model. Physical Review A, 72, 2005.
[dNDM04a] M. Van den Nest, J. Dehaene, and B. De Moor. An efficient algorithm to recognize
local clifford equivalence of graph states. Physical Review A, 70, 2004.
[dNDM04b] M. Van den Nest, J. Dehaene, and B. De Moor. Graphical description of the action
of local clifford transformations on graph states. Physical Review A, 69, 2004.
[DP05] E. D’Hondt and P. Panangaden. Reasoning about quantum knowledge. In Proceed-
ings of the 25th Conference on Foundations of Software Technology and Theoretical
Computer Science, 2005.
[DP06] E. D’Hondt and P. Panangaden. Quantum weakest preconditions. Mathematical
Structures in Computer Science, 16, 2006.
[DS96] C. Dürr and M. Santha. A decision procedure for unitary linear quantum cellular
automata. In Proceedings of FOCS’96 – Symposium on Foundations of Computer
Science. LNCS, 1996.
http://arxiv.org/abs/quant-ph/0402014
http://arxiv.org/abs/quant-ph/0603266
http://arxiv.org/abs/quant-ph/0506070
http://arxiv.org/abs/quant-ph/0506062
[Dun05] R. Duncan. An abstract approach to entanglement, Dec 2005. Mathematical Struc-
tures In Quantum Informatics, QDay II.
[Eke91] A. Ekert. Quantum cryptography based on bell’s theorem. Physical Review Letters,
67, 1991.
[Gay05] S. J. Gay. Quantum programming languages: Survey and bibliography. Bulletin of
the EATCS, 86, 2005.
[GC99] D. Gottesman and I. L. Chuang. Quantum teleportation is a universal computational
primitive. Nature, 402, 1999.
[GHW05] G. Gilbert, M. Hamrick, and Y. S. Weinstein. Efficient construction of photonic
quantum computational clusters. quant-ph/0512110, 2005.
[GN05] S. J. Gay and R. Nagarajan. Communicating quantum processes. In Proceedings
of the 32nd ACM SIGACT-SIGPLAN Symposium on Principles of Programming
Languages (POPL). ACM Press, 2005. quant-ph/0409052.
[Got97] D. Gottesoman. Stabilizer codes and quantum error correction. PhD thesis, California
Institute of Technology, 1997.
[Gro98] L. K. Grover. A framework for fast quantum mechanical algorithms. In Proceedings
of STOC’98 – Symposium on Theory of Computing, 1998.
[HDB05] L. Hartmann, W. Dür, and H. J. Briegel. Steady state entanglement in open and
noisy quantum systems at high temperature. quant-ph/0512219, 2005.
[HEB04] M. Hein, J. Eisert, and H. J. Briegel. Multi-party entanglement in graph states.
Physical Review A, 69, 2004.
[JL04] P. Jorrand and M. Lalire. Toward a quantum process algebra. In Proceedings of the
1st ACM Conference on Computing Frontiers. ACM Press, 2004. quant-ph/0312067.
[JP05] P. Jorrand and S. Perdrix. Unifying quantum computation with projective measure-
ments only and one-way quantum computation. In Yuri I. Ozhigov, editor, Quantum
Informatics 2004, volume 5833 of SPIE Proceedings, 2005.
[KPA06] A. Kay, J. K. Pachos, and C. S. Adams. Graph-state preparation and quantum
computation with global addressing of optical lattices. Physical Review A, 73, 2006.
[Leu04] D. W. Leung. Quantum computation by measurements. International Journal of
Quantum Information, 2(1), 2004.
[MP04] M. Mhalla and S. Perdrix. Complexity of graph state preparation. quant-ph/0412071,
2004.
[NC00] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information.
Cambridge University Press, 2000.
[Nie03] M. A. Nielsen. Universal quantum computation using only projective measurement,
quantum memory, and preparation of the 0 state. Physical Review A, 308, 2003.
http://arxiv.org/abs/quant-ph/0512110
http://arxiv.org/abs/quant-ph/0409052
http://arxiv.org/abs/quant-ph/0512219
http://arxiv.org/abs/quant-ph/0312067
http://arxiv.org/abs/quant-ph/0412071
[Nie04] M. A. Nielsen. Optical quantum computation using cluster states. Physical Review
Letters, 93, 2004.
[Ö01] B. Ömer. Procedural quantum programming. In Proceedings of the AIP Conference
on Computing Anticipatory Systems (AIP Conference Proceedings 627). American
Institute of Physics, 2001.
[Per95] A. Peres. Quantum Theory: Concepts and Methods. Kluwer Academic, 1995.
[Per03] S. Perdrix. State transfer instead of teleportation in measurement-based quantum
computation. International Journal of Quantum Information, 3(1), 2003.
[PJ04] S. Perdrix and P. Jorrand. Measurement-based quantum turing machines and their
universality. quant-ph/0404146, 2004.
[Pre98] J. Preskill. Fault-tolerant quantum computation. In H. K. Lo, S. Popescu, and
T. P. Spiller, editors, Introduction to Quantum Computation and Information. World
Scientific, 1998.
[RAB04] R. Raussendorf, S. Anders, and H. J. Briegel. Fault-tolerant quan-
tum computation using graph states. Communication to the Quantum
Information and Quantum Control Conference, Fields Institute, Toronto.
http://atlas-conferences.com/c/a/n/n/80.htm, 2004.
[RB01] R. Raussendorf and H. J. Briegel. A one-way quantum computer. Physical Review
Letters, 86, 2001.
[RB02] R. Raussendorf and H. J. Briegel. Computational model underlying the one-way
quantum computer. Quantum Information & Computation, 2, 2002.
[RBB03] R. Raussendorf, D. E. Browne, and H. J. Briegel. Measurement-based quantum
computation on cluster states. Physical Review A, 68, 2003.
[Sch03] D. Schlingemann. Cluster states, algorithms and graphs. quant-ph/0305170, 2003.
[Sel04a] P. Selinger, editor. Proceedings of the 2nd International Workshop on Quantum
Programming Languages, TUCS General Publications, 2004.
[Sel04b] P. Selinger. Towards a quantum programming language. Mathematical Structures in
Computer Science, 14(4), 2004.
[Sel04c] P. Selinger. Towards a semantics for higher-order quantum computation. In Pro-
ceedings of the 2nd International Workshop on Quantum Programming Languages
[Sel04a].
[Sel05a] P. Selinger. Dagger compact closed categories and completely positive maps. In
Proceedings of the 3nd International Workshop on Quantum Programming Languages
[Sel05b].
[Sel05b] P. Selinger, editor. Proceedings of the 3nd International Workshop on Quantum
Programming Languages, Electronic Notes in Theoretical Computer Science, 2005.
http://arxiv.org/abs/quant-ph/0404146
http://atlas-conferences.com/c/a/n/n/80.htm
http://arxiv.org/abs/quant-ph/0305170
[Sho94] P. W. Shor. Algorithms for quantum computation: Discrete logarithms and factor-
ing. In Proceedings of FOCS’94 – Symposium on Foundations of Computer Science.
LNCS, 1994.
[SV05] P. Selinger and B. Valiron. A lambda calculus for quantum computation with classical
control. In Proceedings of the 7th International Conference on Typed Lambda Cal-
culi and Applications (TLCA), volume 3461 of Lecture Notes in Computer Science.
Springer, 2005.
[SW04] B. Schumacher and R. F. Werner. Reversible quantum cellular automata.
quant-ph/0405174, 2004.
[SZ00] J. W. Sanders and P. Zuliani. Quantum programming. In Mathematics of Program
Construction, volume 1837 of Lecture Notes in Computer Science. Springer, 2000.
[TPKV04] M. S. Tame, M. Paternostro, M. S. Kim, and V. Vedral. Toward a more economical
cluster state quantum computation. quant-ph/0412156, 2004.
[TPKV06] M. S. Tame, M. Paternostro, M. S. Kim, and V. Vedral. Natural three-qubit inter-
actions in one-way quantum computing. Physical Review A, 73, 2006.
[Unr05] D. Unruh. Quantum programs with classical output streams. In Selinger [Sel05b].
[vD96] W. van Dam. Quantum cellular automata. Master’s thesis, Computer Science Ni-
jmegen, 1996.
[vT04] A. van Tonder. A lambda calculus for quantum computation. SIAM Journal on
Computing, 33(5), 2004.
[Wat95] J. Watrous. On one-dimensional quantum cellular automata. In Proceedings of
FOCS’95 – Symposium on Foundations of Computer Science. LNCS, 1995.
[WkJRR+05] P. Walther, k. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. As-
pelmeyer, and A. Zeilinger. Experimental one-way quantum computing. Nature, 434,
2005.
A Background on Quantum Mechanics and Quantum Computa-
We give a brief summary of quantum mechanics and quantum computing. We develop some of
the algebra, define some notations, and prove a couple of equations which we have used in the
paper. Although the paper is self-contained, the reader will find the expository book of Nielsen and
Chuang [NC00] useful for quantum computation or the excellent book by Peres [Per95] for general
background on quantum mechanics.
http://arxiv.org/abs/quant-ph/0405174
http://arxiv.org/abs/quant-ph/0412156
A.1 Linear Algebra for Quantum Mechanics
We assume that the reader is familiar with the basic notion of a vector space. In quantum mechanics
we always consider vector spaces over the complex numbers. For quantum computation the vector
spaces are always finite dimensional. The vector spaces that arise in quantum mechanics are Hilbert
spaces and are thus usually written H; that is they have an inner product usually written 〈u, v〉
where u and v are vectors. The inner product is a map from H×H to the complex numbers C. The
inner product is linear in the second argument but anti -linear in the first argument. In general,
there is a topological completeness condition on Hilbert spaces but, in the finite dimensional case
this is automatic and we will ignore it.
Following Dirac, it is customary to call elements of H kets and write them in the form |u〉 or
whatever symbol is appropriate inside the half-bracket. The dual vectors are called bras and are
written 〈v|; the pairing thus can naturally be identified – conceptually and notationally – with the
inner product.
Linear operators come naturally with vector spaces; a linear operator is a linear map from
a vector space to itself. Linear operators on finite dimensional spaces are often represented as
matrices. The most important notion for an operator on a Hilbert space is that of an adjoint.
Definition 17 If A : H → H′ is a linear operator then the adjoint, written A†, is a linear operator
from H′ to H such that
∀u ∈ H′, v ∈ H〈u,Av〉 = 〈A†u, v〉.
In terms of matrices this just amounts to transposing the matrix and complex conjugation each
of the matrix entries; sometimes this is called the hermitian conjugate. An inner product preserving
linear map is called a unitary embedding. When H = H′ we can also define the following operators. A
hermitian operator A is one such that A = A† and a unitary operator U is one such that U−1 = U †.
A projection P is a linear operator such that P 2 = P and P = P †. A projection operator can be
identified with a subspace, namely its range. The eigenvalues of a hermitian operator are always
real. Suppose U is a unitary, and P a projection, then UPU † is also a projection.
It is common to use the Dirac notation to write projection operators as follows: given a vector
|a〉 of unit norm, the projection onto the subspace spanned by |a〉 is written |a〉〈a|. To see why this
makes sense, suppose that |b〉 is another vector then its component along |a〉 is the inner product
〈a, b〉. Now if we just juxtapose the expressions |a〉〈a| and |b〉 we get |a〉〈a, b〉, viewing the 〈a, b〉 as
a number and moving it to the front we get 〈a, b〉|a〉 as the result, which is the right answer for the
projection of |b〉 onto |a〉. Thus one can apply the projection operator just by juxtaposing it with
the vector. This kind of suggestive manipulation is part of the appeal of the Dirac notation.
One important fact – the spectral theorem for hermitian operators – states that if M is a
hermitian operator, λi are its eigenvalues and Pi are projection operators onto the corresponding
eigenspaces then one can write
λiPi.
If we have |i〉 as the normalized eigenvectors for the eigenvalues λi then we can write this in Dirac
notation as:
λi|i〉〈i|.
Finally we need to combine Hilbert spaces.
Definition 18 Given two Hilbert spaces H with basis vectors {ai|1 ≤ i ≤ n} and H′ with basis
{bj |1 ≤ j ≤ m} we define the tensor product, written H⊗H′, as the vector space of dimension n ·m
with basis ai ⊗ bj .
There are more elegant, basis-independent ways of describing the tensor product but this definition
will serve our needs. We almost never write the symbol ⊗ between the vectors. In the Dirac
notation this is always omitted and one writes, for example, |uv〉 instead of |u〉 ⊗ |v〉.
The important point is that there are vectors that cannot be written as the tensor product of
vectors. For example, we can write a1 ⊗ b1 + a2 ⊗ b2 where the ai and the bi are basis vectors of
two 2-dimensional Hilbert spaces. This means that given a general element of H ⊗ H′ one cannot
produce elements of H and H′; this is very different from the cartesian product of sets. This is the
mathematical manifestation of entanglement.
A very important function on square matrices is the trace. The usual trace – i.e. the sum of
the diagonal entries – is basis independent and is actually equal to the sum of the eigenvalues,
counted with multiplicity. The trace of A is written tr(A) and satisfies the cyclicity property
tr(AB) = tr(BA); applying this repeatedly one gets
tr(A1 . . . An) = tr(Aσ(1) . . . Aσ(n))
where σ is a cyclic permutation. The explicit formula for the trace of A : V → V is tr(A) =
i〈i|A|i〉 where |i〉 is a basis for V .
One often needs to compute a partial trace. Consider a linear map L : V ⊗ W → V ⊗W .
Suppose that |vi〉 is a basis for V and |wi〉 is a basis for W then |viwj〉 is a basis for V ⊗W . Now
we can define the partial trace over V as
trV (A) : W → W =
〈vi|A|vi〉.
This corresponds to removing the V dependency; often we use the phrase “tracing out the V
component.”
A.2 Quantum Mechanics
We state the basic facts of quantum mechanics and will not discuss the experimental basis for this
framework. The key aspects of quantum mechanics are:
• the states of a quantum system form a Hilbert space,
• when two quantum systems are combined, the state space of the composite system is obtained
as the tensor product of the state spaces of the individual systems, and
• the evolution of a quantum system is given by a unitary operator, and
• the effect of a measurement is indeterminate.
The first says that one can form superpositions of the states. This is one of the most striking
features of quantum mechanics. Thus states are not completely distinct as they are in classical
systems. The inner product measures the extent to which states are distinct. The fact that systems
are combined by tensor product says that there are states that of composite systems that cannot
be decomposed into individual pieces. This is the phenomenon of entanglement or non-locality.
Measurement is what gives quantum mechanics its indeterminate character. The usual case,
called projective measurements, is when the quantity being measured is described by a hermitian
operator M . The possible outcomes are the eigenvalues of M . If M is an observable (hermitian
operator) with eigenvalues λi and eigenvectors |φi〉 and we have a generic state |ψ〉 =
i ci|φi〉
then the probabilities and expectation values of the measurement outcomes are given by:
• Prob(λi||ψ〉) = |ci|2
• E[M ||ψ〉] =
i |ci|2λi =
i cic̄i〈φi,Mφi〉 = 〈ψ,Mψ〉.
It is important to note that the effect of the measurement is that the projection operator Pi
is applied when the result λi is observed. The operator M does not describe the effect of the
measurement.
The formulas above reveal that no aspect of a measurement is altered if the vector describing
a quantum state is multiplied by a complex number of absolute value 1. Thus we can multiply
a state by eiθ without changing the state. This is called changing the phase. While the phase is
not important phase differences are very important. Multiplying a vector by a complex number
is a change of phase as well as a change in its length. Usually we normalize the state so that we
can read the results of measurements as probabilities. Given a vector the subspace spanned by it -
always one dimensional – is called a ray. Thus a state is really a ray rather than a vector. However,
it is customary to blur this distinction.
A.3 Some qubit algebra
Quantum computation is carried out with qubits the quantum analogues of bits. Just as a bit
has two possible values, a qubit is a two dimensional complex Hilbert space, in other words it is
(isomorphic to) the two dimensional complex vector space C2.
One works with a preferred basis, physically this corresponds to two distinguishable states, like
“spin up” and “spin down”. One writes |0〉, and |1〉 for its canonical basis, so that any vector ψ
can be written as α|0〉 + β|1〉 with α, β in C. Furthermore, C2 can be turned into a Hilbert space
with the following inner product:
〈α|0〉 + β|1〉, α′|0〉+ β′|1〉〉 := α⋆α′ + β⋆β′
where α⋆ is the complex conjugate of α. One then obtains the norm of a vector as:
‖ψ‖ := 〈ψ,ψ〉
2 = (α⋆α+ β⋆β)
Given V a finite set, one writes HV for the Hilbert space ⊗u∈VC2; the notation means an n-fold
tensor product of the C2 where n is the size of V . A vector in HV is said to be decomposable if
it can be written ⊗u∈V ψu for some ψu ∈ C2. Such decomposable vectors will be written ǫ in the
sequel. Decomposable vectors can be represented by a map from V to C2, and we will use both
notations depending on which is more convenient. As we have noted before there are some vectors
that are not decomposable.
As in the case of C2, there is a canonical basis for HV , sometimes also called the computational
basis, containing decomposable vectors ǫ such that for all v ∈ V , ǫ(v) = |0〉 or ǫ(v) = |1〉.
The inner product on HV , according to the general definition given above, is defined on decom-
posable vectors as:
〈ǫ, ǫ′〉 :=
v∈V 〈ǫ(v), ǫ′(v)〉
Note that all vectors in the computational basis are orthogonal and of norm 1. The vectors of norm
1 are usually called unit vectors; we always assume that states are described by unit vectors as
noted before.
Here are some common states that arise in quantum computation:
|0〉 = | ↑〉 =
, |1〉 = | ↓〉 =
, |+〉 =
, |−〉 =
It is easy to see that a linear operator is unitary if it preserves the inner product and hence the
norm. Thus unitaries can be viewed as maps from quantum states to quantum states.
Some particularly useful unitaries are the Pauli operators given by the following matrices in the
canonical basis of C2:
, Y =
, Z =
We note that all these operators are involutive, self-adjoint, and therefore unitaries. All these
matrices have determinant = −1. We will not discuss the geometric significance of these operators
here; their real importance in quantum mechanics comes from the fact that they can be used to
describe rotations, thus they are usually called the “Pauli spin matrices” by physicists.
Some basic algebra of these matrices are given below. First they all square to the identity.
X2 = Y 2 = Z2 = I.
The Pauli operators do not commute. We use the notation [A,B] for AB − BA, the commutator
of A and B. The commutator measures the extent to which two operators fail to commute: it is
customary to present the algebra of operators using it. One also uses the symbol {A,B} to stand
for AB + BA: it is called the anti-commutator. For the Pauli operators we have the following
commutators and anti-commutators :
XY = iZ Y X = −iZ [X,Y ] = 2iZ {X,Y } = 0
ZX = iY XZ = −iY [Z,X] = 2iY {Z,X} = 0
Y Z = iX ZY = −iX [Y,Z] = 2iX {Y,Z} = 0
Definition 19 Define the Pauli group, Pn, as the group consisting of tensor products of I, X, Y,
and Z on n qubits, with an overall phase of ±1 or ±i.
Given a group G the operation x 7→ g−1xg is called conjugation by g. These conjugations
give the effect of switching operators around. If G is a group and H is a subgroup of G then the
normalizer of H is another subgroup of G, say K, with the property that for all h ∈ H, k ∈ K we
have k−1hk in H.
The effect of conjugating measurements and other corrections by Pauli operators is a key part
of the rewrite rules described in the main text. They can be verified using the algebra given here.
A very important related group is called the Clifford group.
Definition 20 The Clifford group, Cn, is the group of unitary operators that leave the Pauli group
invariant under conjugation, i.e. it is the normalizer of the Pauli group viewed as a subgroup of the
unitary group.
The Clifford group on n qubits can be generated by the Hadamard transform, the controlled-X
(CNOT ) or controlled-Z (∧Z), and the single-qubit phase rotation:
H = 1√
, CNOT =
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
, ∧Z =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 −1
, P =
The importance of the Clifford group for quantum computation is that a computation consisting
of only Clifford operations on the computational basis followed by final Pauli measurements can be
efficiently simulated by a classical computer, this is the Gottesman-Knill theorem [Got97, NC00].
A.4 Density Matrices
In order to capture partial information about quantum systems one uses density matrices. Before
we describe density matrices we review some linear algebra in the bra-ket notation. Given a ket |ψ〉
the notation |ψ〉〈ψ| denotes the projection operator onto the one dimensional subspace spanned by
|ψ〉. To verify this note that
(|ψ〉〈ψ|)(|ψ〉 = |ψ〉‖ψ‖ = |ψ〉
(|ψ〉〈ψ|)(|φ〉) = |ψ〉〈ψ|φ〉 = 〈ψ|φ〉|ψ〉.
If |ψi〉 is an orthonormal basis for H the identity matrix is written
i |ψi〉〈ψi|. If Q is a linear
operator with eigenvalues qi and eigenvectors |qi〉, which form an orthonormal basis for H, we can
represent Q as
i qi|qi〉〈qi|. To see this, let |ψ〉 =
i ci|qi〉 then
Q|ψ〉 =
ciQ|qi〉 =
ciqi|qi〉
now using our representation for Q we calculate
Q|ψ〉 =
qi|qi〉〈qi|(|ψ〉) =
cjqi|qi〉〈qi|qj〉 =
ciqi|qi〉.
This is a version of the spectral theorem that we mentioned in the first subsection of this
appendix.
A state (i.e. a ray in H) is called a pure state. If a and b are distinct eigenvalues of some
observable A with corresponding eigenvectors |a〉 and |b〉 it is perfectly possible to prepare a state
of the form 1√
(|a〉 + |b〉). A measurement of A on such a state will yield either a or b each with
probability 1
. However, it is also possible that a mixture is prepared. That is to say instead of
a quantum superposition a classical stochastic mixture is prepared. In order to describe these we
will use density matrices.
For a system in a pure state |ψ〉, the density matrix is just the projection operator |ψ〉〈ψ|. If
we have an observable Q with eigenvalues qi – assumed nondegenerate for simplicity – then we can
expand |ψ〉 in terms of the eigenvectors by
|ψ〉 =
ci|qi〉.
Now the probability of observing qi when measuring Q in the state |ψ〉 is |〈qi|ψ〉|2. Recalling that
the identity is given by I =
j |qj〉〈qj | we get that
Prob(qi, |ψ〉) =
〈qi|ψ〉〈ψ|qj〉〈qj|qi〉
which after rearranging and using the definition of trace of an operator yields
Tr((|qi〉〈qi|)(|ψ〉〈ψ|)).
If as is typical we write ρψ for the density matrix and Pi for the projection operator onto the
subspace spanned by the eigenvector |qi〉 we get
Prob(qi, |ψ〉) = Tr(Piρ).
It is an easy calculation to show that the expectation value for Q in the state |ψ〉 is Tr(Qρ).
What if the state is not known completely? Suppose that we only know that a system is one of
several possible states |ψ1〉, . . . , |ψk〉 with probabilities p1, . . . , pk respectively. We define the density
matrix for such a state to be
pi|ψi〉〈ψi|.
The same formulas for the probability of observing a value qi , i.e. Tr(Piρ) and for the expectation
value of Q, i.e. Tr(Qρ) apply. One can check directly that a density matrix has the following two
properties.
Proposition 21 An operator ρ on H is a density matrix if and only if
• ρ has trace 1 and
• ρ is a positive operator, which means that it has only positive eigenvalues or, equivalently,
that for any x ∈ H we have 〈x, ρx〉 ≥ 0.
Furthermore, if ρ is a density operator, Tr(ρ2) ≤ 1 with equality if and only if ρ is a pure state
(i.e. a projection operator).
Suppose that we have a density matrix ρ describing a pure state of an n+m dimensional system.
Now suppose that an observer can only see the first n dimensions. The density matrix ξ describing
what he can see is contained by taking the partial trace over the m dimensions that the observer
cannot see. Doing this gives, in general, a nonpure state. Similarly a complementary observer who
sees only the m dimensions would construct her density matrix σ by taking the appropriate partial
trace. Taking these traces loses information; in fact, one cannot reconstruct ρ even from both ξ
and σ. Certainly the tensor product of ξ and σ does not give back ρ. This is due to the loss of the
cross-correlation information that was encoded in ρ but is not represented in either ξ or σ.
The axioms of quantum mechanics are easily stated in the language of density matrices. For
example, if evolution from time t1 to time t2 is described by the unitary transformation U and ρ
is the density matrix for time t1, then the evolved density matrix ρ
′ for time t2 is given by the
formula ρ′ = UρU †. Similarly, one can describe measurements represented by projective operators
in terms of density matrices [NC00, Pre98]. Thus if a projector P acts on a state |ψ〉 then the
result is P |ψ〉; the resulting transofrmation of density matrices is |ψ〉〈7→ |P |ψ〉〈P |. For a general
density matrix ρ we have ρ 7→ PρP , note that since P is self-adjoint we do not have to write P †.
A.5 Operations on Density matrices
What are the legitimate “physical” transformations on density matrices? Density matrices are
positive operators and they have trace either equal to 1 if we insist on normalizing them or bounded
by 1. These properties muct be preserved by any transformations on them.
We need first to define what it means for a vector to be positive. Any vector space V can be
equipped with a notion of positivity.
Definition 22 A subset C of V is called a cone if
• x ∈ C implies that for any positive α, αx ∈ C,
• x, y ∈ C implies that x+ y ∈ C and
• x and −x both in C means that x = 0.
We can define x ≥ 0 to mean x ∈ C and x ≥ y to mean x− y ∈ C.
Definition 23 An ordered vector space is just a vector space equipped with a cone.
It is easy to check the following explicitly.
Proposition 24 The collection of positive operators in the vector space of linear operators forms
a cone.
Now we can say what it means for a map to be a positive map.
Definition 25 Abstractly, L : (V,≤V ) → (W,≤W ) is a positive map if
∀v ∈ V. v ≥V 0 ⇒ L(v) ≥W 0.
It is important to not confuse “positive maps” and “positive operators.”
If we are transforming states (density matrices) then the legitimate transformations obviously
take density matrices to density matrices. They have to be positive maps considered as maps
between the appropriate ordered vector spaces. The appropriate ordered vector spaces are the
vector spaces of linear operators on H the Hilbert space of pure states.
Unfortunately the tensor product of two positive maps is not positive in general. We really
want this! If one can perform transformation T1 on density matrix ρ1 and transformation T2 on
density matrix ρ2 then it should be possible to regard ρ1 ⊗ ρ2 as a composite system and carry out
T1 ⊗ T2 on this system. We certainly want this if, say, T2 is the identity. But even when T2 is the
identity this may fail; the usual example is the transposition map, see, for example [NC00].
The remedy is to require the appropriate condition by fiat.
Definition 26 A completely positive map K is a positive map such that for every identity map
In : C
n → Cn the tensor product K ⊗ In is positive.
It is not hard to show that the tensor of completely positive maps is always a completely positive
map. This condition satisfies one of the requirements. We can insist that they preserve the bound
on the trace to satisfy the other requirement as well. However we would like an explicit way of
recognizing this.
The important result in this regard is the Kraus representation theorem [Cho75].
Theorem 7 (Kraus) The general form for a completely positive map E : B(H1) → B(H2) is
E(ρ) =
where the Am : H1 → H2.
Here B(H) is the Banach space of bounded linear operators on H. If, in addition, we require that
the trace of E(ρ) ≤ 1 then the Am will satisfy
A†mAm ≤ I.
The following term is common in the quantum computation literature.
Definition 27 A superoperator T is a linear map from BV to BU that is completely positive and
trace preserving.
	Introduction
	Measurement Patterns
	Commands
	Patterns
	Pattern combination
	The semantics of patterns
	Operational semantics
	Denotational semantics
	Short examples
	Compositionality of the Denotational Semantics
	Universality
	The measurement calculus
	The equations
	The rewrite rules
	Standardization
	Signal shifting
	Examples
	The no dependency theorems
	Other Models
	Phase Model
	Pauli model
	Teleportation
	Embedding
	Conclusion
	Background on Quantum Mechanics and Quantum Computation
	Linear Algebra for Quantum Mechanics
	Quantum Mechanics
	Some qubit algebra
	Density Matrices
	Operations on Density matrices

  Measurement-based quantum computation has emerged from the physics community
as a new approach to quantum computation where the notion of measurement is the
main driving force of computation. This is in contrast with the more
traditional circuit model which is based on unitary operations. Among
measurement-based quantum computation methods, the recently introduced one-way
quantum computer stands out as fundamental.
  We develop a rigorous mathematical model underlying the one-way quantum
computer and present a concrete syntax and operational semantics for programs,
which we call patterns, and an algebra of these patterns derived from a
denotational semantics. More importantly, we present a calculus for reasoning
locally and compositionally about these patterns.
  We present a rewrite theory and prove a general standardization theorem which
allows all patterns to be put in a semantically equivalent standard form.
Standardization has far-reaching consequences: a new physical architecture
based on performing all the entanglement in the beginning, parallelization by
exposing the dependency structure of measurements and expressiveness theorems.
  Furthermore we formalize several other measurement-based models:
Teleportation, Phase and Pauli models and present compositional embeddings of
them into and from the one-way model. This allows us to transfer all the theory
we develop for the one-way model to these models. This shows that the framework
we have developed has a general impact on measurement-based computation and is
not just particular to the one-way quantum computer.

Introduction
The emergence of quantum computation has changed our perspective on many fundamental aspects
of computing: the nature of information and how it flows, new algorithmic design strategies and
complexity classes and the very structure of computational models [NC00]. New challenges have
been raised in the physical implementation of quantum computers. This paper is a contribution to
a nascent discipline: quantum programming languages.
This is more than a search for convenient notation, it is an investigation into the structure,
scope and limits of quantum computation. The main issues are questions about how quantum
processes are defined, how quantum algorithms compose, how quantum resources are used and how
classical and quantum information interact.
Quantum computation emerged in the early 1980s with Feynman’s observations about the dif-
ficulty of simulating quantum systems on a classical computer. This hinted at the possibility of
turning around the issue and exploiting the power of quantum systems to perform computational
tasks more efficiently than was classically possible. In the mid 1980s Deutsch [Deu87] and later
http://arxiv.org/abs/0704.1263v1
Deutsch and Jozsa [DJ92] showed how to use superposition – the ability to produce linear combi-
nations of quantum states – to obtain computational speedup. This led to interest in algorithm
design and the complexity aspects of quantum computation by computer scientists. The most
dramatic results were Shor’s celebrated polytime factorization algorithm [Sho94] and Grover’s sub-
linear search algorithm [Gro98]. Remarkably one of the problematic aspects of quantum theory,
the presence of non-local correlation – an example of which is called “entanglement” – turned out
to be crucial for these algorithmic developments.
If efficient factorization is indeed possible in practice, then much of cryptography becomes
insecure as it is based on the difficulty of factorization. However, entanglement makes it possible
to design unconditionally secure key distribution [BB84, Eke91]. Furthermore, entanglement led
to the remarkable – but simple – protocol for transferring quantum states using only classical
communication [BBC+93]; this is the famous so-called “teleportation” protocol. There continues to
be tremendous activity in quantum cryptography, algorithmic design, complexity and information
theory. Parallel to all this work there has been intense interest from the physics community to
explore possible implementations, see, for example, [NC00] for a textbook account of some of these
ideas.
On the other hand, only recently has there been significant interest in quantum programming
languages; i.e. the development of formal syntax and semantics and the use of standard machinery
for reasoning about quantum information processing. The first quantum programming languages
were variations on imperative probabilistic languages and emphasized logic and program develop-
ment based on weakest preconditions [SZ00, Ö01]. The first definitive treatment of a quantum
programming language was the flowchart language of Selinger [Sel04b]. It was based on combining
classical control, as traditionally seen in flowcharts, with quantum data. It also gave a denotational
semantics based on completely positive linear maps. The notion of quantum weakest preconditions
was developed in [DP06]. Later people proposed languages based on quantum control [AG05]. The
search for a sensible notion of higher-type computation [SV05, vT04] continues, but is problem-
atic [Sel04c].
A related recent development is the work of Abramsky and Coecke [AC04, Coe04] where they
develop a categorical axiomatization of quantum mechanics. This can be used to verify the correct-
ness of quantum communication protocols. It is very interesting from a foundational point of view
and allows one to explore exactly what mathematical ingredients are required to carry out certain
quantum protocols. This has also led to work on a categorical quantum logic [AD04].
The study of quantum communication protocols has led to formalizations based on process
algebras [GN05, JL04] and to proposals to use model checking for verifying quantum protocols. A
survey and a complete list of references on this subject up to 2005 is available [Gay05].
These ideas have proven to be of great utility in the world of classical computation. The use of
logics, type systems, operational semantics, denotational semantics and semantic-based inference
mechanisms have led to notable advances such as: the use of model checking for verification,
reasoning compositionally about security protocols, refinement-based programming methodology
and flow analysis.
The present paper applies this paradigm to a very recent development: measurement-based
quantum computation. None of the cited research on quantum programming languages is aimed
at measurement-based computation. On the other hand, the work in the physics literature does
not clearly separate the conceptual layers of the subject from implementation issues. A formal
treatment is necessary to analyze the foundations of measurement-based computation.
So far the main framework to explore quantum computation has been the circuit model [Deu89],
based on unitary evolution. This is very useful for algorithmic development and complexity analysis
[BV97]. There are other models such as quantum Turing machines [Deu85] and quantum cellular
automata [Wat95, vD96, DS96, SW04]. Although they are all proved to be equivalent from the
point of view of expressive power, there is no agreement on what is the canonical model for exposing
the key aspects of quantum computation.
Recently physicists have introduced novel ideas based on the use of measurement and entangle-
ment to perform computation [GC99, RB01, RBB03, Nie03]. This is very different from the circuit
model where measurement is done only at the end to extract classical output. In measurement-based
computation the main operation to manipulate information and control computation is measure-
ment. This is surprising because measurement creates indeterminacy, yet it is used to express
deterministic computation defined by a unitary evolution.
The idea of computing based on measurements emerged from the teleportation protocol [BBC+93].
The goal of this protocol is for an agent to transmit an unknown qubit to a remote agent without
actually sending the qubit. This protocol works by having the two parties share a maximally en-
tangled state called a Bell pair. The parties perform local operations – measurements and unitaries
– and communicate only classical bits. Remarkably, from this classical information the second
party can reconstruct the unknown quantum state. In fact one can actually use this to com-
pute via teleportation by choosing an appropriate measurement [GC99]. This is the key idea of
measurement-based computation.
It turns out that the above method of computing is actually universal. This was first shown
by Gottesman and Chuang [GC99] who used two-qubit measurements and given Bell pairs. Later
Nielsen [Nie03] showed that one could do this with only 4-qubit measurements with no prior Bell
pairs, however this works only probabilistically. Leung [Leu04] improved this to two qubits, but her
method also works only probabilistically. Later Perdrix and Jorrand [Per03, PJ04] gave the minimal
set measurements to perform universal quantum computing – but still in the probabilistic setting
– and introduced the state-transfer and measurement-based quantum Turing machine. Finally
the one-way computer was invented by Raussendorf and Briegel [RB01, RB02] which used only
single-qubit measurements with a particular multi-party entangled state, the cluster state.
More precisely, a computation consists of a phase in which a collection of qubits are set up in a
standard entangled state. Then measurements are applied to individual qubits and the outcomes of
the measurements may be used to determine further measurements. Finally – again depending on
measurement outcomes – local unitary operators, called corrections, are applied to some qubits; this
allows the elimination of the indeterminacy introduced by measurements. The phrase “one-way”
is used to emphasize that the computation is driven by irreversible measurements.
There are at least two reasons to take measurement-based models seriously: one conceptual
and one pragmatic. The main pragmatic reason is that the one-way model is believed by physicists
to lend itself to easier implementations [Nie04, CAJ05, BR05, TPKV04, TPKV06, WkJRR+05,
KPA06, BES05, CCWD06, BBFM06]. Physicists have investigated various properties of the cluster
state and have accrued evidence that the physical implementation is scalable and robust against
decoherence [Sch03, HEB04, DAB03, dNDM04b, dNDM04a, MP04, GHW05, HDB05, DHN06].
Conceptually the measurement-based model highlights the role of entanglement and separates the
quantum and classical aspects of computation; thus it clarifies, in particular, the interplay between
classical control and the quantum evolution process.
Our approach to understanding the structural features of measurement-based computation is to
develop a formal calculus. One can think of this as an “assembly language” for measurement-based
computation. Ours is the first programming framework specifically based on the one-way model. We
first develop a notation for such classically correlated sequences of entanglements, measurements,
and local corrections. Computations are organized in patterns1, and we give a careful treatment
of the composition and tensor product (parallel composition) of patterns. We show next that such
pattern combinations reflect the corresponding combinations of unitary operators. An easy proof
of universality follows.
So far, this is primarily a clarification of what was already known from the series of papers
introducing and investigating the properties of the one-way model [RB01, RB02, RBB03]. However,
we work here with an extended notion of pattern, where inputs and outputs may overlap in any
way one wants them to, and this results in more efficient – in the sense of using fewer qubits –
implementations of unitaries. Specifically, our universal set consists of patterns using only 2 qubits.
From it we obtain a 3 qubit realization of the Rz rotations and a 14 qubit realization for the
controlled-U family: a significant reduction over the hitherto known implementations.
The main point of this paper is to introduce a calculus of local equations over patterns that
exploits some special algebraic properties of the entanglement, measurement and correction op-
erators. More precisely, we use the fact that that 1-qubit XY measurements are closed under
conjugation by Pauli operators and the entanglement command belongs to the normalizer of the
Pauli group; these terms are explained in the appendix. We show that this calculus is sound in that
it preserves the interpretation of patterns. Most importantly, we derive from it a simple algorithm
by which any general pattern can be put into a standard form where entanglement is done first,
then measurements, then corrections. We call this standardization.
The consequences of the existence of such a procedure are far-reaching. Since entangling comes
first, one can prepare the entire entangled state needed during the computation right at the start:
one never has to do “on the fly” entanglements. Furthermore, the rewriting of a pattern to stan-
dard form reveals parallelism in the pattern computation. In a general pattern, one is forced to
compute sequentially and to strictly obey the command sequence, whereas, after standardization,
the dependency structure is relaxed, resulting in lower computational depth complexity. Last, the
existence of a standard form for any pattern also has interesting corollaries beyond implementation
and complexity matters, as it follows from it that patterns using no dependencies, or using only the
restricted class of Pauli measurements, can only realize a unitary belonging to the Clifford group,
and hence can be efficiently simulated by a classical computer [Got97].
As we have noted before, there are other methods for measurement-based quantum comput-
ing: the teleportation technique based on two-qubit measurements and the state-transfer approach
based on single qubit measurements and incomplete two-qubit measurements. We will analyze the
teleportation model and its relation to the one-way model. We will show how our calculus can be
smoothly extended to cover this case as well as new models that we introduce in this paper. We
get several benefits from our treatment. We get a workable syntax for handling the dependencies of
operators on previous measurement outcomes just by mimicking the one obtained in the one-way
model. This has never been done before for the teleportation model. Furthermore, we can use this
embedding to obtain a standardization procedure for the models. Finally these extended calculi
can be compositionally embedded back in the original one-way model. This clarifies the relation
between different measurement-based models and shows that the one-way model of Raussendorf
1We use the word “pattern” rather than “program”, because this corresponds to the commonly used terminology
in the physics literature.
and Briegel is the canonical one.
This paper develops the one-way model ab initio but certain concepts that the reader may be
unfamiliar with: qubits, unitaries, measurements, Pauli operators and the Clifford group are in
an appendix. These are also readily accessible through the very thorough book of Nielsen and
Chuang [NC00].
In the next section we define the basic model, followed by its operational and denotational
semantics, for completeness a simple proof of universality is given in section 4, this has appeared
earlier in the physics literature [DKP05], in section 5 we develop the rewrite theory and prove the
fundamental standardization theorem. In section 6 we develop several examples that illustrate the
use of our calculus in designing efficient patterns. In section 7 we prove some theorems about the
expressive power of the calculus in the absence of adaptive measurements. In section 8 we discuss
other measurement-based models and their compositional embedding to and from the one-way
model. In section 9 we discuss further directions and some more related work. In the appendix we
review basic notions of quantum mechanics and quantum computation.
2 Measurement Patterns
We first develop a notation for 1-qubit measurement based computations. The basic commands
one can use in a pattern are:
• 1-qubit auxiliary preparation Ni
• 2-qubit entanglement operators Eij
• 1-qubit measurements Mαi
• and 1-qubit Pauli operators corrections Xi and Zi
The indices i, j represent the qubits on which each of these operations apply, and α is a
parameter in [0, 2π]. Expressions involving angles are always evaluated modulo 2π. These types of
command will be referred to as N , E, M and C. Sequences of such commands, together with two
distinguished – possibly overlapping – sets of qubits corresponding to inputs and outputs, will be
called measurement patterns, or simply patterns. These patterns can be combined by composition
and tensor product.
Importantly, corrections and measurements are allowed to depend on previous measurement
outcomes. We shall prove later that patterns without these classical dependencies can only realize
unitaries that are in the Clifford group. Thus, dependencies are crucial if one wants to define a
universal computing model; that is to say, a model where all unitaries over ⊗nC2 can be realized.
It is also crucial to develop a notation that will handle these dependencies. This is what we do
2.1 Commands
Preparation Ni prepares qubit i in state |+〉i. The entanglement commands are defined as Eij :=
∧Zij (controlled-Z), while the correction commands are the Pauli operators Xi and Zi.
Measurement Mαi is defined by orthogonal projections on
|+α〉 := 1√
(|0〉+ eiα|1〉)
|−α〉 := 1√
(|0〉 − eiα|1〉)
followed by a trace-out operator. The parameter α ∈ [0, 2π] is called the angle of the mea-
surement. For α = 0, α = π
, one obtains the X and Y Pauli measurements. Operationally,
measurements will be understood as destructive measurements, consuming their qubit. The out-
come of a measurement done at qubit i will be denoted by si ∈ Z2. Since one only deals here with
patterns where qubits are measured at most once (see condition (D1) below), this is unambiguous.
We take the specific convention that si = 0 if under the corresponding measurement the state
collapses to |+α〉, and si = 1 if to |−α〉.
Outcomes can be summed together resulting in expressions of the form s =
i∈I si which we
call signals, and where the summation is understood as being done in Z2. We define the domain
of a signal as the set of qubits on which it depends.
As we have said before, both corrections and measurements may depend on signals. Depen-
dent corrections will be written Xsi and Z
i and dependent measurements will be written
t[Mαi ]
where s, t ∈ Z2 and α ∈ [0, 2π]. The meaning of dependencies for corrections is straightforward:
X0i = Z
i = I, no correction is applied, while X
i = Xi and Z
i = Zi. In the case of dependent
measurements, the measurement angle will depend on s, t and α as follows:
t[Mαi ]
s := M
(−1)sα+tπ
i (1)
so that, depending on the parities of s and t, one may have to modify the α to one of −α, α + π
and −α+ π. These modifications correspond to conjugations of measurements under X and Z:
i Xi = M
i (2)
i Zi = M
i (3)
accordingly, we will refer to them as the X and Z-actions. Note that these two actions commute,
since −α+ π = −α− π up to 2π, and hence the order in which one applies them does not matter.
As we will see later, relations (2) and (3) are key to the propagation of dependent corrections,
and to obtaining patterns in the standard entanglement, measurement and correction form. Since
the measurements considered here are destructive, the above equations actually simplify to
Mαi Xi = M
i (4)
Mαi Zi = M
i (5)
Another point worth noticing is that the domain of the signals of a dependent command, be it a
measurement or a correction, represents the set of measurements which one has to do before one
can determine the actual value of the command.
We have completed our catalog of basic commands, including dependent ones, and we turn
now to the definition of measurement patterns. For convenient reference, the language syntax is
summarized in Figure 1.
2.2 Patterns
Definition 1 Patterns consists of three finite sets V , I, O, together with two injective maps ι :
I → V and o : O → V and a finite sequence of commands An . . . A1, read from right to left, applying
to qubits in V in that order, i.e. A1 first and An last, such that:
(D0) no command depends on an outcome not yet measured;
S := 0, 1, si, S + S Signals
A := Ni Preparations
Eij Entanglements
t[Mαi ]
s Measurements
Xsi , Z
i Corrections
Figure 1: 1-qubit based measurement language syntax
(D1) no command acts on a qubit already measured;
(D2) no command acts on a qubit not yet prepared, unless it is an input qubit;
(D3) a qubit i is measured if and only if i is not an output.
The set V is called the pattern computation space, and we write HV for the associated quantum
state space ⊗i∈V C2. To ease notation, we will omit the maps ι and o, and write simply I, O instead
of ι(I) and o(O). Note, however, that these maps are useful to define classical manipulations of
the quantum states, such as permutations of the qubits. The sets I, O are called respectively the
pattern inputs and outputs, and we write HI , and HO for the associated quantum state spaces. The
sequence An . . . A1 is called the pattern command sequence, while the triple (V, I,O) is called the
pattern type.
To run a pattern, one prepares the input qubits in some input state ψ ∈ HI , while the non-input
qubits are all set to the |+〉 state, then the commands are executed in sequence, and finally the result
of the pattern computation is read back from outputs as some φ ∈ HO. Clearly, for this procedure
to succeed, we had to impose the (D0), (D1), (D2) and (D3) conditions. Indeed if (D0) fails, then
at some point of the computation, one will want to execute a command which depends on outcomes
that are not known yet. Likewise, if (D1) fails, one will try to apply a command on a qubit that
has been consumed by a measurement (recall that we use destructive measurements). Similarly, if
(D2) fails, one will try to apply a command on a non-existent qubit. Condition (D3) is there to
make sure that the final state belongs to the output space HO, i.e., that all non-output qubits, and
only non-output qubits, will have been consumed by a measurement when the computation ends.
We write (D) for the conjunction of our definiteness conditions (D0), (D1), (D2) and (D3).
Whether a given pattern satisfies (D) or not is statically verifiable on the pattern command se-
quence. We could have imposed a simple type system to enforce these constraints but, in the
interests of notational simplicity, we chose not to do so.
Here is a concrete example:
H := ({1, 2}, {1}, {2},Xs12 M01E12N2)
with computation space {1, 2}, inputs {1}, and outputs {2}. To run H, one first prepares the first
qubit in some input state ψ, and the second qubit in state |+〉, then these are entangled to obtain
∧Z12(ψ1 ⊗ |+〉2). Once this is done, the first qubit is measured in the |+〉, |−〉 basis. Finally an X
correction is applied on the output qubit, if the measurement outcome was s1 = 1. We will do this
calculation in detail later, and prove that this pattern implements the Hadamard operator H.
In general, a given pattern may use auxiliary qubits that are neither input nor output qubits.
Usually one tries to use as few such qubits as possible, since these contribute to the space complexity
of the computation.
A last thing to note is that one does not require inputs and outputs to be disjoint subsets of
V . This, seemingly innocuous, additional flexibility is actually quite useful to give parsimonious
implementations of unitaries [DKP05]. While the restriction to disjoint inputs and outputs is
unnecessary, it has been discussed whether imposing it results in patterns that are easier to realize
physically. Recent work [HEB04, BR05, CAJ05] however, seems to indicate it is not the case.
2.3 Pattern combination
We are interested in how one can combine patterns in order to obtain bigger ones.
The first way to combine patterns is by composing them. Two patterns P1 and P2 may be
composed if V1 ∩ V2 = O1 = I2. Provided that P1 has as many outputs as P2 has inputs, by
renaming the pattern qubits, one can always make them composable.
Definition 2 The composite pattern P2P1 is defined as:
— V := V1 ∪ V2, I = I1, O = O2,
— commands are concatenated.
The other way of combining patterns is to tensor them. Two patterns P1 and P2 may be tensored
if V1 ∩ V2 = ∅. Again one can always meet this condition by renaming qubits in a way that these
sets are made disjoint.
Definition 3 The tensor pattern P1 ⊗ P2 is defined as:
— V = V1 ∪ V2, I = I1 ∪ I2, and O = O1 ∪O2,
— commands are concatenated.
In contrast to the composition case, all the unions involved here are disjoint. Therefore commands
from distinct patterns freely commute, since they apply to disjoint qubits, and when we say that
commands have to be concatenated, this is only for definiteness. It is routine to verify that the
definiteness conditions (D) are preserved under composition and tensor product.
Before turning to this matter, we need a clean definition of what it means for a pattern to
implement or to realize a unitary operator, together with a proof that the way one can combine
patterns is reflected in their interpretations. This is key to our proof of universality.
3 The semantics of patterns
In this section we give a formal operational semantics for the pattern language as a probabilistic
labeled transition system. We define deterministic patterns and thereafter concentrate on them.
We show that deterministic patterns compose. We give a denotational semantics of deterministic
patterns; from the construction it will be clear that these two semantics are equivalent.
Besides quantum states, which are non-zero vectors in some Hilbert space HV , one needs a
classical state recording the outcomes of the successive measurements one does in a pattern. If we
let V stand for the finite set of qubits that are still active (i.e. not yet measured) and W stands
for the set of qubits that have been measured (i.e. they are now just classical bits recording the
measurement outcomes), it is natural to define the computation state space as:
S := ΣV,WHV × ZW2 .
In other words the computation states form a V,W -indexed family of pairs2 q, Γ, where q is a
quantum state from HV and Γ is a map from some W to the outcome space Z2. We call this
classical component Γ an outcome map, and denote by ∅ the empty outcome map in Z∅2 . We will
treat these states as pairs unless it becomes important to show how V and W are altered during a
computation, as happens during a measurement.
3.1 Operational semantics
We need some preliminary notation. For any signal s and classical state Γ ∈ ZW2 , such that the
domain of s is included in W , we take sΓ to be the value of s given by the outcome map Γ. That is
to say, if s =
I si, then sΓ :=
I Γ(i) where the sum is taken in Z2. Also if Γ ∈ ZW2 , and x ∈ Z2,
we define:
Γ[x/i](i) = x, Γ[x/i](j) = Γ(j) for j 6= i
which is a map in Z
W∪{i}
We may now view each of our commands as acting on the state space S, we have suppressed V
and W in the first 4 commands:
Ni−→ q ⊗ |+〉i,Γ
Eij−→ ∧Zijq,Γ
i−→ XsΓi q,Γ
i−→ ZsΓi q,Γ
V ∪ {i},W, q,Γ
−→ V,W ∪ {i}, 〈+αΓ |iq,Γ[0/i]
V ∪ {i},W, q,Γ
−→ V,W ∪ {i}, 〈−αΓ |iq,Γ[1/i]
where αΓ = (−1)sΓα + tΓπ following equation (1). Note how the measurement moves an index
from V to W ; a qubit once measured cannot be neasured again. Suppose q ∈ HV , for the above
relations to be defined, one needs the indices i, j on which the various command apply to be in V .
One also needs Γ to contain the domains of s and t, so that sΓ and tΓ are well-defined. This will
always be the case during the run of a pattern because of condition (D).
All commands except measurements are deterministic and only modify the quantum part of
the state. The measurement actions on S are not deterministic, so that these are actually binary
relations on S, and modify both the quantum and classical parts of the state. The usual convention
has it that when one does a measurement the resulting state is renormalized and the probabilities
are associated with the transition. We do not adhere to this convention here, instead we leave the
states unnormalized. The reason for this choice of convention is that this way, the probability of
reaching a given state can be read off its norm, and the overall treatment is simpler. As we will
show later, all the patterns implementing unitary operators will have the same probability for all
the branches and hence we will not need to carry these probabilities explicitly.
2These are actually quadruples of the form (V,W, q,Γ), unless necessary we will suppress the V and the W .
We introduce an additional command called signal shifting :
i−→ q,Γ[Γ(i) + sΓ/i]
It consists in shifting the measurement outcome at i by the amount sΓ. Note that the Z-action leaves
measurements globally invariant, in the sense that |+α+π〉, |−α+π〉 = |−α〉, |+α〉. Thus changing α
to α+ π amounts to swapping the outcomes of the measurements, and one has:
t[Mαi ]
s = Sti
0[Mαi ]
s (6)
and signal shifting allows to dispose of the Z action of a measurement, resulting sometimes in
convenient optimizations of standard forms.
3.2 Denotational semantics
Let P be a pattern with computation space V , inputs I, outputs O and command sequence
An . . . A1. To execute a pattern, one starts with some input state q in HI , together with the
empty outcome map ∅. The input state q is then tensored with as many |+〉s as there are non-
inputs in V (the N commands), so as to obtain a state in the full space HV . Then E, M and
C commands in P are applied in sequence from right to left. We can summarize the situation as
follows:
// HO
HI × Z∅2
prep // HV × Z∅2
A1...An // HO × ZVrO2
If m is the number of measurements, which is also the number of non outputs, then the run may
follow 2m different branches. Each branch is associated with a unique binary string s of length m,
representing the classical outcomes of the measurements along that branch, and a unique branch
map As representing the linear transformation from HI to HO along that branch. This map is
obtained from the operational semantics via the sequence (qi,Γi) with 1 ≤ i ≤ n+ 1, such that:
q1,Γ1 = q ⊗ |+ . . .+〉,∅
qn+1 = q
′ 6= 0
and for all i ≤ n : qi,Γi
Ai−→ qi+1,Γi+1.
Definition 4 A pattern P realizes a map on density matrices ρ given by ρ 7→
s(ρ)As. We
write [[P]] for the map realized by P.
Proposition 5 Each pattern realizes a completely positive trace preserving map.
Proof. Later on we will show that every pattern can be put in a semantically equivalent form
where all the preparations and entanglements appear first, followed by a sequence of measurements
and finally local Pauli corrections. Hence branch maps decompose as As = CsΠsU , where Cs is a
unitary map over HO collecting all corrections on outputs, Πs is a projection from HV to HO rep-
resenting the particular measurements performed along the branch, and U is a unitary embedding
from HI to HV collecting the branch preparations, and entanglements. Note that U is the same on
all branches. Therefore,
sAs =
U †Π†sC
sCsΠsU
U †Π†sΠsU
= U †(
= U †U = I
where we have used the fact that Cs is unitary, Πs is a projection and U is independent of
the branches and is also unitary. Therefore the map T (ρ) :=
As(ρ)A
s is a trace-preserving
completely-positive map (cptp-map), explicitly given as a Kraus decomposition. ✷
Hence the denotational semantics of a pattern is a cptp-map. In our denotational semantics we
view the pattern as defining a map from the input qubits to the output qubits. We do not explicitly
represent the result of measuring the final qubits; these may be of interest in some cases. Techniques
for dealing with classical output explicitly are given by Selinger [Sel04b] and Unruh [Unr05].
Definition 6 A pattern is said to be deterministic if it realizes a cptp-map that sends pure states
to pure states. A pattern is said to be strongly deterministic when branch maps are equal.
This is equivalent to saying that for a deterministic pattern branch maps are proportional, that
is to say, for all q ∈ HI and all s1, s2 ∈ Zn2 , As1(q) and As2(q) differ only up to a scalar. For a
strongly deterministic pattern we have for all s1, s2 ∈ Zn2 , As1 = As2 .
Proposition 7 If a pattern is strongly deterministic, then it realizes a unitary embedding.
Proof. Define T to be the map realized by the pattern. We have T =
sAs. Since the pattern
in strongly deterministic all the branch maps are the same. Define A to be 2n/2As, then A must
be a unitary embedding, because A†A = I. ✷
3.3 Short examples
For the rest of paper we assume that all the non-input qubits are prepared in the state |+〉 and
hence for simplicity we omit the preparation commands NIc .
First we give a quick example of a deterministic pattern that has branches with different proba-
bilities. Its type is V = {1, 2}, I = O = {1}, and its command sequence is Mα2 . Therefore, starting
with input q, one gets two branches:
q ⊗ |+〉,∅
(1 + e−iα)q,∅[0/2]
(1− e−iα)q,∅[1/2]
Thus this pattern is indeed deterministic, and implements the identity up to a global phase, and
yet the two branches have respective probabilities (1 + cosα)/2 and (1 − cosα)/2, which are not
equal in general and hence this pattern is not strongly deterministic.
There is an interesting variation on this first example. The pattern of interest, call it T , has
the same type as above with command sequence X
2E12. Again, T is deterministic, but not
strongly deterministic: the branches have different probabilities, as in the preceding example. Now,
however, these probabilities may depend on the input. The associated transformation is a cptp-map,
T (ρ) := AρA† +BρB† with:
, B :=
One has A†A+B†B = I, so T is indeed a completely positive and trace-preserving linear map and
T (|ψ〉〈ψ|) = 〈ψ,ψ〉|0〉〈0| and clearly for no unitary U does one have T (ρ) := UρU †.
For our final example, we return to the pattern H, already defined above. Consider the pattern
with the same qubit space {1, 2}, and the same inputs and outputs I = {1}, O = {2}, as H, but
with a shorter command sequence namely M01E12. Starting with input q = (a|0〉 + b|1〉)|+〉, one
has two computation branches, branching at M01 :
(a|0〉+ b|1〉)|+〉,∅ E12−→ 1√
(a|00〉 + a|01〉+ b|10〉 − b|11〉),∅
((a+ b)|0〉 + (a− b)|1〉),∅[0/1]
((a− b)|0〉 + (a+ b)|1〉),∅[1/1]
and since ‖a+ b‖2 + ‖a− b‖2 = 2(‖a‖2 + ‖b‖2), both transitions happen with equal probabilities 1
Both branches end up with non proportional outputs, so the pattern is not deterministic. However,
if one applies the local correction X2 on either of the branches’ ends, both outputs will be made to
coincide. If we choose to let the correction apply to the second branch, we obtain the pattern H,
already defined. We have just proved H = UH, that is to say H realizes the Hadamard operator.
3.4 Compositionality of the Denotational Semantics
With our definitions in place, we will show that the denotational semantics is compositional.
Theorem 1 For two patterns P1 and P2 we have [[P1P2]] = [[P2]][[P1]] and [[P1⊗P2]] = [[P2]]⊗ [[P1]].
Proof. Recall that two patterns P1, P2 may be combined by composition provided P1 has as many
outputs as P2 has inputs. Suppose this is the case, and suppose further that P1 and P2 respectively
realize some cptp-maps T1 and T2. We need to show that the composite pattern P2P1 realizes T2T1.
Indeed, the two diagrams representing branches in P1 and P2:
// HO1 HI2
// HO2
HI1 × Z
p1// HV1 × Z
// HO1 × Z
V1rO1
HI2 × Z
p2// HV2 × Z
// HO2 × Z
V2rO2
can be pasted together, since O1 = I2, and HO1 = HI2 . But then, it is enough to notice 1) that
preparation steps p2 in P2 commute with all actions in P1 since they apply on disjoint sets of qubits,
and 2) that no action taken in P2 depends on the measurements outcomes in P1. It follows that
the pasted diagram describes the same branches as does the one associated to the composite P2P1.
A similar argument applies to the case of a tensor combination, and one has that P2 ⊗ P1
realizes T2 ⊗ T1. ✷
If one wanted to give a categorical treatment3 one can define a category where the objects are
finite sets representing the input and output qubits and the morphisms are the patterns. This is
clearly a monoidal category with our tensor operation as the monoidal structure. One can show that
the denotational semantics gives a monoidal functor into the category of superoperators or into any
suitably enriched strongly compact closed category [AC04] or dagger category [Sel05a]. It would be
very interesting to explore exactly what additional categorical structures are required to interpret
the measurement calculus presented below. Duncan Ross[Dun05] has skectched a polycategorical
presentation of our measurement calculus.
4 Universality
Define the two following patterns on V = {1, 2}:
J (α) := Xs12 M
1 E12 (7)
∧Z := E12 (8)
with I = {1}, O = {2} in the first pattern, and I = O = {1, 2} in the second. Note that the second
pattern does have overlapping inputs and outputs.
Proposition 8 The patterns J (α) and ∧Z are universal.
Proof. First, we claim J (α) and ∧Z respectively realize J(α) and ∧Z, with:
J(α) := 1√
1 eiα
1 −eiα
We have already seen in our example that J (0) = H implements H = J(0), thus we already know
this in the particular case where α = 0. The general case follows by the same kind of computation.4
The case of ∧Z is obvious.
Second, we know that these unitaries form a universal set for ⊗nC2 [DKP05]. Therefore, from
the preceding section, we infer that combining the corresponding patterns will generate patterns
realizing any unitary in ⊗nC2. ✷
These patterns are indeed among the simplest possible. As a consequence, in the section devoted
to examples, we will find that our implementations often have lower space complexity than the
traditional implementations.
Remarkably, in our set of generators, one finds a single measurement and a single dependency,
which occurs in the correction phase of J (α). Clearly one needs at least one measurement, since
patterns without measurements can only implement unitaries in the Clifford group. It is also true
that dependencies are needed for universality, but we have to wait for the development of the
measurement calculus in the next section to give a proof of this fact.
3The rest of the paragraph can be omitted without loss of continuity.
4Equivalently, this follows from J(α) = HP (α), with P (α) =
0 eiα
1 E12 = X
1P (α)1E12 = HP (α)1.
5 The measurement calculus
We turn to the next important matter of the paper, namely standardization. The idea is quite
simple. It is enough to provide local pattern-rewrite rules pushing Es to the beginning of the
pattern and Cs to the end. The crucial point is to justify using the equations as rewrite rules.
5.1 The equations
The expressions appearing as commands are all linear operators on Hilbert space. At first glance,
the appropriate equality between commands is equality as operators. For the deterministic com-
mands, the equality that we consider is indeed equality as operators. This equality implies equality
in the denotational semantics. However, for measurement commands one needs a stricter definition
for equality in order to be able to apply them as rewriting rules. Essentially we have to take into
the account the effect of different branches that might result from the measurement process. The
precise definition is below.
Definition 9 Consider two patterns P and P ′ we define P = P ′ if and only if for any branch s,
we have APs = A
s , where A
s and A
s are the branch map As defined in Section 3.2.
The first set of equations gives the means to propagate local Pauli corrections through the
entangling operator Eij.
i = X
jEij (9)
j = X
iEij (10)
i = Z
iEij (11)
j = Z
jEij (12)
These equations are easy to verify and are natural since Eij belongs to the Clifford group, and
therefore maps under conjugation the Pauli group to itself. Note that, despite the symmetry of the
Eij operator qua operator, we have to consider all the cases, since the rewrite system defined below
does not allow one to rewrite Eij to Eji. If we did allow this the reqrite process could loop forever.
A second set of equations allows one to push corrections through measurements acting on the
same qubit. Again there are two cases:
t[Mαi ]
sXri =
t[Mαi ]
s+r (13)
t[Mαi ]
sZri =
t+r[Mαi ]
s (14)
These equations follow easily from equations (4) and (5). They express the fact that the measure-
ments Mαi are closed under conjugation by the Pauli group, very much like equations (9),(10),(11)
and (12) express the fact that the Pauli group is closed under conjugation by the entanglements
Eij .
Define the following convenient abbreviations:
[Mαi ]
s := 0[Mαi ]
s, t[Mαi ] :=
t[Mαi ]
0, Mαi :=
0[Mαi ]
Mxi :=M
i , M
i :=M
Particular cases of the equations above are:
Mxi X
i = M
i = [M
s = s[M
i ] = M
The first equation, follows from the fact that −0 = 0, so the X action on Mxi is trivial; the second
equation, is because −π
is equal π
+ π modulo 2π, and therefore the X and Z actions coincide on
i . So we obtain the following:
t[Mxi ]
s = t[Mxi ] (15)
s = s+t[M
i ] (16)
which we will use later to prove that patterns with measurements of the form Mx and My may
only realize unitaries in the Clifford group.
5.2 The rewrite rules
We now define a set of rewrite rules, obtained by orienting the equations above5:
i ⇒ Xsi ZsjEij EX
j ⇒ XsjZsiEij EX
i ⇒ ZsiEij EZ
j ⇒ ZsjEij EZ
t[Mαi ]
sXri ⇒ t[Mαi ]s+r MX
t[Mαi ]
sZri ⇒ r+t[Mαi ]s MZ
to which we need to add the free commutation rules, obtained when commands operate on disjoint
sets of qubits:
EijA~k ⇒ A~kEij where A is not an entanglement
i ⇒ XsiA~k where A is not a correction
i ⇒ ZsiA~k where A is not a correction
where ~k represent the qubits acted upon by command A, and are supposed to be distinct from i
and j. Clearly these rules could be reversed since they hold as equations but we are orienting them
this way in order to obtain termination.
Condition (D) is easily seen to be preserved under rewriting.
Under rewriting, the computation space, inputs and outputs remain the same, and so do the
entanglement commands. Measurements might be modified, but there is still the same number
of them, and they still act on the same qubits. The only induced modifications concern local
corrections and dependencies. If there was no dependency at the start, none will be created in the
rewriting process.
In order to obtain rewrite rules, it was essential that the entangling command (∧Z) belongs
to the normalizer of the Pauli group. The point is that the Pauli operators are the correction
operators and they can be dependent, thus we can commute the entangling commands to the
beginning without inheriting any dependency. Therefore the entanglement resource can indeed be
prepared at the outset of the computation.
5Recall that patterns are executed from right to left.
5.3 Standardization
Write P ⇒ P ′, respectively P ⇒⋆ P ′, if both patterns have the same type, and one obtains the
command sequence of P ′ from the command sequence of P by applying one, respectively any
number, of the rewrite rules of the previous section. We say that P is standard if for no P ′, P ⇒ P ′
and the procedure of writing a pattern to standard form is called standardization6.
One of the most important results about the rewrite system is that it has the desirable properties
of determinacy (confluence) and termination (standardization). In other words, we will show that
for all P, there exists a unique standard P ′, such that P ⇒⋆ P ′. It is, of course, crucial that the
standardization process leaves the semantics of patterns invariant. This is the subject of the next
simple, but important, proposition,
Proposition 10 Whenever P ⇒⋆ P ′, [[P]] = [[P ′]].
Proof. It is enough to prove it when P ⇒ P ′. The first group of rewrites has been proved to be
sound in the preceding subsections, while the free commutation rules are obviously sound. ✷
We now begin the main proof of this section. First, we prove termination.
Theorem 2 (Termination) All rewriting sequences beginning with a pattern P terminate after
finitely many steps. For our rewrite system, this implies that for all P there exist finitely many P ′
such that P ⇒⋆ P ′ where the P ′ are standard.
Proof. Suppose P has command sequence An . . . A1; so the number of commands is n. Let
e ≤ n be the number of E commands in P. As we have noted earlier, this number is invariant
under ⇒. Moreover E commands in P can be ordered by increasing depth, read from right to left,
and this order, written <E, is also invariant, since EE commutations are forbidden explicitly in
the free commutation rules.
Define the following depth function d on E and C commands in P:
d(Ai) =
i if Ai = Ejk
n− i if Ai = Cj
Define further the following sequence of length e, dE(P)(i) is the depth of the E-command of rank
i according to <E. By construction this sequence is strictly increasing. Finally, we define the
measure m(P) := (dE(P), dC (P)) with:
dC(P) =
C∈P d(C)
We claim the measure we just defined decreases lexicographically under rewriting, in other words
P ⇒ P ′ implies m(P) > m(P ′), where < is the lexicographic ordering on Ne+1.
To clarify these definitions, consider the following example. Suppose P’s command sequence is
of the form EXZE, then e = 2, dE(P) = (1, 4), and m(P) = (1, 4, 3). For the command sequence
EEX we get that e = 2, dE(P) = (2, 3) and m(P) = (2, 3, 2). Now, if one considers the rewrite
EEX ⇒ EXZE, the measure of the left hand side is (2, 3, 2), while the measure of the right hand
side, as said, is (1, 4, 3), and indeed (2, 3, 2) > (1, 4, 3). Intuitively the reason is clear: the Cs are
being pushed to the left, thus decreasing the depths of Es, and concomitantly, the value of dE .
6We use the word “standardization” instead of the more usual “normalization” in order not to cause terminological
confusion with the physicists’ notion of normalization.
Let us now consider all cases starting with an EC rewrite. Suppose the E command under
rewrite has depth d and rank i in the order <E. Then all Es of smaller rank have same depth in
the right hand side, while E has now depth d − 1 and still rank i. So the right hand side has a
strictly smaller measure. Note that when C = X, because of the creation of a Z (see the example
above), the last element of m(P) may increase, and for the same reason all elements of index j > i
in dE(P) may increase. This is why we are working with a lexicographical ordering.
Suppose now one does an MC rewrite, then dC(P) strictly decreases, since one correction is
absorbed, while all E commands have equal or smaller depths. Again the measure strictly decreases.
Next, suppose one does an EA rewrite, and the E command under rewrite has depth d and rank
i. Then it has depth d− 1 in the right hand side, and all other E commands have invariant depths,
since we forbade the case when A is itself an E. It follows that the measure strictly decreases.
Finally, upon an AC rewrite, all E commands have invariant depth, except possibly one which
has smaller depth in the case A = E, and dC(P) decreases strictly because we forbade the case
where A = C. Again the claim follows.
So all rewrites decrease our ordinal measure, and therefore all sequences of rewrites are finite,
and since the system is finitely branching (there are no more than n possible single step rewrites
on a given sequence of length n), we get the statement of the theorem.
The final statement of the theorem follows from the fact that we have finitely many rules so the
system is finitely branching. In any finitely branching rewrite system with the property that every
rewrite sequence terminates, it is clearly true that there can be only finitely many standard forms.
The next theorem establishes the important determinacy property and furthermore shows that
the standard patterns have a certain canonical form which we call the NEMC form. The precise
definition is:
Definition 11 A pattern has a NEMC form if its commands occur in the order of Ns first, then
Es , then Ms, and finally Cs.
We will usually just say “EMC” form since we can assume that all the auxiliary qubits are prepared
in the |+〉 state we usually just elide these N commands.
Theorem 3 (Confluence) For all P, there exists a unique standard P ′, such that P ⇒⋆ P ′, and
P ′ is in EMC form.
Proof. Since the rewriting system is terminating, confluence follows from local confluence 7 by
Newman’s lemma, see, for example, [Bar84]. The uniqueness of the standard is form an immediate
consequence.
We look for critical pairs, that is occurrences of three successive commands where two rules can
be applied simultaneously. One finds that there are only five types of critical pairs, of these the
three involve the N command, these are of the form: NMC, NEC and NEM ; and the remaining
two are: EijMkCk with i, j and k all distinct, EijMkCl with k and l distinct. In all cases local
confluence is easily verified.
Suppose now P ′ does not satisfy the EMC form conditions. Then, either there is a pattern EA
with A not of type E, or there is a pattern AC with A not of type C. In the former case, E and
7This means that whenever two rewrite rules can be applied to a term t yielding t1 and t2, one can rewrite both
t1 and t2 to a common third term t3, possibly in many steps.
A must operate on overlapping qubits, else one may apply a free commutation rule, and A may
not be a C since in this case one may apply an EC rewrite. The only remaining case is when A
is of type M , overlapping E’s qubits, but this is what condition (D1) forbids, and since (D1) is
preserved under rewriting, this contradicts the assumption. The latter case is even simpler. ✷
We have shown that under rewriting any pattern can be put in EMC form, which is what we
wanted. We actually proved more, namely that the standard form obtained is unique. However,
one has to be a bit careful about the significance of this additional piece of information. Note first
that uniqueness is obtained because we dropped the CC and EE free commutations, thus having a
rigid notion of command sequence. One cannot put them back as rewrite rules, since they obviously
ruin termination and uniqueness of standard forms.
A reasonable thing to do, would be to take this set of equations as generating an equivalence
relation on command sequences, call it ≡, and hope to strengthen the results obtained so far, by
proving that all reachable standard forms are equivalent.
But this is too naive a strategy, since E12X1X2 ≡ E12X2X1, and:
2 ⇒⋆ Xs1Zs2Xt2Zt1E12
≡ Xs1Zt1Zs2Xt2E12
obtaining an expression which is not symmetric in 1 and 2. To conclude, one has to extend ≡
to include the additional equivalence Xs1Z
1 ≡ Zt1Xs1 , which fortunately is sound since these two
operators are equal up to a global phase. Thus, these are all equivalent in our semantics of patterns.
We summarize this discussion as follows.
Definition 12 We define an equivalence relation ≡ on patterns by taking all the rewrite rules as
equations and adding the equation Xs1Z
1 ≡ Zt1Xs1 and generating the smallest equivalence relation.
With this definition we can state the following proposition.
Proposition 13 All patterns that are equivalent by ≡ are equal in the denotational semantics.
This≡ relation preserves both the type (the (V, I,O) triple) and the underlying entanglement graph.
So clearly semantic equality does not entail equality up to ≡. In fact, by composing teleportation
patterns one obtains infinitely many patterns for the identity which are all different up to ≡. One
may wonder whether two patterns with same semantics, type and underlying entanglement graph
are necessarily equal up to ≡. This is not true either. One has J(α)J(0)J(β) = J(α + β) =
J(β)J(0)J(α) (where J(α) is defined in Section 4), and this readily gives a counter-example.
We can now formally describe a simple standardization algorithm.
Algorithm 1 Input: A pattern P on |V | = N qubits with command sequence AM · · ·A1.
Output: An equivalent pattern P ′ in NEMC form.
1. Commute all the preparation commands (new qubits) to the right side.
2. Commute all the correction commands to the left side using the EC and MC rewriting rules.
3. Commute all the entanglement commands to the right side after the preparation commands.
Note that since each qubit can be entangled with at most N − 1 other qubits, and can be
measured or corrected only once, we have O(N2) entanglement commands and O(N) measurement
commands. According to the definiteness condition, no command acts on a qubit not yet prepared,
hence the first step of the above algorithm is based on trivial commuting rules; the same is true
for the last step as no entanglement command can act on a qubit that has been measured. Both
steps can be done in O(N2). The real complexity of the algorithm comes from the second step
and the EX commuting rule. In the worst case scenario, commuting an X correction to the left
might create O(N2) other Z corrections, each of which has to be commuted to the left themselves.
Thus one can have at most O(N3) new corrections, each of which has to be commuted past O(N2)
measurement or entanglement commands. Therefore the second step, and hence the algorithm, has
a worst case complexity of O(N5).
We conclude this subsection by emphasizing the importance of the EMC form. Since the
entanglement can always be done first, we can always derive the entanglement resource needed for
the whole computation right at the beginning. After that only local operations will be performed.
This will separate the analysis of entanglement resource requirements from the classical control.
Furthermore, this makes it possible to extract the maximal parallelism for the execution of the
pattern since the necessary dependecies are explicitly expressed, see the example in section 6 for
further discussion. Finally, the EMC form provides us with tools to prove general theorems about
patterns, such as the fact that they always compute cptp-maps and the expressiveness theorems of
section 7.
5.4 Signal shifting
One can extend the calculus to include the signal shifting command Sti . This allows one to dispose
of dependencies induced by the Z-action, and obtain sometimes standard patterns with smaller
computational depth complexity, as we will see in the next section which is devoted to examples.
t[Mαi ]
s ⇒ Sti [Mαi ]s
i ⇒ StiX
s[t+si/si]
i ⇒ StiZ
s[t+si/si]
t[Mαj ]
sSri ⇒ Sri t[r+si/si][Mαj ]s[r+si/si]
Ssi S
j ⇒ StjS
s[t+sj/sj ]
where s[t/si] denotes the substitution of si with t in s, s, t being signals. Note that when we write
a t explicitly on the upper left of an M , we mean that t 6= 0. The first additional rewrite rule was
already introduced as equation (6), while the other ones merely propagate the signal shift. Clearly
one can dispose of Sti when it hits the end of the pattern command sequence. We will refer to this
new set of rules as ⇒S. Note that we always apply first the standardization rules and then signal
shifting, hence we do not need any commutation rule for E and S commands.
It is important to note that both theorem 2 and 3 still hold for this extended rewriting system.
In order to prove termination one can start with the EMC form and then adapt the proof of
Theorem 2 by defining a depth function for a signal shift similar to the depth of a correction
command. As with the correction, signal shifts can also be commuted to the left hand side of a
command sequence. Now our measure can be modified to account for the new signal shifting terms
and shown to be decreasing under each step of signal shifting. Confluence can be also proved from
local confluence using again Newman’s Lemma [Bar84]. One typical critical pair is t[Mαj ]S
i where
i appears in the domain of signal t and hence the signal shifting command Ssi will have an effect on
the measurement. Now there are two possible ways to rewrite this pair, first, commute the signal
shifting command and then replace the left signal of the measurement with its own signal shifting
command:
t[Mαj ] S
i ⇒ Ssi t+s[Mαj ]
⇒ Ssi S
The other way is to first replace the left signal of the measurement and then commute the signal
shifting command:
t[Mαj ] S
i ⇒ StjMαj Ssi
⇒ Stj Ssi Mαj
Now one more step of rewriting on the last equation will give us the same result for both choices.
Stj S
j ⇒ Ssi S
All other critical terms can be dealt with similarly.
6 Examples
In this section we develop some examples illustrating pattern composition, pattern standardization,
and signal shifting. We compare our implementations with the implementations given in the refer-
ence paper [RBB03]. To combine patterns one needs to rename their qubits as we already noted.
We use the following concrete notation: if P is a pattern over {1, . . . , n}, and f is an injection,
we write P(f(1), . . . , f(n)) for the same pattern with qubits renamed according to f . We also
write P2 ◦ P1 for pattern composition, in order to make it more readable. Finally we define the
computational depth complexity to be the number of measurement rounds plus one final correction
round. More details on depth complexity, specially on the preparation depth, i.e. depth of the
entanglement commands, can be found in [BK06].
Teleportation.
Consider the composite pattern J (β)(2, 3)◦J (α)(1, 2) with computation space {1, 2, 3}, inputs {1},
and outputs {3}. We run our standardization procedure so as to obtain an equivalent standard
pattern:
J (β)(2, 3) ◦ J (α)(1, 2) = Xs23 M
2 E23X
1 E12
⇒EX Xs23 M
1 E23E12
⇒MX Xs23 Z
s1M−α1 E23E12
Let us call the pattern just obtained J (α, β). If we take as a special case α = β = 0, we get:
1E23E12
and since we know that J (0) implements H and H2 = I, we conclude that this pattern implements
the identity, or in other words it teleports qubit 1 to qubit 3. As it happens, this pattern obtained
by self-composition, is the same as the one given in the reference paper [RBB03, p.14].
x-rotation.
Here is the reference implementation of an x-rotation [RBB03, p.17], Rx(α):
Xs23 Z
s1Mx1E23E12
with type {1, 2, 3}, {1}, and {3}. There is a natural question which one might call the recognition
problem, namely how does one know this is implementing Rx(α) ? Of course there is the brute
force answer to that, which we applied to compute our simpler patterns, and which consists in
computing down all the four possible branches generated by the measurements at qubits 1 and 2.
Another possibility is to use the stabilizer formalism as explained in the reference paper [RBB03].
Yet another possibility is to use pattern composition, as we did before, and this is what we are
going to do.
We know that Rx(α) = J(α)H up to a global phase, hence the composite pattern J (α)(2, 3) ◦
H(1, 2) implements Rx(α). Now we may standardize it:
J (α)(2, 3) ◦ H(1, 2) = Xs23 M
2 E23X
⇒EX Xs23 Z
1E23E12
⇒MX Xs23 Z
s1Mx1E23E12
obtaining exactly the implementation above. Since our calculus preserves the semantics, we deduce
that the implementation is correct.
z-rotation.
Now, we have a method here for synthesizing further implementations. Let us replay it with another
rotation Rz(α). Again we know that Rz(α) = HRx(α)H, and we already know how to implement
both components H and Rx(α).
So we start with the pattern H(4, 5) ◦ Rx(α)(2, 3, 4) ◦ H(1, 2) and standardize it:
H(4, 5) ◦ Rx(α)(2, 3, 4) ◦ H(1, 2) =
H(4, 5)Xs34 Z
1+s2Mx2E34 E23X
1E12 ⇒EX
H(4, 5)Xs34 Z
1+s2Mx2X
2 E34Z
1E123 ⇒EZ
H(4, 5)Xs34 Z
1+s2Z
1E1234 ⇒MX
H(4, 5)Xs34 Z
1+s2Zs13 M
1E1234 ⇒MZ
4 E45X
s1 [Mα3 ]
1+s2Mx2M
1E1234 ⇒EX
Xs45 Z
s1 [Mα3 ]
1+s2Mx2M
1E12345 ⇒MX
s1 [Mα3 ]
1+s2Mx2M
1E12345 ⇒MZ
Xs45 Z
s2 [Mx4 ]
s3s1 [Mα3 ]
1+s2Mx2M
1E12345
To aid reading E23E12 is shortened to E123, E12E23E34 to E1234, and
t[Mαi ]
1+s is used as shorthand
for t[M−αi ]
Here for the first time, we see MZ rewritings, inducing the Z-action on measurements. The
resulting standardized pattern can therefore be rewritten further using the extended calculus:
Xs45 Z
s2 [Mx4 ]
s3s1 [Mα3 ]
1+s2Mx2M
1E12345 ⇒S
s2+s4
s1+s3
1+s2Mx2M
1E12345
obtaining the pattern given in the reference paper [RBB03, p.5].
However, just as in the case of the Rx rotation, we also have Rz(α) = HJ(α) up to a global
phase, hence the pattern H(2, 3)J (α)(1, 2) also implements Rz(α), and we may standardize it:
H(2, 3) ◦ J (α)(1, 2) = Xs23 Mx2 E23X
1 E12
⇒EX Xs23 Z
1 E123
⇒MX Xs23 Z
1 E123
obtaining a 3 qubit standard pattern for the z-rotation, which is simpler than the preceding one,
because it is based on the J (α) generators. Since the z-rotation Rz(α) is the same as the phase
operator:
P (α) =
0 eiα
up to a global phase, we also obtain with the same pattern an implementation of the phase oper-
ator. In particular, if α = π
, using the extended calculus, we get the following pattern for P (π
Xs23 Z
1E123.
General rotation.
The realization of a general rotation based on the Euler decomposition of rotations asRx(γ)Rz(β)Rx(α),
would results in a 7 qubit pattern. We get a 5 qubit implementation based on the J(α) decompo-
sition [DKP05]:
R(α, β, γ) = J(0)J(−α)J(−β)J(−γ)
(The parameter angles are inverted to make the computation below more readable.) The extended
standardization procedure yields:
J (0)(4, 5)J (−α)(3, 4)J (−β)(2, 3)J (−γ)(1, 2) =
Xs45 M
4E45X
3 E34X
2 E23X
1E12 ⇒EX
4E45X
3 E34X
1E123 ⇒MX
4E45X
3 E34X
1E123 ⇒EXZ
Xs45 M
4E45X
1E1234 ⇒MXZ
4 E45X
s1 [Mα3 ]
s2 [M
1E1234 ⇒EXZ
Xs45 M
s1 [Mα3 ]
s2 [M
1E12345 ⇒MXZ
s2 [M04 ]
s1 [Mα3 ]
s2 [M
1E12345 ⇒S
s2+s4
s1+s3
s2 [M
1E12345
CNOT (∧X).
This is our first example with two inputs and two outputs. We use here the trivial pattern I with
computation space {1}, inputs {1}, outputs {1}, and empty command sequence, which implements
the identity over H1.
One has ∧X = (I ⊗ H)∧Z(I ⊗ H), so we get a pattern using 4 qubits over {1, 2, 3, 4}, with
inputs {1, 2}, and outputs {1, 4}, where one notices that inputs and outputs intersect on the control
qubit {1}:
(I(1)⊗ 〈(3, 4))∧Z(1, 3)(I(1) ⊗ 〈(2, 3)) = Xs34 Mx3E34E13X
By standardizing:
3E34 E13X
2E23 ⇒EX
3 E34X
2E13E23 ⇒EX
Xs34 Z
2E13E23E34 ⇒MX
Xs34 Z
2E13E23E34
Note that, in this case, we are not using the E1234 abbreviation, because the underlying struc-
ture of entanglement is not a chain. This pattern was already described in Aliferis and Leung’s
paper [AL04]. In their original presentation the authors actually use an explicit identity pattern (us-
ing the teleportation pattern J (0, 0) presented above), but we know from the careful presentation
of composition that this is not necessary.
We present now a family of patterns preparing the GHZ entangled states |0 . . . 0〉 + |1 . . . 1〉. One
GHZ(n) = (Hn ∧Zn−1n . . . H2 ∧Z12)|+. . .+〉
and by combining the patterns for ∧Z and H, we obtain a pattern with computation space
{1, 2, 2′, . . . , n, n′}, no inputs, outputs {1, 2′, . . . , n′}, and the following command sequence:
MxnEnn′E(n−1)′n . . . X
Mx2E22′E12
With this form, the only way to run the pattern is to execute all commands in sequence. The
situation changes completely, when we bring the pattern to extended standard form:
MxnEnn′E(n−1)′n . . . X
Mx3E33′ E2′3X
Mx2E22′E12 ⇒
MxnEnn′E(n−1)′n . . . X
Mx3 Z
2E33′E2′3E22′E12 ⇒
MxnEnn′E(n−1)′n . . . X
s2 [Mx3 ]M
2E33′E2′3E22′E12 ⇒⋆
Xsnn′ . . . X
sn−1 [Mxn ] . . .
s2 [Mx3 ]M
2Enn′E(n−1)′n . . . E33′E2′3E22′E12 ⇒S
Xs2+s3+···+sn
. . . Xs2+s3
Mxn . . .M
2Enn′E(n−1)′n . . . E33′E2′3E22′E12
All measurements are now independent of each other, it is therefore possible after the entanglement
phase, to do all of them in one round, and in a subsequent round to do all local corrections. In
other words, the obtained pattern has constant computational depth complexity 2.
Controlled-U .
This final example presents another instance where standardization obtains a low computational
depth complexity, the proof of this fact can be found in [BK06]. For any 1-qubit unitary U , one
has the following decomposition of ∧U in terms of the generators J(α) [DKP05]:
∧U12 = J01Jα
2 ∧Z12J
−π−δ−β
2 ∧Z12J
−β+δ−π
with α′ = α + β+γ+δ
. By translating each J operator to its corresponding pattern, we get the
following wild pattern for ∧U :
BEBCX
A EABX
j EjkX
i Eij
h EhiX
g EghX
fEfgEAfX
e Eef
Xsde M
d EdeX
π+δ+β
c EcdX
bEbcEAbX
β−δ+π
a Eab
In order to run the wild form of the pattern one needs to follow the pattern commands in sequence.
It is easy to verify that, because of the dependent corrections, one needs at least 12 rounds to
complete the execution of the pattern. The situation changes completely after extended standard-
ization:
si+sg+se+sc+sa
sj+sh+sf+sd+sb
sA+se+sc
sh+sf+sd+sb [M
]sg+se+sc+sa [M
sf+sd+sb
M0f [M
sd+sb [M
sc+sa [M
π+δ+β
sbM0bM
β−δ+π
EBCEABEjkEijEhiEghEfgEAfEefEdeEcdEbcEabEAb
Now the order between measurements is relaxed, as one sees in Figure 2, which describes the depen-
dency structure of the standard pattern above. Specifically, all measurements can be completed in
7 rounds. This is just one example of how standardization lowers computational depth complexity,
and reveals inherent parallelism in a pattern.
Figure 2: The dependency graph for the standard ∧U pattern.
7 The no dependency theorems
From standardization we can also infer results related to dependencies. We start with a simple
observation which is a direct consequence of standardization.
Lemma 14 Let P be a pattern implementing some cptp-maps T , and suppose P’s command se-
quence has measurements only of the Mx and My kind, then U has a standard implementation,
having only independent measurements, all being of the Mx and My kind (therefore of computa-
tional depth complexity at most 2).
Proof. Write P ′ for the standard pattern associated to P. By equations (15) and (16), the X-
actions can be eliminated from P ′, and then Z-actions can be eliminated by using the extended
calculus. The final pattern still implements T , has no longer any dependent measurements, and
has therefore computational depth complexity at most 2. ✷
Theorem 4 Let U be a unitary operator, then U is in the Clifford group iff there exists a pattern
P implementing U , having measurements only of the Mx and My kind.
Proof. The “only if” direction is easy, since we have seen in the example section, standard patterns
for ∧X, H and P (π
) which had only independent Mx and My measurements. Hence any Clifford
operator can be implemented by a combination of these patterns. By the lemma above, we know
we can actually choose these patterns to be standard.
For the “if” direction, we prove that U belongs to the normalizer of the Pauli group, and hence
by definition to the Clifford group. In order to do so we use the standard form of P written as
P ′ = CP ′MP ′EP ′ which still implements U , and has only Mx and My measurements. Recall that,
because of equations (15) and (16), these measurements are independent.
Let i be an input qubit, and consider the pattern P ′′ = P ′Ci, where Ci is either Xi or Zi.
Clearly P ′′ implements UCi. First, one has:
CP ′MP ′EP ′Ci ⇒⋆EC CP ′MP ′C ′EP ′
for some non-dependent sequence of corrections C ′, which, up to free commutations can be written
uniquely as C ′OC
′′, where C ′O applies on output qubits, and therefore commutes to MP ′ , and C
applies on non-output qubits (which are therefore all measured in MP ′). So, by commuting C
both through MP ′ and CP ′ (up to a global phase), one gets:
CP ′MP ′C
′EP ′ ⇒⋆ C ′OCP ′MP ′C ′′EP ′
Using equations (15), (16), and the extended calculus to eliminate the remaining Z-actions, one
gets:
MP ′C
′′ ⇒⋆MC,S SMP ′
for some product S =
{j∈J} S
j of constant shifts
8, applying to some subset J of the non-output
qubits. So:
C ′OCP ′MP ′C
′′EP ′ ⇒⋆MC,S C ′OCP ′SMP ′EP ′
⇒⋆ C ′OC ′′OCP ′MP ′EP ′
where C ′′O is a further constant correction obtained by signal shifting CP ′ with S. This proves that
P ′′ also implements C ′OC ′′OU , and therefore UCi = C ′OC ′′OU which completes the proof, since C ′OC ′′O
is a non dependent correction. ✷
The “only if” part of this theorem already appears in previous work [RBB03, p.18]. The “if”
part can be construed as an internalization of the argument implicit in the proof of Gottesman-Knill
theorem [NC00, p.464].
We can further prove that dependencies are crucial for the universality of the model. Observe
first that if a pattern has no measurements, and hence no dependencies, then it follows from (D2)
that V = O, i.e., all qubits are outputs. Therefore computation steps involve only X, Z and
8Here we have used the trivial equations Za+1i = ZiZ
i and X
i = XiX
∧Z, and it is not surprising that they compute a unitary which is in the Clifford group. The
general argument essentially consists in showing that when there are measurements, but still no
dependencies, then the measurements are playing no part in the result.
Theorem 5 Let P be a pattern implementing some unitary U , and suppose P’s command sequence
doesn’t have any dependencies, then U is in the Clifford group.
Proof. Write P ′ for the standard pattern associated to P. Since rewriting is sound, P ′ still
implements U , and since rewriting never creates any dependency, it still has no dependencies. In
particular, the corrections one finds at the end of P ′, call them C, bear no dependencies. Erasing
them off P ′, results in a pattern P ′′ which is still standard, still deterministic, and implementing
U ′ := C†U .
Now how does the pattern P ′′ run on some input φ ? First φ⊗|+. . .+〉 goes by the entanglement
phase to some ψ ∈ HV , and is then subjected to a sequence of independent 1-qubit measurements.
Pick a basis B spanning the Hilbert space generated by the non-output qubits HVrO and associated
to this sequence of measurements.
Since HV = HO ⊗HVrO and HVrO = ⊕φb∈B[φb], where [φb] is the linear subspace generated by
φb, by distributivity, ψ uniquely decomposes as:
φb∈B xb ⊗ φb
where φb ranges over B, and xb ∈ HO. Now since P ′′ is deterministic, there exists an x, and scalars
λb such that xb = λbx. Therefore ψ can be written x ⊗ ψ′, for some ψ′. It follows in particular
that the output of the computation will still be x (up to a scalar), no matter what the actual
measurements are. One can therefore choose them to be all of the Mx kind, and by the preceding
theorem U ′ is in the Clifford group, and so is U = CU ′, since C is a Pauli operator. ✷
From this section, we conclude in particular that any universal set of patterns has to include
dependencies (by the preceding theorem), and also needs to use measurements Mα where α 6= 0
modulo π
(by the theorem before). This is indeed the case for the universal set J (α) and ∧Z.
8 Other Models
There are several other approaches to measurement-based computation as we have mentioned in
the introduction. However, it is only for the one-way model that the importance of having all
the entanglement in front has been emphasized. For example, Gottesman and Chuang describe
computing with teleportation in the setting of the circuit model and hence the computation is very
sequential [GC99]. What we will do is to give a general treatment of a variety of measurement-
based models – including some that appear here for the first time – in the setting of our calculus.
More precisely we would like to know other potential definitions for commands N , E, M and C
that lead to a model that still satisfies the properties of: (i) being closed under composition; (ii)
universality and (iii) standardization.
Moreover we are interested in obtaining a compositional embedding of these models into a single
one-qubit measurement-based model. The teleportation model can indeed be embedded into the
one-way model. There is, however, a new model, the Pauli model – formally defined here for the
first time – which is motivated by considerations of fault tolerance [RAB04, DK05b, DKOS06]. The
Pauli model can be embedded into a slight generalization of the one-way model called the phase
model; also given here for the first time. The one-way model will trivially embed in the phase
model so by composition all the measurement-based models will embed in the phase model. We
could have done everything ab initio in terms of the phase model but this would have made much
of the presentation unnecessarily complicated at the outset.
We recall the remark from the introduction that these embeddings have three advantages: first,
we get a workable syntax for handling the dependencies of operators on previous measurement
outcomes, second, one can use these embeddings to transfer the measurement calculus previously
developed for the one-way model to obtain a calculus for the new model including, of course, a
standardization procedure that we get automatically; lastly, one can embed the patterns from the
phase model into the new models and vice versa. In essence, these compositional embeddings will
allow us to exhibit the phase model as being a core calculus for measurement-based computation.
However different models are interesting from the point of view of implementation issues like fault-
tolerance and ease of preparation of entanglement resources. Our embeddings allow one to move
easily between these models and to concentrate on the one-way model for designing algorithms and
proving general theorems.
This section has been structured into several subsections, one for each model and its embedding.
8.1 Phase Model
In the one-way model the auxiliary qubits are initialized to be in the |+〉 state. We extend the
one-way model to allow the auxiliary qubits to be in a more general state. We define the extended
preparation command Nαi to be the preparation of the auxiliary qubit i in the state |+α〉. We
also add a new correction command Zαi , called a phase correction to guarantee that we can obtain
determinate patterns. The dependent phase correction is written as Z
i with Z
i = I and
0 eiα
. Under conjugation, the phase correction, defines a new action over measurement:
†Mαi Z
and since the measurement is destructive, it simplifies to Mαi Z
i = M
i . This action does
not commute with Pauli actions and hence one cannot write a compact notation for dependent
measurement, as we did before, and the computation of angle dependencies is a bit more compli-
cated. Thereafter, a measurement preceded by a sequence of corrections on the same qubit will be
called a dependent measurement. Note that, by the absorption equations, this indeed can be seen
as a measurement, where the angle depends on the outcomes of some other measurements made
beforehand.
To complete the extended calculus it remains to define the new rewrite rules:
i ⇒ Z
i Eij EP
Mαi X
i ⇒ M
(−1)sα
Mαi Z
i ⇒ M
Mαi Z
i ⇒ M
The above rules together with the rewriting rules of the one-way model described in Section 5, lead
to a standardization procedure for the model. It is trivial that the one-way model is a fragment of
this generalized model and hence universality immediately follows. It is also easy to check that the
model is closed under composition and all the semantical properties of the one-way model can be
extended to this general model as well.
The choice of extended preparations and its concomitant phase correction is actually quite
delicate. One wishes to keep the standardizability of the calculus which constrains what can be
added but one also wishes to have determinate patterns which forces us to put in appropriate
corrections. The phase model is only a slight extension of the original one-way model, but it allows
a discussion of the next model which is of great physical interest.
8.1.1 Pauli model
An interesting fragment of the phase model is defined by restricting the angles of measurements to
{0, π
, π,−π
} i.e. Pauli measurements and the angles of preparation to 0 and π
. Also the correction
commands are restricted to Pauli corrections X, Z and Phase correction Z
8 . One readily sees that
the subset of angles is closed under the actions of the corrections and hence the Pauli model is
closed under composition.
Proposition 15 The Pauli model is approximately universal.
Proof. We know that the set consisting of J(0) (which is H), J(π
), and ∧Z is approximately
universal. Hence, to prove the approximate universality of Pauli model, it is enough to exhibit a
pattern in the Pauli model for each of these three unitaries. We saw before that J(0) and ∧Z are
computed by the following 2-qubit patterns:
J (0) := Xs12 M01E12
∧Z := E12
where both belong also to the Pauli model. The pattern for Jπ
in the one-way model is expressed
as follows:
) := Xs12 M
1 E12
= Xs12 M
1E12Z
The above forms do not fit in the Pauli model, since the first one uses a measurement with an angle
and the second uses Z
4 . However by teleporting the input qubit and then applying the Z
4 and
finally running the standardization procedure we obtain the following pattern in the Pauli model
for J(π
1E12Z
3E34 Z
1E12E23
= Xs34 M
3E34Z
1E12E23 Z
3E34Z
1E12E23 Z
s3+s2
−(−1)s1s2 π2
1E12E23E34N
Approximate universality for the Pauli model is now immediate. ✷
Note that we cannot really expect universality (as we had for the phase model) because the
angles are restricted to a discrete set. On the other hand it is precisely this restriction that makes
the Pauli model interesting from the point of view of implementation. The other particular interest
behind this model, apart from its simple structure, is based on the existence of a novel fault tolerant
technique for computing within this framework [BK05, RAB04, DKOS06].
8.2 Teleportation
Another class of measurement-based models – older, in fact, than the one-way model – uses 2-
qubit measurements. These are collectively referred to as teleportation models [Leu04]. Several
papers that are concerned with the relation and possible unification of these models [CLN05,
AL04, JP05] have already appeared. One aspect of these models that stands in the way of a
complete understanding of this relation, is that, whereas in the one-way model one has a clearly
identified class of measurements, there is less agreement concerning which measurements are allowed
in teleportation models.
We propose here to take as our class of 2-qubit measurements a family obtained as the conjugate
under the operator ∧Z of tensors of 1-qubit measurements. We show that the resulting teleportation
model is universal. Moreover, almost by construction, it embeds into the one-way model, and thus
exposes completely the relation between the two models.
Before embarking on the specifics of our family of 2-qubit measurements, we remark that the
situation commented above is more general:
Lemma 16 Let A be an orthonormal basis in ⊗nC2, with associated n-qubit measurement MA,
and Ai with i = 1, . . . , n be orthonormal bases in C2, with associated 1-qubit measurements MAii .
Then there exists a unique (up to a permutation) n-qubit unitary operator U such that:
MA1···n = U1···n(⊗iM
1···n
Proof. Take U to map ⊗iAi to A. ✷
This simple lemma says that general n-qubit measurements can always be seen as conjugated
1-qubit measurements, provided one uses the appropriate unitary to do so. As an example consider
the orthogonal graph basis G = ∧Z12{|±〉 ⊗ |±〉} then the two-qubit graph basis measurements are
defined as MG12 = ∧Z12(M01 ⊗M02 )∧Z12. It is now natural to extend our definition of M
12 to obtain
the family of 2-qubit measurements of interest:
12 := ∧Z12(M
2 )∧Z12 (17)
corresponding to projections on the basis Gα,β := ∧Z12(P1(α)⊗P2(β))({|±〉 ⊗ |±〉}. This family of
two-qubit measurements together with the preparation, entanglement and corrections commands
of the one-way model define the teleportation model.
Before we carry on, a clarification about our choice of measurements in the teleportation model
is necessary. The usual teleportation protocol uses Bell basis measurement defined with
B = ∧X12{|±〉 ⊗ |0/1〉}
MB12 = ∧X12(Mz1 ⊗Mz2 )∧X12
where Mz is the computational-basis measurement. Note how similar these equations are to the
equations defining the graph basis measurements. This is a clear indication that everything that
follows can be transferred to the case where X replaces Z, and B replaces G. However, since the
methodology we adopt is to embed the 2-qubit measurement based model in the one-way model,
and the latter is based on ∧Z and G, we will work with the graph-basis measurements. Furthermore,
since ∧Z is symmetric, whereas ∧X (a.k.a. as C-NOT) is not, the algebra is usually nicer to work
with.
Now we prove that the family of measurements in Equation 17 leads to a universal model,
which embeds nicely into the one-way model, but first we need to describe the important notion
of dependent measurements. These will arise as a consequence of standardization; they were not
considered in the existing teleportation models.
In what follows we drop the subscripts on the ∧Z unless they are really necessary. We write
(s(i), s(j)) ∈ Z2 × Z2 to represent outcome of a 2-qubit measurement, with the specific convention
that (0, 0), (0, 1), (1, 0), and (1, 1), correspond respectively to the cases where the state collapses
to ∧Z|+α〉|+α〉, ∧Z|+α〉|−α〉, ∧Z|−α〉|+α〉, and ∧Z|−α〉|−α〉.
We will use two types of dependencies for measurements associated with X-action and Z-action:
(s,t) = M
(−1)sα,(−1)tβ
(u,v)[M
ij ] = M
α+uπ,β+vπ
where s, t, u and v are in Z2. The two actions commute, so the equations above define unambigu-
ously the full dependent measurement (u,v)[M
(s,t). Here are some useful abbreviations:
(0,0)[Mα,β ](s,t) := [Mα,β ](s,t)
(u,v)[Mα,β ](0,0) := (u,v)[Mα,β ]
(0,0)[Mα,β ](0,0) :=Mα,β
Mα,x := Mα,0
Mα,y :=Mα,
As in the 1-qubit measurement case we obtain the following rewriting rules for the teleportation
model:
i ⇒ Xsi ZsjEij EX
i ⇒ ZsiEij EZ
(u,v)[M
(s,t)Xri ⇒ (u,v+r)[M
(s+r,t) MX
(u,v)[M
(s,t)Xrj ⇒ (u+r,v)[M
(s,t+r) MX
(u,v)[M
(s,t)Zri ⇒ (u+r,v)[M
(s,t) MZ
(u,v)[M
(s,t)Zrj ⇒ (u,v+r)[M
(s,t) MZ
to which we add also the trivial commutation rewriting which are possible between commands that
don’t overlap (meaning, acting on disjoint sets of qubits).
8.2.1 Embedding
We describe how to translate 2-qubit EMC patterns to 1-qubit patterns and vice versa. The
following equation plays the central role in the translation:
ij = Eij(M
j )Eij (18)
Note that this immediately gives the denotational semantics of two-qubit measurements as cptp-
maps. Furthermore, all other commands in the teleportation model are the same as in the one-way
model, so we have right away a denotational semantics for the entire teleportation model in terms
of cptp-maps.
We write P for the collection of patterns in the one-way model and T for the collection of
patterns in the teleportation model.
Theorem 6 There exist functions [·]f : P → T and [·]b : T → P such that
1. ∀P ∈ P : [[P]] = [[[P]f ]];
2. ∀T ∈ T : [[T ]] = [[[T ]b]];
3. [·]f ◦ [·]b and [·]b ◦ [·]f are both identity maps.
Proof. We first define the forward map [·]f in stages as follows for any patterns P = (V, I,O,An . . . A1):
1. For any i ∈ V rO (i.e. measured qubits) we add an auxiliary qubit id called a dummy qubit
to the space V .
2. For any i ∈ V rO we replace any occurrence of Mαi with Mαi Mxid .
3. We then replace each of the newly created occurrences of Mαi M
Eiid .
Now we show that the first condition stated in the theorem holds; we do this stage wise. The
first two stages are clear because we are just adding qubits that have no effect on the pattern
because they are not entangled with any pre-existing qubit, and no other command depends on a
measurement applied to one of the dummy qubits. Furthermore, we add qubits in the state |+〉
and measure them in the |±〉 basis. The invariance of the semantics under stage 3 is an immediate
consequence of Equation 18 and the fact that all the measurements are destructive, and hence an
entanglement command on qubits appearing after a measurement of any of those qubits can just
be removed.
The map [·]b is defined similarly except that there is no need to add dummy qubits. One
only needs to replace any two-qubit measurement M
ij with M
j Eij . Again, this clearly pre-
serves the semantics of patterns because of Equation 18 and the above remark about destructive
measurements. Thus condition 2 of the theorem holds.
The fact that the two maps are mutual inverses follows easily. As all the steps in the translations
are local we can reason locally. Looking at the forward mapping followed by the backward mapping
we get the following sequence of transformations
Mαi ⇒stage 1,2 Mαi Mxid
⇒Equation 18 Mα,xiid Eiid
⇒Equation 18 Mαi MxidEiidEiid
⇒ Mαi Mxid
⇒ Mαi
This shows that we have the third condition of the theorem. ✷
Note that the translations are compositional since the denotational semantics is and also it fol-
lows immediately that the teleportation model is universal and admits a standardization procedure.
Example. Consider the teleportation pattern in the teleportation model given by the command
sequence: Xs13 Z
12 E23, we perform the above steps:
12 E23 ⇒Equation 18
Xs13 Z
2E12E23
and hence obtain the teleportation pattern with 1-qubit measurements.
Example. We saw before, the following EMC 1-qubit pattern for Rz(α) which can be embedded
to an EMC 2-qubit pattern using the above steps:
s1M−α1 E12E23 ⇒stage 1,2
s1Mx2dM
E12E23 ⇒Equation 18 and standardization
Xs23 Z
](s1,0)M
E11dE22dE12E23
Note that we have explicit algorithmic translations between the models and not just illustrative
examples. This is the main advantage of our approach in unifying these two models compared to
the extant work [CLN05, AL04, JP05].
9 Conclusion
We have presented a calculus for the one-way quantum computer. We have developed a syntax
of patterns and, much more important, an algebra of pattern composition. We have seen that
pattern composition allows for a structured proof of universality, which also results in parsimonious
implementations. We develop an operational and denotational semantics for this model; in this
simple first-order setting their equivalence is clear.
We have developed a rewrite system for patterns which preserves the semantics. We have
shown further that our calculus defines a polynomial-time standardization algorithm transforming
any pattern to a standard form where entanglement is done first, then measurements, then local
corrections. We have inferred from this procedure that the denotational semantics of any pattern is
a cptp-map and also proved that patterns with no dependencies, or using only Pauli measurements,
may only implement unitaries in the Clifford group.
In addition we introduced some variations of the one-way and teleportation models and pre-
sented compositional back-and-forth embeddings of these models into the one-way model. This
allows one to carry forward all the theory we have developed: semantics, rewrite rules, standard-
ization, no-dependency theorems and universality. In fact the result of making the connection
between the one-way model and the teleportation model is to introduce ideas: dependent mea-
surements, standard forms for patterns and a standardization procedure which had never been
considered before for the teleportation model. This shows the generality of our formalism: we
expect that any yet to be discovered measurement-based computation frameworks can be treated
in the same way.
Perhaps the most important aspect of standardization is the fact that now we can make patterns
maximally parallel and distributed because all the entanglement operators, i.e. non-local operators,
can be performed at the beginning of the computation. Then from the dependency structure that
can be obtained from the standard form of a pattern the measurements can be organized to be as
parallel as possible. This is the essence of the difference between measurement-based computation
and the quantum circuit model or the quantum Turing machine.
We feel that our measurement calculus has shown the power of the formalisms developed by
the programming languages community to analyze quantum computations. The ideas that we use:
rewriting theory, (primitive) type theory and above all, the importance of reasoning compositionally,
locally and modularly, are standard for the analysis of traditional programming languages. However,
for quantum computation these ideas are in their infancy. It is not merely a question of adapting
syntax to the quantum setting; there are fundamental new ideas that need to be confronted. What
we have done here is to develop such a theory in a new, physically-motivated setting.
There were prior discussions about putting patterns in a standard form [RB02] but these worked
only with strongly deterministic patterns, furthermore one needs to know which unitary is being
implemented. In our case the rewrite rules are entirely local and work equally well with all patterns.
An interesting question related to the measurement calculus is whether one can give sufficient
conditions – depending only on the entanglement structure of a pattern – that guarantee deter-
minacy. In a related paper the first two authors have solved this problem [DK05a]. In effect
given an entanglement structure with distinguished inputs and outputs one can enumerate all the
unitaries that can be implemented with it. This gives a precise handle on the entanglement re-
sources needed in the design of specific algorithms and protocols directly in the measurement-based
model [dBDK06].
Finally, there is also a compelling reading of dependencies as classical communications, while
local corrections can be thought of as local quantum operations in a multipartite scenario. From
this point of view, standardization pushes non-local operations to the beginning of a distributed
computation, and it seems the measurement calculus could prove useful in the analysis of dis-
tributed quantum protocols. To push this idea further, one needs first to articulate a definition of
a distributed version of the measurement calculus; this was done in a recent paper [DDKP05]. The
distributed version of the calculus was then used to analyze a variety of quantum protocols and to
examine the notion of knowledge flow in them [DP05].
Acknowledgments
We thank the anonymous referees for their helpful comments. We would like to thank Ellie D’Hondt
for implementing an interpreter for the measurement calculus and Daniel Gottesman for clarifying
the extent to which Theorem 4 was implicit in his own work. We have benefited from discus-
sions with Samson Abramsky, Hans Briegel, Dan Browne, Philippe Jorrand, Harold Olivier, Simon
Perdrix and Marcus Silva. Elham Kashefi was partially supported by the PREA, MITACS, OR-
DCF, CFI and ARDA projects during her stay at University of Waterloo where this work was
finished. Prakash Panangaden thanks EPSRC and NSERC for support and Samson Abramsky and
the Oxford University Computing Laboratory for hospitality at Oxford where this work was begun.
References
[AC04] S. Abramsky and B. Coecke. A categorical semantics of quantum protocols. In IEEE
Computer Science Press, editor, Proceedings of the 19th Annual IEEE Symposium
on Logic in Computer Science (LiCS), 2004.
[AD04] S. Abramsky and R. Duncan. A categorical quantum logic. In Selinger [Sel04a].
quant-ph/0512114.
[AG05] T. Altenkirch and J. Grattage. A functional quantum programming language. In
IEEE Computer Science Press, editor, Proceedings of the 20th Annual IEEE Sympo-
sium on Logic in Computer Science (LiCS), 2005.
[AL04] P. Aliferis and D. W. Leung. Computation by measurements: a unifying picture.
Physical Review A, 70, 2004.
[Bar84] H. P. Barendregt. The Lambda Calculus, Its Syntax and Semantics. Studies in Logic.
North-Holland, 1984.
[BB84] G. Brassard and C. H. Bennett. Public key distribution and coin tossing. In Pro-
ceedings of IEEE International Conference on Computers, Systems and Signal Pro-
cessing, 1984.
[BBC+93] C. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. Wootters. Tele-
porting an unknown quantum state via dual classical and EPR channels. Physical
Review Letters, 1993.
[BBFM06] S. C. Benjamin, D. E. Browne, J. Fitzsimons, and J. J. L. Morton. Brokered graph
state quantum computing. New Journal of Physics, 8, 2006.
[BES05] S.C. Benjamin, J. Eisert, and T. M. Stace. Optical generation of matter qubit graph
states. New Journal of Physics, 7, 2005.
[BK05] S. Bravyi and A. Kitaev. Universal quantum computation with ideal clifford gates
and noisy ancillas. Physical Review A, 71, 2005.
[BK06] A. Broadbent and E. Kashefi. On parallelizing quantum circuits. In Preparation,
2006.
[BR05] D. E. Browne and T. Rudolph. Resource-efficient linear optical quantum computa-
tion. Physical Review Letters, 95, 2005.
[BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal of Com-
puting, 5(26), 1997.
[CAJ05] S. R. Clark, C. Moura Alves, and D. Jaksch. Efficient generation of graph states for
quantum computation. New Journal of Physics, 7, 2005.
[CCWD06] Q. Chen, J. Cheng, K. L. Wang, and J. Du. Efficient construction of two-dimensional
cluster states with probabilistic quantum gates. Physical Review A, 73, 2006.
[Cho75] M. D. Choi. Completely positive linear maps on complex matrices. Linear Algebra
and Applications, 10, 1975.
[CLN05] A. M. Childs, D. W. Leung, and M. A. Nielsen. Unified derivations of measurement-
based schemes for quantum computation. Physical Review A, 71, 2005.
http://arxiv.org/abs/quant-ph/0512114
[Coe04] B. Coecke. The logic of entanglement. quant-ph/0402014, 2004.
[DAB03] W. Dür, H. Aschauer, and H. J. Briegel. Multiparticle entanglement purification for
graph state. Physical Review Letters, 91, 2003.
[dBDK06] N. de Beaudrap, V. Danos, and E. Kashefi. Phase map decomposition for unitaries.
quant-ph/0603266, 2006.
[DDKP05] V. Danos, E. D’Hondt, E. Kashefi, and P. Panangaden. Distributed measurement-
based quantum computation. In Selinger [Sel05b]. quant-ph/0506070.
[Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum
computer. In Proceedings of the Royal Society of London, volume A400, 1985.
[Deu87] D. Deutsch. Quantum computers. Computer Bulletin, 3(2), 1987.
[Deu89] D. Deutsch. Quantum computational networks. Proceedings of the Royal Society of
London, 425, 1989.
[DHN06] C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen. Noise thresholds for optical
cluster-state quantum computation. Physical Review A, 73, 2006.
[DJ92] D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. In
Proceedings of the Royal Society of London, volume 439, 1992.
[DK05a] V. Danos and E. Kashefi. Determinism in the one-way model. quant-ph/0506062,
2005.
[DK05b] V. Danos and E. Kashefi. Pauli measurements are universal. In Selinger [Sel05b].
[DKOS06] V. Danos, E. Kashefi, H. Olivier, and M. Silva. Pauli model, a new approach towards
fault tolerant quantum computing. In Preparation, 2006.
[DKP05] V. Danos, E. Kashefi, and P. Panangaden. Parsimonious and robust realizations of
unitary maps in the one-way model. Physical Review A, 72, 2005.
[dNDM04a] M. Van den Nest, J. Dehaene, and B. De Moor. An efficient algorithm to recognize
local clifford equivalence of graph states. Physical Review A, 70, 2004.
[dNDM04b] M. Van den Nest, J. Dehaene, and B. De Moor. Graphical description of the action
of local clifford transformations on graph states. Physical Review A, 69, 2004.
[DP05] E. D’Hondt and P. Panangaden. Reasoning about quantum knowledge. In Proceed-
ings of the 25th Conference on Foundations of Software Technology and Theoretical
Computer Science, 2005.
[DP06] E. D’Hondt and P. Panangaden. Quantum weakest preconditions. Mathematical
Structures in Computer Science, 16, 2006.
[DS96] C. Dürr and M. Santha. A decision procedure for unitary linear quantum cellular
automata. In Proceedings of FOCS’96 – Symposium on Foundations of Computer
Science. LNCS, 1996.
http://arxiv.org/abs/quant-ph/0402014
http://arxiv.org/abs/quant-ph/0603266
http://arxiv.org/abs/quant-ph/0506070
http://arxiv.org/abs/quant-ph/0506062
[Dun05] R. Duncan. An abstract approach to entanglement, Dec 2005. Mathematical Struc-
tures In Quantum Informatics, QDay II.
[Eke91] A. Ekert. Quantum cryptography based on bell’s theorem. Physical Review Letters,
67, 1991.
[Gay05] S. J. Gay. Quantum programming languages: Survey and bibliography. Bulletin of
the EATCS, 86, 2005.
[GC99] D. Gottesman and I. L. Chuang. Quantum teleportation is a universal computational
primitive. Nature, 402, 1999.
[GHW05] G. Gilbert, M. Hamrick, and Y. S. Weinstein. Efficient construction of photonic
quantum computational clusters. quant-ph/0512110, 2005.
[GN05] S. J. Gay and R. Nagarajan. Communicating quantum processes. In Proceedings
of the 32nd ACM SIGACT-SIGPLAN Symposium on Principles of Programming
Languages (POPL). ACM Press, 2005. quant-ph/0409052.
[Got97] D. Gottesoman. Stabilizer codes and quantum error correction. PhD thesis, California
Institute of Technology, 1997.
[Gro98] L. K. Grover. A framework for fast quantum mechanical algorithms. In Proceedings
of STOC’98 – Symposium on Theory of Computing, 1998.
[HDB05] L. Hartmann, W. Dür, and H. J. Briegel. Steady state entanglement in open and
noisy quantum systems at high temperature. quant-ph/0512219, 2005.
[HEB04] M. Hein, J. Eisert, and H. J. Briegel. Multi-party entanglement in graph states.
Physical Review A, 69, 2004.
[JL04] P. Jorrand and M. Lalire. Toward a quantum process algebra. In Proceedings of the
1st ACM Conference on Computing Frontiers. ACM Press, 2004. quant-ph/0312067.
[JP05] P. Jorrand and S. Perdrix. Unifying quantum computation with projective measure-
ments only and one-way quantum computation. In Yuri I. Ozhigov, editor, Quantum
Informatics 2004, volume 5833 of SPIE Proceedings, 2005.
[KPA06] A. Kay, J. K. Pachos, and C. S. Adams. Graph-state preparation and quantum
computation with global addressing of optical lattices. Physical Review A, 73, 2006.
[Leu04] D. W. Leung. Quantum computation by measurements. International Journal of
Quantum Information, 2(1), 2004.
[MP04] M. Mhalla and S. Perdrix. Complexity of graph state preparation. quant-ph/0412071,
2004.
[NC00] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information.
Cambridge University Press, 2000.
[Nie03] M. A. Nielsen. Universal quantum computation using only projective measurement,
quantum memory, and preparation of the 0 state. Physical Review A, 308, 2003.
http://arxiv.org/abs/quant-ph/0512110
http://arxiv.org/abs/quant-ph/0409052
http://arxiv.org/abs/quant-ph/0512219
http://arxiv.org/abs/quant-ph/0312067
http://arxiv.org/abs/quant-ph/0412071
[Nie04] M. A. Nielsen. Optical quantum computation using cluster states. Physical Review
Letters, 93, 2004.
[Ö01] B. Ömer. Procedural quantum programming. In Proceedings of the AIP Conference
on Computing Anticipatory Systems (AIP Conference Proceedings 627). American
Institute of Physics, 2001.
[Per95] A. Peres. Quantum Theory: Concepts and Methods. Kluwer Academic, 1995.
[Per03] S. Perdrix. State transfer instead of teleportation in measurement-based quantum
computation. International Journal of Quantum Information, 3(1), 2003.
[PJ04] S. Perdrix and P. Jorrand. Measurement-based quantum turing machines and their
universality. quant-ph/0404146, 2004.
[Pre98] J. Preskill. Fault-tolerant quantum computation. In H. K. Lo, S. Popescu, and
T. P. Spiller, editors, Introduction to Quantum Computation and Information. World
Scientific, 1998.
[RAB04] R. Raussendorf, S. Anders, and H. J. Briegel. Fault-tolerant quan-
tum computation using graph states. Communication to the Quantum
Information and Quantum Control Conference, Fields Institute, Toronto.
http://atlas-conferences.com/c/a/n/n/80.htm, 2004.
[RB01] R. Raussendorf and H. J. Briegel. A one-way quantum computer. Physical Review
Letters, 86, 2001.
[RB02] R. Raussendorf and H. J. Briegel. Computational model underlying the one-way
quantum computer. Quantum Information & Computation, 2, 2002.
[RBB03] R. Raussendorf, D. E. Browne, and H. J. Briegel. Measurement-based quantum
computation on cluster states. Physical Review A, 68, 2003.
[Sch03] D. Schlingemann. Cluster states, algorithms and graphs. quant-ph/0305170, 2003.
[Sel04a] P. Selinger, editor. Proceedings of the 2nd International Workshop on Quantum
Programming Languages, TUCS General Publications, 2004.
[Sel04b] P. Selinger. Towards a quantum programming language. Mathematical Structures in
Computer Science, 14(4), 2004.
[Sel04c] P. Selinger. Towards a semantics for higher-order quantum computation. In Pro-
ceedings of the 2nd International Workshop on Quantum Programming Languages
[Sel04a].
[Sel05a] P. Selinger. Dagger compact closed categories and completely positive maps. In
Proceedings of the 3nd International Workshop on Quantum Programming Languages
[Sel05b].
[Sel05b] P. Selinger, editor. Proceedings of the 3nd International Workshop on Quantum
Programming Languages, Electronic Notes in Theoretical Computer Science, 2005.
http://arxiv.org/abs/quant-ph/0404146
http://atlas-conferences.com/c/a/n/n/80.htm
http://arxiv.org/abs/quant-ph/0305170
[Sho94] P. W. Shor. Algorithms for quantum computation: Discrete logarithms and factor-
ing. In Proceedings of FOCS’94 – Symposium on Foundations of Computer Science.
LNCS, 1994.
[SV05] P. Selinger and B. Valiron. A lambda calculus for quantum computation with classical
control. In Proceedings of the 7th International Conference on Typed Lambda Cal-
culi and Applications (TLCA), volume 3461 of Lecture Notes in Computer Science.
Springer, 2005.
[SW04] B. Schumacher and R. F. Werner. Reversible quantum cellular automata.
quant-ph/0405174, 2004.
[SZ00] J. W. Sanders and P. Zuliani. Quantum programming. In Mathematics of Program
Construction, volume 1837 of Lecture Notes in Computer Science. Springer, 2000.
[TPKV04] M. S. Tame, M. Paternostro, M. S. Kim, and V. Vedral. Toward a more economical
cluster state quantum computation. quant-ph/0412156, 2004.
[TPKV06] M. S. Tame, M. Paternostro, M. S. Kim, and V. Vedral. Natural three-qubit inter-
actions in one-way quantum computing. Physical Review A, 73, 2006.
[Unr05] D. Unruh. Quantum programs with classical output streams. In Selinger [Sel05b].
[vD96] W. van Dam. Quantum cellular automata. Master’s thesis, Computer Science Ni-
jmegen, 1996.
[vT04] A. van Tonder. A lambda calculus for quantum computation. SIAM Journal on
Computing, 33(5), 2004.
[Wat95] J. Watrous. On one-dimensional quantum cellular automata. In Proceedings of
FOCS’95 – Symposium on Foundations of Computer Science. LNCS, 1995.
[WkJRR+05] P. Walther, k. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. As-
pelmeyer, and A. Zeilinger. Experimental one-way quantum computing. Nature, 434,
2005.
A Background on Quantum Mechanics and Quantum Computa-
We give a brief summary of quantum mechanics and quantum computing. We develop some of
the algebra, define some notations, and prove a couple of equations which we have used in the
paper. Although the paper is self-contained, the reader will find the expository book of Nielsen and
Chuang [NC00] useful for quantum computation or the excellent book by Peres [Per95] for general
background on quantum mechanics.
http://arxiv.org/abs/quant-ph/0405174
http://arxiv.org/abs/quant-ph/0412156
A.1 Linear Algebra for Quantum Mechanics
We assume that the reader is familiar with the basic notion of a vector space. In quantum mechanics
we always consider vector spaces over the complex numbers. For quantum computation the vector
spaces are always finite dimensional. The vector spaces that arise in quantum mechanics are Hilbert
spaces and are thus usually written H; that is they have an inner product usually written 〈u, v〉
where u and v are vectors. The inner product is a map from H×H to the complex numbers C. The
inner product is linear in the second argument but anti -linear in the first argument. In general,
there is a topological completeness condition on Hilbert spaces but, in the finite dimensional case
this is automatic and we will ignore it.
Following Dirac, it is customary to call elements of H kets and write them in the form |u〉 or
whatever symbol is appropriate inside the half-bracket. The dual vectors are called bras and are
written 〈v|; the pairing thus can naturally be identified – conceptually and notationally – with the
inner product.
Linear operators come naturally with vector spaces; a linear operator is a linear map from
a vector space to itself. Linear operators on finite dimensional spaces are often represented as
matrices. The most important notion for an operator on a Hilbert space is that of an adjoint.
Definition 17 If A : H → H′ is a linear operator then the adjoint, written A†, is a linear operator
from H′ to H such that
∀u ∈ H′, v ∈ H〈u,Av〉 = 〈A†u, v〉.
In terms of matrices this just amounts to transposing the matrix and complex conjugation each
of the matrix entries; sometimes this is called the hermitian conjugate. An inner product preserving
linear map is called a unitary embedding. When H = H′ we can also define the following operators. A
hermitian operator A is one such that A = A† and a unitary operator U is one such that U−1 = U †.
A projection P is a linear operator such that P 2 = P and P = P †. A projection operator can be
identified with a subspace, namely its range. The eigenvalues of a hermitian operator are always
real. Suppose U is a unitary, and P a projection, then UPU † is also a projection.
It is common to use the Dirac notation to write projection operators as follows: given a vector
|a〉 of unit norm, the projection onto the subspace spanned by |a〉 is written |a〉〈a|. To see why this
makes sense, suppose that |b〉 is another vector then its component along |a〉 is the inner product
〈a, b〉. Now if we just juxtapose the expressions |a〉〈a| and |b〉 we get |a〉〈a, b〉, viewing the 〈a, b〉 as
a number and moving it to the front we get 〈a, b〉|a〉 as the result, which is the right answer for the
projection of |b〉 onto |a〉. Thus one can apply the projection operator just by juxtaposing it with
the vector. This kind of suggestive manipulation is part of the appeal of the Dirac notation.
One important fact – the spectral theorem for hermitian operators – states that if M is a
hermitian operator, λi are its eigenvalues and Pi are projection operators onto the corresponding
eigenspaces then one can write
λiPi.
If we have |i〉 as the normalized eigenvectors for the eigenvalues λi then we can write this in Dirac
notation as:
λi|i〉〈i|.
Finally we need to combine Hilbert spaces.
Definition 18 Given two Hilbert spaces H with basis vectors {ai|1 ≤ i ≤ n} and H′ with basis
{bj |1 ≤ j ≤ m} we define the tensor product, written H⊗H′, as the vector space of dimension n ·m
with basis ai ⊗ bj .
There are more elegant, basis-independent ways of describing the tensor product but this definition
will serve our needs. We almost never write the symbol ⊗ between the vectors. In the Dirac
notation this is always omitted and one writes, for example, |uv〉 instead of |u〉 ⊗ |v〉.
The important point is that there are vectors that cannot be written as the tensor product of
vectors. For example, we can write a1 ⊗ b1 + a2 ⊗ b2 where the ai and the bi are basis vectors of
two 2-dimensional Hilbert spaces. This means that given a general element of H ⊗ H′ one cannot
produce elements of H and H′; this is very different from the cartesian product of sets. This is the
mathematical manifestation of entanglement.
A very important function on square matrices is the trace. The usual trace – i.e. the sum of
the diagonal entries – is basis independent and is actually equal to the sum of the eigenvalues,
counted with multiplicity. The trace of A is written tr(A) and satisfies the cyclicity property
tr(AB) = tr(BA); applying this repeatedly one gets
tr(A1 . . . An) = tr(Aσ(1) . . . Aσ(n))
where σ is a cyclic permutation. The explicit formula for the trace of A : V → V is tr(A) =
i〈i|A|i〉 where |i〉 is a basis for V .
One often needs to compute a partial trace. Consider a linear map L : V ⊗ W → V ⊗W .
Suppose that |vi〉 is a basis for V and |wi〉 is a basis for W then |viwj〉 is a basis for V ⊗W . Now
we can define the partial trace over V as
trV (A) : W → W =
〈vi|A|vi〉.
This corresponds to removing the V dependency; often we use the phrase “tracing out the V
component.”
A.2 Quantum Mechanics
We state the basic facts of quantum mechanics and will not discuss the experimental basis for this
framework. The key aspects of quantum mechanics are:
• the states of a quantum system form a Hilbert space,
• when two quantum systems are combined, the state space of the composite system is obtained
as the tensor product of the state spaces of the individual systems, and
• the evolution of a quantum system is given by a unitary operator, and
• the effect of a measurement is indeterminate.
The first says that one can form superpositions of the states. This is one of the most striking
features of quantum mechanics. Thus states are not completely distinct as they are in classical
systems. The inner product measures the extent to which states are distinct. The fact that systems
are combined by tensor product says that there are states that of composite systems that cannot
be decomposed into individual pieces. This is the phenomenon of entanglement or non-locality.
Measurement is what gives quantum mechanics its indeterminate character. The usual case,
called projective measurements, is when the quantity being measured is described by a hermitian
operator M . The possible outcomes are the eigenvalues of M . If M is an observable (hermitian
operator) with eigenvalues λi and eigenvectors |φi〉 and we have a generic state |ψ〉 =
i ci|φi〉
then the probabilities and expectation values of the measurement outcomes are given by:
• Prob(λi||ψ〉) = |ci|2
• E[M ||ψ〉] =
i |ci|2λi =
i cic̄i〈φi,Mφi〉 = 〈ψ,Mψ〉.
It is important to note that the effect of the measurement is that the projection operator Pi
is applied when the result λi is observed. The operator M does not describe the effect of the
measurement.
The formulas above reveal that no aspect of a measurement is altered if the vector describing
a quantum state is multiplied by a complex number of absolute value 1. Thus we can multiply
a state by eiθ without changing the state. This is called changing the phase. While the phase is
not important phase differences are very important. Multiplying a vector by a complex number
is a change of phase as well as a change in its length. Usually we normalize the state so that we
can read the results of measurements as probabilities. Given a vector the subspace spanned by it -
always one dimensional – is called a ray. Thus a state is really a ray rather than a vector. However,
it is customary to blur this distinction.
A.3 Some qubit algebra
Quantum computation is carried out with qubits the quantum analogues of bits. Just as a bit
has two possible values, a qubit is a two dimensional complex Hilbert space, in other words it is
(isomorphic to) the two dimensional complex vector space C2.
One works with a preferred basis, physically this corresponds to two distinguishable states, like
“spin up” and “spin down”. One writes |0〉, and |1〉 for its canonical basis, so that any vector ψ
can be written as α|0〉 + β|1〉 with α, β in C. Furthermore, C2 can be turned into a Hilbert space
with the following inner product:
〈α|0〉 + β|1〉, α′|0〉+ β′|1〉〉 := α⋆α′ + β⋆β′
where α⋆ is the complex conjugate of α. One then obtains the norm of a vector as:
‖ψ‖ := 〈ψ,ψ〉
2 = (α⋆α+ β⋆β)
Given V a finite set, one writes HV for the Hilbert space ⊗u∈VC2; the notation means an n-fold
tensor product of the C2 where n is the size of V . A vector in HV is said to be decomposable if
it can be written ⊗u∈V ψu for some ψu ∈ C2. Such decomposable vectors will be written ǫ in the
sequel. Decomposable vectors can be represented by a map from V to C2, and we will use both
notations depending on which is more convenient. As we have noted before there are some vectors
that are not decomposable.
As in the case of C2, there is a canonical basis for HV , sometimes also called the computational
basis, containing decomposable vectors ǫ such that for all v ∈ V , ǫ(v) = |0〉 or ǫ(v) = |1〉.
The inner product on HV , according to the general definition given above, is defined on decom-
posable vectors as:
〈ǫ, ǫ′〉 :=
v∈V 〈ǫ(v), ǫ′(v)〉
Note that all vectors in the computational basis are orthogonal and of norm 1. The vectors of norm
1 are usually called unit vectors; we always assume that states are described by unit vectors as
noted before.
Here are some common states that arise in quantum computation:
|0〉 = | ↑〉 =
, |1〉 = | ↓〉 =
, |+〉 =
, |−〉 =
It is easy to see that a linear operator is unitary if it preserves the inner product and hence the
norm. Thus unitaries can be viewed as maps from quantum states to quantum states.
Some particularly useful unitaries are the Pauli operators given by the following matrices in the
canonical basis of C2:
, Y =
, Z =
We note that all these operators are involutive, self-adjoint, and therefore unitaries. All these
matrices have determinant = −1. We will not discuss the geometric significance of these operators
here; their real importance in quantum mechanics comes from the fact that they can be used to
describe rotations, thus they are usually called the “Pauli spin matrices” by physicists.
Some basic algebra of these matrices are given below. First they all square to the identity.
X2 = Y 2 = Z2 = I.
The Pauli operators do not commute. We use the notation [A,B] for AB − BA, the commutator
of A and B. The commutator measures the extent to which two operators fail to commute: it is
customary to present the algebra of operators using it. One also uses the symbol {A,B} to stand
for AB + BA: it is called the anti-commutator. For the Pauli operators we have the following
commutators and anti-commutators :
XY = iZ Y X = −iZ [X,Y ] = 2iZ {X,Y } = 0
ZX = iY XZ = −iY [Z,X] = 2iY {Z,X} = 0
Y Z = iX ZY = −iX [Y,Z] = 2iX {Y,Z} = 0
Definition 19 Define the Pauli group, Pn, as the group consisting of tensor products of I, X, Y,
and Z on n qubits, with an overall phase of ±1 or ±i.
Given a group G the operation x 7→ g−1xg is called conjugation by g. These conjugations
give the effect of switching operators around. If G is a group and H is a subgroup of G then the
normalizer of H is another subgroup of G, say K, with the property that for all h ∈ H, k ∈ K we
have k−1hk in H.
The effect of conjugating measurements and other corrections by Pauli operators is a key part
of the rewrite rules described in the main text. They can be verified using the algebra given here.
A very important related group is called the Clifford group.
Definition 20 The Clifford group, Cn, is the group of unitary operators that leave the Pauli group
invariant under conjugation, i.e. it is the normalizer of the Pauli group viewed as a subgroup of the
unitary group.
The Clifford group on n qubits can be generated by the Hadamard transform, the controlled-X
(CNOT ) or controlled-Z (∧Z), and the single-qubit phase rotation:
H = 1√
, CNOT =
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
, ∧Z =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 −1
, P =
The importance of the Clifford group for quantum computation is that a computation consisting
of only Clifford operations on the computational basis followed by final Pauli measurements can be
efficiently simulated by a classical computer, this is the Gottesman-Knill theorem [Got97, NC00].
A.4 Density Matrices
In order to capture partial information about quantum systems one uses density matrices. Before
we describe density matrices we review some linear algebra in the bra-ket notation. Given a ket |ψ〉
the notation |ψ〉〈ψ| denotes the projection operator onto the one dimensional subspace spanned by
|ψ〉. To verify this note that
(|ψ〉〈ψ|)(|ψ〉 = |ψ〉‖ψ‖ = |ψ〉
(|ψ〉〈ψ|)(|φ〉) = |ψ〉〈ψ|φ〉 = 〈ψ|φ〉|ψ〉.
If |ψi〉 is an orthonormal basis for H the identity matrix is written
i |ψi〉〈ψi|. If Q is a linear
operator with eigenvalues qi and eigenvectors |qi〉, which form an orthonormal basis for H, we can
represent Q as
i qi|qi〉〈qi|. To see this, let |ψ〉 =
i ci|qi〉 then
Q|ψ〉 =
ciQ|qi〉 =
ciqi|qi〉
now using our representation for Q we calculate
Q|ψ〉 =
qi|qi〉〈qi|(|ψ〉) =
cjqi|qi〉〈qi|qj〉 =
ciqi|qi〉.
This is a version of the spectral theorem that we mentioned in the first subsection of this
appendix.
A state (i.e. a ray in H) is called a pure state. If a and b are distinct eigenvalues of some
observable A with corresponding eigenvectors |a〉 and |b〉 it is perfectly possible to prepare a state
of the form 1√
(|a〉 + |b〉). A measurement of A on such a state will yield either a or b each with
probability 1
. However, it is also possible that a mixture is prepared. That is to say instead of
a quantum superposition a classical stochastic mixture is prepared. In order to describe these we
will use density matrices.
For a system in a pure state |ψ〉, the density matrix is just the projection operator |ψ〉〈ψ|. If
we have an observable Q with eigenvalues qi – assumed nondegenerate for simplicity – then we can
expand |ψ〉 in terms of the eigenvectors by
|ψ〉 =
ci|qi〉.
Now the probability of observing qi when measuring Q in the state |ψ〉 is |〈qi|ψ〉|2. Recalling that
the identity is given by I =
j |qj〉〈qj | we get that
Prob(qi, |ψ〉) =
〈qi|ψ〉〈ψ|qj〉〈qj|qi〉
which after rearranging and using the definition of trace of an operator yields
Tr((|qi〉〈qi|)(|ψ〉〈ψ|)).
If as is typical we write ρψ for the density matrix and Pi for the projection operator onto the
subspace spanned by the eigenvector |qi〉 we get
Prob(qi, |ψ〉) = Tr(Piρ).
It is an easy calculation to show that the expectation value for Q in the state |ψ〉 is Tr(Qρ).
What if the state is not known completely? Suppose that we only know that a system is one of
several possible states |ψ1〉, . . . , |ψk〉 with probabilities p1, . . . , pk respectively. We define the density
matrix for such a state to be
pi|ψi〉〈ψi|.
The same formulas for the probability of observing a value qi , i.e. Tr(Piρ) and for the expectation
value of Q, i.e. Tr(Qρ) apply. One can check directly that a density matrix has the following two
properties.
Proposition 21 An operator ρ on H is a density matrix if and only if
• ρ has trace 1 and
• ρ is a positive operator, which means that it has only positive eigenvalues or, equivalently,
that for any x ∈ H we have 〈x, ρx〉 ≥ 0.
Furthermore, if ρ is a density operator, Tr(ρ2) ≤ 1 with equality if and only if ρ is a pure state
(i.e. a projection operator).
Suppose that we have a density matrix ρ describing a pure state of an n+m dimensional system.
Now suppose that an observer can only see the first n dimensions. The density matrix ξ describing
what he can see is contained by taking the partial trace over the m dimensions that the observer
cannot see. Doing this gives, in general, a nonpure state. Similarly a complementary observer who
sees only the m dimensions would construct her density matrix σ by taking the appropriate partial
trace. Taking these traces loses information; in fact, one cannot reconstruct ρ even from both ξ
and σ. Certainly the tensor product of ξ and σ does not give back ρ. This is due to the loss of the
cross-correlation information that was encoded in ρ but is not represented in either ξ or σ.
The axioms of quantum mechanics are easily stated in the language of density matrices. For
example, if evolution from time t1 to time t2 is described by the unitary transformation U and ρ
is the density matrix for time t1, then the evolved density matrix ρ
′ for time t2 is given by the
formula ρ′ = UρU †. Similarly, one can describe measurements represented by projective operators
in terms of density matrices [NC00, Pre98]. Thus if a projector P acts on a state |ψ〉 then the
result is P |ψ〉; the resulting transofrmation of density matrices is |ψ〉〈7→ |P |ψ〉〈P |. For a general
density matrix ρ we have ρ 7→ PρP , note that since P is self-adjoint we do not have to write P †.
A.5 Operations on Density matrices
What are the legitimate “physical” transformations on density matrices? Density matrices are
positive operators and they have trace either equal to 1 if we insist on normalizing them or bounded
by 1. These properties muct be preserved by any transformations on them.
We need first to define what it means for a vector to be positive. Any vector space V can be
equipped with a notion of positivity.
Definition 22 A subset C of V is called a cone if
• x ∈ C implies that for any positive α, αx ∈ C,
• x, y ∈ C implies that x+ y ∈ C and
• x and −x both in C means that x = 0.
We can define x ≥ 0 to mean x ∈ C and x ≥ y to mean x− y ∈ C.
Definition 23 An ordered vector space is just a vector space equipped with a cone.
It is easy to check the following explicitly.
Proposition 24 The collection of positive operators in the vector space of linear operators forms
a cone.
Now we can say what it means for a map to be a positive map.
Definition 25 Abstractly, L : (V,≤V ) → (W,≤W ) is a positive map if
∀v ∈ V. v ≥V 0 ⇒ L(v) ≥W 0.
It is important to not confuse “positive maps” and “positive operators.”
If we are transforming states (density matrices) then the legitimate transformations obviously
take density matrices to density matrices. They have to be positive maps considered as maps
between the appropriate ordered vector spaces. The appropriate ordered vector spaces are the
vector spaces of linear operators on H the Hilbert space of pure states.
Unfortunately the tensor product of two positive maps is not positive in general. We really
want this! If one can perform transformation T1 on density matrix ρ1 and transformation T2 on
density matrix ρ2 then it should be possible to regard ρ1 ⊗ ρ2 as a composite system and carry out
T1 ⊗ T2 on this system. We certainly want this if, say, T2 is the identity. But even when T2 is the
identity this may fail; the usual example is the transposition map, see, for example [NC00].
The remedy is to require the appropriate condition by fiat.
Definition 26 A completely positive map K is a positive map such that for every identity map
In : C
n → Cn the tensor product K ⊗ In is positive.
It is not hard to show that the tensor of completely positive maps is always a completely positive
map. This condition satisfies one of the requirements. We can insist that they preserve the bound
on the trace to satisfy the other requirement as well. However we would like an explicit way of
recognizing this.
The important result in this regard is the Kraus representation theorem [Cho75].
Theorem 7 (Kraus) The general form for a completely positive map E : B(H1) → B(H2) is
E(ρ) =
where the Am : H1 → H2.
Here B(H) is the Banach space of bounded linear operators on H. If, in addition, we require that
the trace of E(ρ) ≤ 1 then the Am will satisfy
A†mAm ≤ I.
The following term is common in the quantum computation literature.
Definition 27 A superoperator T is a linear map from BV to BU that is completely positive and
trace preserving.
	Introduction
	Measurement Patterns
	Commands
	Patterns
	Pattern combination
	The semantics of patterns
	Operational semantics
	Denotational semantics
	Short examples
	Compositionality of the Denotational Semantics
	Universality
	The measurement calculus
	The equations
	The rewrite rules
	Standardization
	Signal shifting
	Examples
	The no dependency theorems
	Other Models
	Phase Model
	Pauli model
	Teleportation
	Embedding
	Conclusion
	Background on Quantum Mechanics and Quantum Computation
	Linear Algebra for Quantum Mechanics
	Quantum Mechanics
	Some qubit algebra
	Density Matrices
	Operations on Density matrices
