Universal MBQC with generalised parity-phase inter-
actions and Pauli measurements
Aleks Kissinger and John van de Wetering
Radboud University Nijmegen
April 17, 2019
We introduce a new family of models for measurement-based quantum com-
putation which are deterministic and approximately universal. The resource
states which play the role of graph states are prepared via 2-qubit gates of
the form exp(−i
π
2
n
Z ⊗ Z). When n = 2, these are equivalent, up to local
Clifford unitaries, to graph states. However, when n > 2, their behaviour di-
verges in two important ways. First, multiple applications of the entangling
gate to a single pair of qubits produces non-trivial entanglement, and hence
multiple parallel edges between nodes play an important role in these gener-
alised graph states. Second, such a state can be used to realise deterministic,
approximately universal computation using only Pauli Z and X measurements
and feed-forward. Even though, for n > 2, the relevant resource states are no
longer stabiliser states, they admit a straightforward, graphical representation
using the ZX-calculus. Using this representation, we are able to provide a sim-
ple, graphical proof of universality. We furthermore show that for every n > 2
this family is capable of producing all Clifford gates and all diagonal gates in
the n-th level of the Clifford hierarchy.
Keywords: Measurement-Based Quantum Computation, ZX-calculus, Clifford hierarchy
1 Introduction
Measurement-based quantum computation (MBQC) describes a family of alternatives to
the quantum circuit model, where one starts with a highly entangled resource state and
performs all computation via measurements. While individual measurements introduce
non-determinism, a deterministic quantum computation can be recovered by allowing
future operations to depend on past measurement outcomes, a concept known as feed-
forward. The most prevalent model of MBQC is the one-way model, first described by
Briegel and Raussendorf [28], which makes use of cluster states or more generally graph
states and single-qubit measurements. Graph states are a family of stabiliser states that
can be described by an undirected graph, where each edge represents a pair of qubits
entangled via a controlled-Z operation. Since they are stabiliser states, any computa-
tion involving just Pauli measurements will be efficiently classically simulable, due to the
Gottesman-Knill theorem [1]. In fact, any computation involving Pauli measurements can
be done in a single time-step [27]. Hence, the entire computational power of the one-way
model comes from introducing non-stabiliser measurements to a computation.
Aleks Kissinger: aleks@cs.ru.nl, https://www.cs.ru.nl/A.Kissinger
John van de Wetering: john@vdwetering.name, http://vdwetering.name
Accepted in Quantum 2019-04-04, click title to verify 1
arXiv:1704.06504v3 [quant-ph] 16 Apr 2019
It is natural to ask if we can invert this problem: is it possible to obtain universal
computation by means of a non-stabiliser resource state and just Pauli measurements?
There are several ways to achieve this. For example, one could consider resource states
which are prepared just like cluster states, but with certain qubits prepared in a |T i magic
state rather than the usual |+i state. One can also consider hypergraph states [13], a gen-
eralisation of graph states produced by multi-qubit n-controlled-Z operations, represented
graphically as hyper-edges. These were recently shown to admit a universal model of com-
putation using Pauli measurements and feed-forward [31]. A different approach was taken
in [22], where a resource state was created that allowed non-deterministic approximately
universal computation using just X, Y and Z measurements.
In this paper, we introduce a new family of generalisations of graph states which
admit universal deterministic computation using only Pauli X and Z measurements and
feed-forward. We call these parity-phase graph states, or P-graph states. Edges in P-graph
states represent an application of the following parity-phase gate, for some fixed angle α:
P (α) = exp(−i
α
2
Z ⊗ Z)
We refer to this as a parity-phase gate because it introduces a relative phase of α between
its even-parity eigenstates |00i, |11i and its odd parity eigenstates |01i, |10i.
We focus on parity-phase gates because they are a popular primitive two-qubit entan-
gling gate in hardware implementations of quantum computation, such as ion trap qubits
(via Mølmer Sørensen gates [4, 14]) and, in transmon-based superconducting qubits [32].
At the end of Section 6, we comment briefly on near-future prospects of implementing this
scheme using the latter.
When α =
π
2
, we obtain resource states which are equivalent to graph states from
the one-way model up to local Clifford operations. However, if α =
π
4
, we can construct
resources which are approximately universal for quantum computation using only single-
qubit Pauli X and Z measurements and feed-forward. We call this the PPM model, for
parity-phase with Pauli measurements.
1
A key feature which distinguishes P-graph states from standard graph states is that,
unlike for controlled-Z gates, P (α)P (α) 6= 1, except in the degenerate case where α = π.
Hence it is possible, and even desirable, to consider resource states described by graphs
with multiple, parallel edges between nodes, e.g.
(1)
These parallel edges correspond to multiple applications of the entangling gate P (α) to
the adjacent qubits. For example, a doubled edge above indicates the application of
P (α)
2
= P (2α). In the graph theory literature, graphs such as (1) are sometimes referred
to as undirected multigraphs.
In the PPM model, doubled edges play a special role. Since P (
π
4
)
2
= P (
π
2
) is equiva-
lent, up to local Clifford operations, to a controlled-Z gate, subgraphs of a P-graph state
containing only doubled edges behave in much the same way as traditional graph states.
However, P-graph states additionally yield the ability to selectively inject π/4 phases into
computations via nodes connected by single edges. One way to conceptualise this fact is
to consider the two-qubit gates P (π/4) as introducing ‘virtual’ magic states between pairs
1
Note that, in a previous version of this article, this model was referred to as MSPM, for Mølmer-
Sørensen with Pauli measurments.
Accepted in Quantum 2019-04-04, click title to verify 2
of qubits. The phase data carried by this ‘virtual’ magic state can either be destroyed
or injected on to one of the neighbouring qubits, depending on the measurement choices,
using a method similar to e.g. Ref. [5].
Notably, this dichotomy gives a clean separation of the efficiently simulable parts of the
computation and the rest. In deriving a universal scheme for computation with P-graph
states, we will note the feed-forward is only required in the vicinity of single edges. So,
much like the case in the one-way model, the entire ‘Clifford’ part of the computation can
be done in a single time step.
We make use of the ZX-calculus [8] for representing and reasoning about P-graph
states. This is a formalism for representing quantum states as certain tensor networks,
called ZX-diagrams, as well as a set of rules for transforming and simplifying ZX-diagrams.
In some sense, it can be regarded as an enhanced version of the stabiliser formalism, in
that any stabiliser state (or Clifford circuit) can be described as a ZX-diagram, and if
two such states/circuits are equal, then one can be efficiently transformed into the other
by means of the ZX-calculus [2]. However, the ZX-calculus goes beyond the stabiliser
formalism in that arbitrary linear maps between qubits can be described as ZX-diagrams.
It was recently shown that two ZX-diagrams describing the same linear map can always
be transformed into one another using an extended version of the ZX-calculus (albeit not
necessarily efficiently) [18, 24]. Our usage of the calculus lies somewhere between these
two extremes: we will use the ZX-calculus to efficiently manipulate certain well-behaved
families of non-stabiliser states.
In particular, we use a variation of the translation from graph states and measurement
patterns into ZX-diagrams given by Duncan and Perdrix [11] to prove the correctness of
our computation scheme. Much like in their work, and in standard approaches to MBQC,
we will demonstrate the possibility of deterministic computation by ‘pushing’ Pauli errors
forward from measurements to qubits in future, which can be corrected. However, unlike
previous work, we rely on the extra flexibility of ZX-diagrams to represent non-stabilizer
correlations between qubits and develop techniques for ‘pushing’ errors through these edges
using the diagrammatic language. As we shall see, the diagrams keep track of the extra
(Clifford) errors introduced by propagating errors forward, and it enables us to derive a
technique for performing Pauli and Clifford corrections purely by means of single-qubit
measurement choices in the bases {X, Z}. This yields a measurement-based model which
is very flexible. To give some evidence of this flexibility, we show in Section 7 how to
generalise to P-graph states where a single edge denotes an application of P (
π
2
n−1
). This
enables us to incorporate a familiar ‘trick’ (see e.g. [16, Section III]) into the model to
deterministically implement any diagonal gate of the n-th level of the Clifford hierarchy.
Related work. To give a proof of universality, we introduce ‘hairy brickwork states’,
which are inspired by the brickwork states introduced in Ref. [6] for universal computation
in the one-way model. Alternatives to the one-way model have been considered, notably in
a broad range of models by Gross et al [17], which include a variation on graph states called
weighted graph states, whose two-qubit interactions are equivalent to P (α) for values of α
different from π/2, up to local unitaries. However, our approach is distinct in that we use
very limited measurements and rely on the fact that P-graph states are a more powerful
resource than standard graph states, in spite of having non-maximal entanglement between
some pairs of qubits. Our scheme also has the property of the one-way model that all errors
can be corrected via feed-forward, eliminating the need for ‘trial-until-success’ strategies
used by Ref. [17]. In Ref. [22] a model based on hypergraph states is constructed that only
needs Pauli measurements to become universal, but its structure is more complex than ours
and the protocols used are not deterministic. Deterministic protocols using hypergraph
Accepted in Quantum 2019-04-04, click title to verify 3
states and Pauli measurements have been proposed since the appearance of this article in
preprint, namely those in Refs. [31] and [13]. However, our protocol remains interesting
for several reasons. First, parity-phase interactions are typically more primitive, in that
they have simpler realisations within the gate sets of current hardware proposals. Second,
the universal gate set we produce in our model is Clifford+T (or more generally, Clifford
+ arbitrary diagonal Clifford-hierarchy gates), as opposed to CCZ+Hadamard. While the
latter is also universal, it requires extra overhead for encoding computations in a higher-
dimensional space [29]. Third, and perhaps most importantly, we introduce a drastically
different methodology to existing approaches. This yields a rather flexible family of models
that enable us to explore a variety of multi-qubit interactions and graph topologies. Indeed
it is a topic of active research to extend these techniques to hypergraph-based models,
where the role of the ZX-calculus is played by the recently-introduced ZH-calculus [3].
2 The PPM Model
A P-graph state is described by an undirected graph, where we allow multiple edges
between vertices. In practice, we will only need to consider two cases: either a single edge
or a double edge:
A single edge describes the application of an P(π/4) gate, whereas a double edge describes
the application of an P (π/2) = P (π/4)
2
gate.
A measurement pattern is a P-graph state where each node is labelled by a measurement
expression of the form “b ← φ(a
1
, . . . , a
n
)” where b is a fresh name called the output value
and φ is a classical function from boolean variables a
1
, . . . , a
n
to a single boolean value.
In this case, we say for each a
i
that b depends on a
i
. An MS-pattern is well-founded if
there are no cyclic dependencies between variables, such as in the following pattern:
b ← 0
e ← bc ⊕ d f ← a
a ← 1
c ← 0 d ← 0
These expressions do not have any explicit time-ordering, but there are restrictions on
the order in which measurements can be made, due to dependencies on prior outcomes,
i.e. feed-forward. As a matter of convention, we will typically draw earlier measurements
below later ones, i.e. ‘time’ flows upward.
Computations are performed as follows:
1. A qubit is initialised in the |+i state for each vertex in a P-graph state.
2. For every edge in the graph, P (
π
4
) is applied to the two qubits at its source and
target. In particular, P (
π
2
) = P (
π
4
)
2
is applied to every pair of qubits connected by
a double edge.
3. For a qubit labelled “b ← φ(a
1
, . . . , a
n
)”, where the values a
1
, . . . , a
n
are known,
measure in the X-basis if φ(a
1
, . . . , a
n
) = 0 and the Z-basis otherwise. In either
case, store the measurement result in b.
Accepted in Quantum 2019-04-04, click title to verify 4
4. Optionally, perform some classical post-processing on the measurement results.
As with the one-way model, the two-qubit gates all commute, so the order of application
is irrelevant, leaving only the undirected graph structure.
To show that this model is universal, we will compose smaller patterns into larger ones.
In order to do this, we give a notion of pattern fragment analogous to the notion given
for the one-way model. A pattern fragment is just like a measurement pattern, with the
exception that we additionally identify two (not necessarily disjoint) subsets of vertices
I, O ⊆ V which respectively correspond to inputs and outputs. Inputs correspond to qubits
that can be in an arbitrary state, rather than the fixed state |+i. Outputs correspond to
qubits which remain unmeasured after the application of the pattern-fragment.
Each vertex in I is labelled with an input error expression of the form: “(z, x) ← ”
for fresh variables z and x, which capture whether a Z or X error is being fed forward into
this vertex. Unless the input vertex is also an output, the vertex will also be labelled with
a measurement expression. Measurement choice functions φ in the fragment are allowed to
depend on the input errors as well as other measurements occurring within the fragment.
Each vertex in the output set O is labelled by an expression of the form: “ ← (ζ, ξ)”
consisting of a pair of classical functions ζ, ξ which again can depend on the input errors
and the results of measurements in the pattern fragment. Vertices in O are not measured
so they do not contain a measurement expression.
Here is an example of a pattern fragment where the bottom left qubit is an input, and
the top left qubit is an output:
(z, x) ← ; a ← 0
← (ζ, ξ) e ← b ⊕ x
b ← 1
d ← 0c ← 0
We say a pattern fragment implements a gate G if, for any input state of the form:
X
x
Z
z
|ψi, performing the pattern fragment yields X
ξ
Z
ζ
G |ψi. This extends in the natural
way to gates with multiple input/output qubits:
(X
x
1
Z
z
1
⊗ . . . ⊗ X
x
n
Z
z
n
) |ψi 7→ (X
ξ
1
Z
ζ
1
⊗ . . . ⊗ X
ξ
m
Z
ζ
m
)G |ψi
Composing pattern fragments then results in the composition of their associated gates,
hence it suffices for the sake of universality to show we can implement a universal set of
quantum gates via pattern fragments.
3 ZX-notation
To derive a universal set of measurement patterns for the PPM model, it is convenient to
use ZX-notation, which is a superset of the usual quantum circuit notation. It is used to
depict linear maps from qubits to qubits, put together in the usual way via composition
and tensor product. We will provide a brief overview. For an in-depth reference see
Ref. [9].
The only operations in ZX-notation are swap gates, identities, and special linear maps
called spiders. These come in two varieties, Z-spiders depicted as white dots:
α
...
...
:= |0 ···0ih0 ···0| + e
iα
|1 ···1ih1 ···1|
Accepted in Quantum 2019-04-04, click title to verify 5
and X-spiders depicted as grey dots:
α
...
...
:= |+ ···+ih+ ···+| + e
iα
|−···−ih−···−|
A special case is when spiders have a single input and output, in which case they form
Z-phase and X-phase gates (up to a global phase):
α
= |0ih0| + e
iα
|1ih1| = Z(α)
α
= |+ih+| + e
iα
|−ih−| = X(α)
Note that we adopt the convention for α such that the Pauli Z and X gates are obtained
as Z(π) and X(π), respectively. Another special case is when α = 0, in which case we
omit the label:
...
...
:= |0 ···0ih0 ···0| + |1 ···1ih1 ···1|
...
...
:= |+ ···+ih+ ···+| + |−···−ih−···−|
In particular, when these phaseless spiders have single input and output they are the
identity:
= =
Phaseless spiders can be thought of as a generalisation of the GHZ state to a linear
map. Indeed the Z-spider with 0 inputs and 3 outputs is the usual GHZ state (up to
normalisation):
= |000i + |111i
Furthermore, the |0i and |+i states are just one-legged spiders:
= |0i + |1i ∝ |+i = |+i + |−i ∝ |0i (2)
The |1i and |−i states are these states followed by respectively a Z(π) and X(π) gate:
=
π π
= |0i + e
iπ
|1i ∝ |−i
π π
=
= |+i + e
iπ
|−i ∝ |1i
Note that hence forth we will ignore non-zero scalar factors and we will cease to write ∝
instead of =, as scalar factors will not enter into our calculations.
While spiders are typically non-unitary, and hence not quantum gates, they can be
used to construct a universal family of quantum gates. We already saw Z- and X-phase
gates, while the CNOT gate can be constructed as follows:
CNOT := = =
Note that we can always reverse the direction of a wire connecting two spiders without
changing the value of the linear map, hence we can write the leftmost diagram above
without ambiguity. More generally, diagrams of spiders are less rigid than circuits. Much
Accepted in Quantum 2019-04-04, click title to verify 6
like diagrammatic depictions of tensor networks (e.g. Ref. [26]), any two diagrams of spiders
with the same connectivity and ordering of inputs/outputs describe the same linear map.
The power of the ZX-notation comes from the set of rewrite rules associated to it,
collectively known as the ZX-calculus. The ZX-calculus has a couple of variations. We
will only need a minimal set of rules. The first two are the spider-fusion rules, which says
adjacent spiders of the same colour fuse together, and their phases add:
β
...
...
α
...
...
=
...
...
...
α+β
β
...
...
α
...
...
=
...
...
...
α+β
This implies in particular that Z and X phase gates commute through spiders of the same
colour. Pauli Z and X gates can be pushed through spiders of the opposite colour, but
they change the sign of the angle:
απ
...
=
-α
π
...
π
π
(3)
απ
...
=
-α
π
...
π
π
(4)
We introduce a special notation for the Hadamard gate:
1
√
2
1 1
1 −1
!
=
=
-
π
2
-
π
2
-
π
2
(5)
And of course the Hadamard is self-inverse:
=
The Hadamard gate interchanges the Z and X bases, so that it acts as a colour-changer
for spiders:
α
...
=
α
...
A final property that we will use is the strong complementarity of the Z and X bases
of a qubit, which are captured by the following two diagrammatic rules:
= =
...
...
We will refer to these two rules, respectively, as the exchange rule and the copy rule.
Combining the rightmost equation with the other rules yields a more general version,
for any a ∈ {0, 1} and α ∈ [0, 2π):
...
aπ
...
aπ
aπ
=
α
Accepted in Quantum 2019-04-04, click title to verify 7
β
...
...
α
...
...
=
...
...
...
α+β
(f)
(-1)
a
α
=
aπ
aπ
aπ α
...
...
aπ
(π)
aπ
...
aπ
α
=
...
aπ
(c)
aπ
α
...
=
α
...
(h)
(i)
=
=
(hh)
(x)
=
Figure 1: The rules of the ZX-calculus: spider-(f)usion, (h)adamard, (π)-commutation, (c)opy,
e(x)change, (i)dentity, and (hh)-cancellation. Note these rules hold for all α, β ∈ [0, 2π) and a ∈ {0, 1}
and also with the colours interchanged, due to (h) and (hh).
We summarise all these rules in Figure 1. Note that an extended set of these rules
has been proven to be complete [18, 24], that is, two diagrams represent the same linear
map if and only if they can be rewritten into one another using the rules of the ZX-
calculus. In contrast, the rules of Figure 1 are only complete when restricted to the
Clifford fragment [2].
As a demonstration of rewriting with these rules, let us derive the following equality,
which we will use throughout the paper:
π
2
=
π
2
π
2
=
-
π
2
-
π
2
-
π
2
=
-
π
2
-
π
2
=
-
π
2
=
-
π
2
(h)
(5)
(f) (π) (f)
(6)
The same equation with the colours reversed also holds.
4 PPM in the ZX-calculus
In order to express the PPM model in the ZX-calculus, we give graphical presentations for
the parity-phase gate and for Pauli measurements. Recall that P (α) = exp(−i
α
2
Z ⊗ Z).
It is straightforward to check that as a matrix in the computational basis, we have:
exp(−i
α
2
Z ⊗ Z) = e
−i
α
2
1 0 0 0
0 e
iα
0 0
0 0 e
iα
0
0 0 0 1
If we interchange the third and fourth computational state (|10i and |11i), we obtain (up
to a global phase):
I ⊗ Z(α) =
1 0 0 0
0 e
iα
0 0
0 0 1 0
0 0 0 e
iα
Hence we obtain the parity-phase gate by pre- and post-composing the above matrix with
CNOTs:
P (α) = CNOT(I ⊗ Z(α))CNOT =
α
Accepted in Quantum 2019-04-04, click title to verify 8
This simplifies as a routine calculation in the ZX-calculus (see e.g. Ref. [9]):
α
=
α
α
= =
α
=
α
=
α
(f) (f)
(x) (i)
Hence, we have:
P (α) =
α
(7)
The Pauli Z and X measurements non-deterministically introduce projections onto
their respective eigenstates, namely {h0|, h1|} for Z-measurements and {h+|, h−|} for X-
measurements. Because basis elements of one colour can be expressed as spiders of the
other colour, we can depict measurements as follows:
Z-measure := {
aπ
}
a∈{0,1}
X-measure := {
aπ
}
a∈{0,1}
(8)
The appearance of the ‘virtual qubit’, i.e. the state being input between the two wires
in equation (7) is quite suggestive. We can interpret this node as a magic state that is
waiting to be applied to one of its neighbouring (actual) qubits to introduce a phase. More
specifically, if we prepare the second qubit in the |+i state and then measure it in the
Z basis, we obtain a Z-phase gate Z(±α), with the sign depending on the measurement
outcome:
α
aπ
=
α aπ
=
(-1)
a
α
(-1)
a
α
==
aπ
α α
=
aπ
(f) (i) (f) (π) (f)
If we take α =
π
2
we can rewrite the expression of P(
π
2
) in the ZX-calculus a bit further:
-
π
2
=
π
2
=
-
π
2
==
P (
π
2
)
-
π
2
π
2
-
π
2
π
2
π
2
π
2
(6)
(f)
(5)
(9)
Written in this way it is clear that the gate is equivalent, up to single-qubit Clifford
unitaries to the controlled-Z gate CZ, which is represented in ZX-notation as:
Since P (α)P (β) = P (α + β) we get P (
π
2
) = P(
π
4
)
2
, so that the gate P (
π
4
) is a
√
CZ
gate, up to local unitaries.
Convention. From hence forth, we will typically suppress explicit references to the spider-
fusion rule (f), and assume that spiders of the same colour are (un)fused as necessary.
Similarly, we will suppress references to (i) and (hh) and simply remove 2-legged spiders
and pairs of H gates as they appear, as both are equal to the identity matrix.
Accepted in Quantum 2019-04-04, click title to verify 9
We can now define the translation from P-graph states and patterns to ZX-diagrams,
which is similar in spirit to the one given in Ref. [11] for graph states. Qubits become
white dots with a single output and single/double edges become edges decorated by the
appropriate phases as follows:
C D
B A
7→
D
C
B
A
π
4
π
2
π
2
π
4
π
2
A
C
=
B
D
π
2
It will be convenient to deform the right-hand side to match the topology of the
associated P-graph state, in which case we can drop the qubit labels:
7→
π
4
π
2
π
2
Note that all of the wires with a free end correspond to outputs, so there is no need to
draw them exiting to the right of the diagram.
To compute the result of a measurement pattern, we post-compose with the appropriate
effects {h0|, h1|} for Z-measurements and {h+|, h−|} for X-measurements using equation
(8). This enables us to write patterns (without feed-forward) as a single ZX-diagram:
7→
π
4
π
2
dπ
bπ
cπ
aπ
π
2
c ← 0 d ← 0
b ← 0 a ← 1
We could also represent the feed-forward within the diagram (e.g. by conditionally apply-
ing Hadamard gates to outputs), but for our purposes, it will be simpler just to do some
simple case-distinctions.
Finally, pattern fragments can be expressed by not measuring outputs, and adding a
new input wire for each input:
7→
π
4
π
2
cπ
bπ
aπ
π
2
← (ζ, ξ) c ← 0
(z, x) ← ; b ← 0 a ← 1
(10)
In order to implement a gate G, we should show that the right-hand side above, pre-
composed with possible Pauli errors, implements G followed by some possible Pauli errors.
We can represent the possible Pauli errors as follows:
zπ
X-error :=
x∈{0,1}
xπ
z∈{0,1}
Z-error :=
(11)
Then, giving a deterministic implementation of a gate G amounts to proving that there
exists boolean functions ζ, ξ such that the following equation holds, for all values of the
boolean variables a, b, c, x, z:
Accepted in Quantum 2019-04-04, click title to verify 10
π
4
π
2
cπ
bπ
aπ
π
2
xπ
zπ
=
ξπζπ
G
Remark. The colours play opposite roles in equations (8) and (11). This is a common
theme in the ZX-calculus, and comes from the fact that basis elements of one colour can
be described as spiders of the other colour (cf. equation (2)).
5 Measurement patterns for a universal set of gates
In this section, we will introduce several pattern fragments, and show using the ZX-
calculus that they deterministically implement certain quantum gates. We will start a
simple example, which uses one double-edge to implement an X(π/2) = HSH gate.
Following that, we will show that a single P-graph, with different measurement patterns,
can implement T , H, or S gates. Similarly, we show a different P-graph shape can be
used to selectively implement CZ or S ⊗S. These will be used in the next section to show
universality of the PPM model.
The pattern for an HSH gate is:
7→
π
2
ζπ ξπ
(z, x) ← ; a ← 0
← (ζ, ξ)
where
(
ζ = z ⊕ a
ξ = z ⊕ a ⊕ x ⊕ 1
The bottom qubit is the input of the expression. We always measure it in the X basis
(a ← 0) which gives us a measurement result a. We record the incoming Z and X error
in the variables z and x. The resulting Z error at the end is now z ⊕ a, and the X error
is z ⊕ a ⊕ x ⊕ 1. We can show the correctness of this fragment by performing translation
(10) and reducing using the ZX-calculus:
zπ
xπ
aπ
π
2
=
(z ⊕ a)π
xπ
= =
π
2
(z ⊕ a ⊕ x ⊕ 1)π
(z ⊕ a)π
π
2
-
π
2
(z ⊕ a)π
xπ
xπ
=
-
π
2
(z ⊕ a)π
=
xπ
(z ⊕ a)π
-
π
2
(z ⊕ a)π
(∗∗)(6)
Here equation (∗∗) is the standard Clifford commutation law of S
†
X ∝ XZS
†
. This
commutation follows straightforwardly from (π) and the fact that, for a ∈ {0, 1}, we have
(−1)
a
π
2
=
π
2
+ aπ (mod 2π).
π
2
aπ
(-1)
a
π
2
aπ
=
(π)
π
2
aπ
=
aπ
π
2
+ aπ
aπ
=
(12)
Accepted in Quantum 2019-04-04, click title to verify 11
We will now introduce a more versatile P-graph fragment, shaped like an ‘E’, which
can implement a variety of single-qubit gates. The first pattern fragment in the E-shape
implements a Z(π/4) gate, i.e. a T gate:
(z, x) ← ; a ← 0
← (ζ, ξ) e ← b ⊕ x
b ← 1
d ← 0c ← 0
where
ζ = a ⊕ c ⊕ d ⊕ e ⊕ x ⊕ (b ⊕ z)(c ⊕ d ⊕ z ⊕ 1)
ξ = c ⊕ d ⊕ z ⊕ 1
Note that now the basis in which the qubit e is measured depends on the incoming X
error and one of the measurement results in the pattern fragment itself. Let’s translate
this to the ZX-calculus, ignoring for the moment being the Pauli errors that could be at
the beginning of the fragment:
π
2
π
π
2
π
4
π
2
=
π
2
π
4
π
2
π
2
π
2
π
2
(9)
Now we measure a, c and d in the X-basis and b in the Z-basis, each of which can introduce
a π phase of their respective colour:
π
2
(c ⊕ 1)π
(-1)
a
π
2
π
4
π
2
bπ
=
π
2
(-1)
b
π
4
π
2
(c ⊕ d ⊕ 1)π
=
(-1)
b
π
4
π
2
(a ⊕ c ⊕ d)π
(c ⊕ d ⊕ 1)π
aπ
π
2
dπ
π
2
π
π
2
π
4
π
2
bπ
π
2
dπ
=
cπ
aπ
π
2
(c ⊕ 1)π
(-1)
a
π
2
(-1)
b
π
4
π
2
π
2
dπ
(c)
(π)
dπ
=
π
2
(c ⊕ d ⊕ 1)π
aπ
(-1)
b
π
4
π
2
π
2
=
(h)
π
2
π
2
(-1)
b
π
4
π
2
(c ⊕ d ⊕ 1)π
aπ
=
π
2
(c ⊕ d ⊕ 1)π
(12)
(π)
(∗)
In the step marked by (∗) we have removed the dangling two spider diagram. We are
allowed to do this because we are ignoring scalar factors.
The goal of this pattern is to introduce a π/4 phase. We see that now we either have
π/4 or −π/4. If we measure e in the X-basis, it gets cut off the main structure, but if we
measure it in the Z-basis it introduces an extra π/2 phase. So, if we got π/4 (which is the
case in the previous diagram when b = 0), we measure e in the X-basis:
π
4
π
2
(a ⊕ c ⊕ d)π
(c ⊕ d ⊕ 1)π
eπ
=
(a ⊕ c ⊕ d ⊕ e)π
π
4
(c ⊕ d ⊕ 1)π
=
π
4
π
2
(a ⊕ c ⊕ d)π
(c ⊕ d ⊕ 1)π
eπ eπ
(c)
Accepted in Quantum 2019-04-04, click title to verify 12
and otherwise we measure e in the Z-basis:
=
-
π
4
π
2
(a ⊕ c ⊕ d)π
(c ⊕ d ⊕ 1)π
eπ
(c ⊕ d ⊕ 1)π
-
π
4
(a ⊕ c ⊕ d)π
(-1)
e
π
2
(a ⊕ c ⊕ d ⊕ e)π
(c ⊕ d ⊕ 1)π
=
-
π
4
π
2
=
(a ⊕ c ⊕ d ⊕ e)π
π
4
(c ⊕ d ⊕ 1)π
(c ⊕ d ⊕ 1)π
π
4
=
(c ⊕ d ⊕ 1)π
(a ⊕ e ⊕ 1)π
(π)
(12)
(c ⊕ d ⊕ 1)π
(π)
so that we indeed implement a π/4 Z-rotation with some Pauli X and Z error depending on
the measurement outcomes. In the presence of of some starting Pauli X and Z errors, the
same procedure can be done by being careful to track where the errors spread. Tracking
these errors correctly gives the pattern fragment that we started out with. If we decide to
measure e in the opposite basis (so in the Z basis when b = 0 and the X basis when b = 1),
we can implement a T
†
gate. Classical control determines the sign of our rotations.
Using the same pattern fragment, but with a different set of measurements on the
‘hairs’ of the fragment we can implement some different operators. For instance, the
following pattern fragment gives a Hadamard gate:
(z, x) ← ; a ← 0
← (ζ, ξ) e ← 0
b ← 0
d ← 1c ← 0
where
(
ξ = a ⊕ b ⊕ c ⊕ d ⊕ 1
ζ = c ⊕ d ⊕ e ⊕ 1
Note there is no feed-forward, so we can verify this in a single derivation:
π
2
π
4
π
2
π
2
π
2
aπ
cπ
eπ
bπ
dπ
eπ
-
π
2
(a ⊕ b)π
-
π
2
-
π
2
(c ⊕ d ⊕ 1)π
=
-
π
2
eπ
-
π
2
-
π
2
(c ⊕ d ⊕ 1)π
(c ⊕ d ⊕ 1)π
(a ⊕ b)π
(a ⊕ b ⊕ c ⊕ d ⊕ 1)π
=
(c ⊕ d ⊕ e ⊕ 1)π
π
2
π
4
π
2
π
2
cπ
aπ
π
2
eπ
bπ
dπ
=
π
2
π
4
π
2
π
2
cπ
aπ
dπ
π
2
eπ
bπ
=
(c)
bπ
eπ
π
2
π
2
cπ
(a ⊕ b)π
eπ
(-1)
d
π
2
=
(π)
-
π
2
-
π
2
cπ
(a ⊕ b)π
eπ
(-1)
d
π
2
=
(6)
=
eπ
-
π
2
-
π
2
-
π
2
(c ⊕ d ⊕ 1)π
(12)
=
(a ⊕ b)π
(a ⊕ b)π
(12) (5)
In a similar way we can also produce an S-gate by measuring qubit e in the Z basis and
the rest in the X basis.
The following fragment implements a CZ-gate:
a ← 1
b ← 0
(z
1
, x
1
) ←
← (ζ
2
, ξ
2
)
← (ζ
1
, ξ
1
)
(z
2
, x
2
) ←
where
ξ
i
= x
i
ζ
1
= z
1
⊕ x
2
⊕ a ⊕ b ⊕ 1
ζ
2
= z
2
⊕ x
1
⊕ a ⊕ b ⊕ 1
Accepted in Quantum 2019-04-04, click title to verify 13
By conjugating one side with Hadamard gates we get a CNOT gate, and thus we can use
this gate to achieve universality.
Note that the top and bottom qubits act as both inputs and outputs, so they are
not measured. We measure a in the Z-basis, and b in the X-basis. Writing the resulting
diagram out in ZX-calculus (again ignoring incoming Pauli errors for the moment) we get:
aπ
π
2
π
2
π
2
=
(-1)
a
π
2
bπ
-
π
2
-
π
2
-
π
2
(-1)
a⊕b
π
2
=
-
π
2
bπ
π
2
aπ
π
2
π
2
bπ
=
(6)
(π)
Now we can use the conversion rule for Hadamards (
=
-
π
2
-
π
2
-
π
2
) on the middle
part, giving:
=
-
π
2
-
π
2
-
π
2
(a ⊕ b ⊕ 1)π
(a ⊕ b ⊕ 1)π
=
(a ⊕ b ⊕ 1)π
(a ⊕ b ⊕ 1)π
(a ⊕ b ⊕ 1)π
=
(a ⊕ b ⊕ 1)π
(-1)
a⊕b
π
2
-
π
2
-
π
2
(12) (5)
(h)
Pauli errors propagate through a CZ in the following way:
zπxπ zπxπ
=
xπ
xπ
=
zπ
xπ
xπ
zπ
=
xπ
(π) (h)
and in exactly the same way for the other input. Putting the above derivation together
with this error propagation gives the pattern fragment as specified above.
This pattern fragment implementing CZ has the additional property that if we measure
b in the Z basis instead of the X basis, it disconnects. It doesn’t matter in which basis we
measure a, but let’s take it to be the X basis. This pattern fragment is:
a ← 0
← (x
2
⊕ z
2
⊕ b, x
2
)
← (x
1
⊕ z
1
⊕ b, x
1
)(z
1
, x
1
) ←
(z
2
, x
2
) ←
b ← 1
In ZX notation (ignoring incoming Pauli errors):
π
2
π
2
π
2
=
bπ
aπ
= =
π
2
π
2
aπ
π
2
bπ
bπ
bπ
bπ
π
2
bπ
π
2
π
2
bπ
π
2
bπ
(c) (π)
Hence, the choice of measurement basis for b ‘switches’ the CZ-gate on or off.
Accepted in Quantum 2019-04-04, click title to verify 14
6 Proof of universality
In the previous section, we have constructed a pattern fragment that can implement a T
gate and an H gate depending on the chosen measurements. Combining these, we can
produce H and T , which suffice to approximate any single-qubit unitary. Combining this
with the entangling gate we demonstrated at the end of the previous section suffices for
universality.
It only remains to combine these patterns into a configuration that allows us to combine
them arbitrarily. We will construct a fragment that is a combination of the simple blocks
described above which fits neatly into a 2D square lattice. If we simply compose two of
the ‘E’-shaped blocks from the previous section with a CZ block rotated 90 degrees we
get:
i
1
i
2
o
1
o
2
where the i’s denote inputs and o’s denote outputs.
These bricks however don’t fit together in a square lattice, since there is no useful tiling
we can produce without some qubits overlapping. However, we can solve this problem by
considering a slightly larger brick, where the E-shape on the right is offset downward and
extra double-edges are added to i
1
, i
2
and o
2
:
i
1
i
2
o
1
o
2
∼
=
i
1
i
2
o
1
o
2
We can picture the paths from i
1
to o
1
and i
2
to o
2
as two qubits passing through a circuit.
The E-shapes on the left and the right can be used to apply S, T, or H gates depending
on the choice of pattern. Similarly, the shape connecting the two qubits can be used to
apply CZ or S ⊗S to both qubits. The extra edges will always introduce HSH gates. By
selecting these patterns, we can implement 3 ·3 ·2 different two-qubit unitaries U. When
these are arranged as follows:
U U
UU
U U U
U
··· ···
it is straightforward to verify that we can implement any Clifford+T circuit. Hence, we
obtain a model allowing for universal quantum computation, much like in Ref. [6].
The asymmetry present in the brick allows us to efficiently tile them:
Accepted in Quantum 2019-04-04, click title to verify 15
We see that all locations in a square grid are used. Qubits whose measurement could
potentially depend on prior outcomes are shown in white above. Of those, only the
corrections forming part of the T pattern described rely on feed-forward. Hence all of the
other qubits can be measured simultaneously at the beginning of the computation.
This graph state can be viewed as consisting of lanes which carry the computation
forward, attached to which are ‘hairs’ which introduce extra phases. ‘Shaving off’ all of
the hairs reveals a state that has a somewhat similar structure to the brickwork state from
Ref. [6]:
While our primitive computational ‘brick’ doesn’t seem to be particularly canonical,
the fact that it is missing some edges from a square lattice could have advantages when
thinking about space-limited architectures. For instance, after dropping the extra ‘dummy’
qubits i
1
and o
1
and a bit of folding, the resulting 16-qubit pattern fits into the 17-qubit
‘ninja star’ design of the superconducting chip proposed in [32], which is designed primarily
for implementing a 17-qubit surface code:
This means that a proof of concept for this computational model is potentially close at
hand. Looking at the way the ‘E’-shape implements the T-gate we also see that the middle
‘hair’ is actually not necessary. Removing this qubit allows us to fit a universal brick inside
the superconducting chip of Ref. [25].
Accepted in Quantum 2019-04-04, click title to verify 16
7 Climbing the Clifford hierarchy
The construction of a deterministic feed-forward strategy in the previous sections relies
on the fact that a sign error in a T gate, i.e. a π/4 rotation, can be corrected by applying
a π/2 rotation, and then correcting a sign error in a π/2 rotation by selectively applying
a π rotation. Since such a π rotation can be commuted past all other gates, the resulting
error can be handled at the end of the computation in a classical manner.
We will now show that this works not only for π/4, but for all angles π/2
n
where
2 ≤ n ∈ N. While the P-graphs of the previous sections had a single edge represent a
P (
π
4
) gate, we will now let a single edge represent P(
π
2
n
). If we have k edges between two
vertices then this represents a P(
π
2
n
)
k
= P (
kπ
2
n
) gate. Now consider the following fragment:
(z, x) ← ; a ← 0
← (ζ, ξ) e ← b ⊕ x
b ← 1
c ← 0
..
2
n−1
2
n−1
..
Here the 2
n−1
refers to the amount of wires between the vertices. I.e. this means that
there will be a P (π/2) gate between the qubits there. Let us simplify the corresponding
diagram in the ZX-calculus. We will not yet apply the measurement of the qubit e.
π
2
(c ⊕ 1)π
(-1)
a
π
2
π
2
n
π
2
n−1
bπ
=
(-1)
b
π
2
n
π
2
n−1
aπ
π
2
(c ⊕ 1)π
=
(-1)
b
π
2
n
π
2
n−1
(a ⊕ c)π
(c ⊕ 1)π
π
2
π
2
n
π
2
n−1
bπ
=
aπ
cπ
π
2
π
2
(9)
(h)
(π)
(12)
(π)
If b = 0, then we have the rotation we want, so we can measure the remaining qubit e
in the X basis, and we see that we are left with a π/2
n
rotation with some Pauli error. If
b = 1, however, we will measure e in the Z-basis, and we calculate:
=
-
π
2
n
π
2
n−1
(a ⊕ c)π
(c ⊕ 1)π
eπ
π
2
n
π
2
n−1
(a ⊕ c)π
(c ⊕ e ⊕ 1)π
-
π
2
n−1
=
π
2
n
(-1)
c⊕e⊕1
π
2
n−1
(a ⊕ c)π
(c ⊕ e ⊕ 1)π
-
π
2
n−1
=
π
2
n
-(c ⊕ e ⊕ 1)
π
2
n−2
(a ⊕ c)π
(c ⊕ e ⊕ 1)π
eπ
(π) (π)
If c ⊕ e = 1, then this is the desired computation. Otherwise, we are left with an
unwanted π/2
n−2
rotation. Since this undesired rotation is heralded by the outcome of
a measurement, we can however decide to do a π/2
n−2
in its future to cancel out this
rotation using exactly the same procedure. Trying to do this extra π/2
n−2
rotation could
then introduce an unwanted π/2
n−3
rotation. After n−2 repetitions of this protocol we are
therefore left with a π error that can safely be incorporated into the classical feed-forward.
The relevant concept to understand this kind of iteration of rotations is that of the
Clifford hierarchy. The first level C
1
is defined to be the set of tensor products of the
identity and the Pauli unitaries. The higher levels are then iteratively defined to be
the multiqubit unitaries that send the Pauli unitaries to a lower level of the hierarchy:
Accepted in Quantum 2019-04-04, click title to verify 17
C
n
:= {U | ∀V ∈ C
1
. U V U
†
∈ C
n−1
}. With this definition we can see that C
2
consists
of exactly the usual Clifford operators. While C
1
and C
2
are closed under composition,
the higher levels no longer form groups. In fact, not much is known about the general
structure of the higher sets in the Clifford hierarchy. What we do know however is that the
diagonal unitaries in C
n
always form a group, and that for n ≥ 2 each of these diagonal
elements can be constructed using Clifford operations and the π/2
n−1
Z rotation [10].
Using the above description of a deterministic implementation of a π/2
n−1
rotation we
have therefore found a deterministic measurement-based model that can implement any
diagonal n-th level Clifford operation using just Pauli measurements.
8 Conclusions and further work
We presented a novel family of graph states that lead to approximately universal quan-
tum computation using just measurements in two bases. Furthermore, depending on the
chosen parameter, diagonal gates of arbitrarily high levels of the Clifford hierarchy can be
implemented.
In the scheme we gave, each of the qubits whose measurement depends on previous
outcomes is a correction involved in implementing a single T -gate. Hence, the number of
required measurement/feed-forward cycles is clearly related to the T -depth of the associ-
ated circuit. We intend to make this relationship precise and relate to similar results known
for the one-way model concerning pattern depth and parallelisation of measurements. An-
other avenue of future work is to understand the general properties of feed-forward in
P-graph states. For instance, concepts like Flow and gFlow [7, 21] are likely to apply with
little modification to the ‘double edge’ portion of a P-graph state, so it will be interesting
to see if this can be extended.
This work also highlights a link between the form of a parity-phase gate derived in
equation (7) and quantum computing with magic states. It may be useful to consider if the
representation of Ising-type interactions (i.e. parity-phase gates) as ‘virtual’ magic states
can be exploited for magic state distillation. For instance, on ion trap based architectures,
it is possible to introduce O(n
2
) parity-phase gates in a single time step using an n-qubit
interaction [30]. It is a topic of future work to try to make use of this curious property in
the construction of fault-tolerant protocols.
The interactions needed to make the graph states described in this paper are avail-
able ‘natively’ in both ion trap and superconducting quantum computing hardware which
means proofs of concept could be implemented in a short timeframe. However, given long
turnaround times for quantum measurements and feed-forward, it remains unclear if such
a measurement-based scheme would yield benefits over the circuit model on such architec-
tures. On the other hand, measurement-based schemes have already had some success in
quantum optics [33], where deterministic application of multi-qubit gates remains a sig-
nificant challenge. While the scheme we gave relied on resource states with a very specific
structure, its likely that this could be relaxed using techniques similar to those employed
in producing perfect cluster states from imperfect lattices (e.g. [23]). Furthermore, the use
of multiple kinds of edges between qubits creates a possibility for more multiple successful
outcomes for non-deterministic entangling operations. That is, known errors giving rise to
non-maximal entanglement between pairs of qubits could still yield good resource states
for universal deterministic computation. This could, for example, be exploited in mod-
els of universal quantum computation using linear optical devices and non-deterministic
fusion gates [15].
Another advantage for our approach is the availability of automated tools for reason-
Accepted in Quantum 2019-04-04, click title to verify 18
ing with, and transforming ZX-diagrams. The graphical proof assistant Quantomatic [20]
makes it possible to scale calculations in the style of this paper to large and more elabo-
rate pattern fragments, and the quantum compilation tool PyZX [12, 19]—which uses the
ZX-calculus as a native intermediate representation for computations—can be straightfor-
wardly adapted to produce ZX-based measurement patterns as a target architecture.
Acknowledgements: This work is supported by the ERC under the European Unions
Seventh Framework Programme (FP7/2007-2013) / ERC grant n
o
320571 and AFOSR
grant FA2386-18-1-4028. The authors would like to thank Brian Tarasinksi and Mar-
tin Sepiol for useful discussions about superconducting qubits and the Mølmer-Sørensen
interaction in ion traps, respectively.
References
[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits.
Physical Review A, 70(5):052328, 2004. DOI: 10.1103/PhysRevA.70.052328.
[2] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New
Journal of Physics, 16(9):093021, 2014. DOI: 10.1088/1367-2630/16/9/093021.
[3] Miriam Backens and Aleks Kissinger. ZH: A complete graphical calculus for quantum
computations involving classical non-linearity. arXiv preprint arXiv:1805.02175, 2018.
DOI: 10.4204/EPTCS.287.2.
[4] CJ Ballance, TP Harty, NM Linke, MA Sepiol, and DM Lucas. High-Fidelity Quan-
tum Logic Gates Using Trapped-Ion Hyperfine Qubits. Physical Review Letters, 117
(6):060504, 2016. DOI: 10.1103/PhysRevLett.117.060504.
[5] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford
gates and noisy ancillas. Physical Review A, 71(2):022316, 2005. DOI: 10.1103/Phys-
RevA.71.022316.
[6] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal Blind Quantum
Computation. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual
IEEE Symposium on, pages 517–526. IEEE, 2009. DOI: 10.1109/FOCS.2009.36.
[7] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. Generalized
flow and determinism in measurement-based quantum computation. New Journal of
Physics, 9(8):250, 2007. DOI: 10.1088/1367-2630/9/8/250.
[8] B. Coecke and R. Duncan. Interacting quantum observables: categorical algebra
and diagrammatics. New Journal of Physics, 13:043016, 2011. DOI: 10.1088/1367-
2630/13/4/043016. arXiv:quant-ph/09064725.
[9] B. Coecke and A. Kissinger. Picturing Quantum Processes. Cambridge University
Press, 2017. ISBN 9781107104228. DOI: 10.1017/9781316219317.
[10] Shawn X Cui, Daniel Gottesman, and Anirudh Krishna. Diagonal gates in the
Clifford hierarchy. Physical Review A, 95(1):012329, 2017. DOI: 10.1103/Phys-
RevA.95.012329.
[11] R. Duncan and S. Perdrix. Rewriting Measurement-Based Quantum Computations
with Generalised Flow. In Proceedings of ICALP, Lecture Notes in Computer Science,
pages 285–296. Springer, 2010. DOI: 10.1007/978-3-642-14162-1˙24.
[12] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-
theoretic Simplification of Quantum Circuits with the ZX-calculus. arXiv preprint
arXiv:1902.03178, 2019.
[13] Mariami Gachechiladze, Otfried G¨uhne, and Akimasa Miyake. Changing the circuit-
depth complexity of measurement-based quantum computation with hypergraph
states. arXiv preprint arXiv:1805.12093, 2018.
Accepted in Quantum 2019-04-04, click title to verify 19
[14] JP Gaebler, TR Tan, Y Lin, Y Wan, R Bowler, AC Keith, S Glancy, K Coak-
ley, E Knill, D Leibfried, et al. High-Fidelity Universal Gate Set for Be 9+
Ion Qubits. Physical Review Letters, 117(6):060505, 2016. DOI: 10.1103/Phys-
RevLett.117.060505.
[15] Mercedes Gimeno-Segovia, Pete Shadbolt, Dan E Browne, and Terry Rudolph. From
Three-Photon Greenberger-Horne-Zeilinger States to Ballistic Universal Quantum
Computation. Physical review letters, 115(2):020502, 2015. DOI: 10.1103/Phys-
RevLett.115.020502.
[16] D. Gottesman and I. L. Chuang. Demonstrating the viability of universal quantum
computation using teleportation and single-qubit operations. Nature, 402(6760):390–
393, 1999. DOI: 10.1038/46503.
[17] D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia. Measurement-based quantum
computation beyond the one-way model. Phys. Rev. A, 76:052315, Nov 2007. DOI:
10.1103/PhysRevA.76.052315.
[18] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Complete Axiomatisation
of the ZX-calculus for Clifford+T Quantum Mechanics. In Proceedings of the 33rd
Annual ACM/IEEE Symposium on Logic in Computer Science, pages 559–568. ACM,
2018. DOI: 10.1145/3209108.3209131.
[19] Aleks Kissinger and John van de Wetering. Pyzx: Large scale automated diagram-
matic reasoning. arXiv preprint arXiv:1904.04735, 2019.
[20] Aleks Kissinger and Vladimir Zamdzhiev. Quantomatic: A proof assistant for dia-
grammatic reasoning. In International Conference on Automated Deduction, pages
326–336. Springer, 2015. DOI: 10.1007/978-3-319-21401-6˙22.
[21] Damian Markham and Elham Kashefi. Entanglement, Flow and Classical Simulata-
bility in Measurement Based Quantum Computation, pages 427–453. Lecture Notes in
Computer Science. Springer International Publishing, 2014. ISBN 978-3-319-06879-4.
DOI: 10.1007/978-3-319-06880-0˙22.
[22] Jacob Miller and Akimasa Miyake. Hierarchy of universal entanglement in 2D
measurement-based quantum computation. npj Quantum Information, 2:16036, 2016.
DOI: 10.1038/npjqi.2016.36.
[23] Sam Morley-Short, Sara Bartolucci, Mercedes Gimeno-Segovia, Pete Shadbolt, Hugo
Cable, and Terry Rudolph. Physical-depth architectural requirements for generating
universal photonic cluster states. Quantum Science and Technology, 3(1):015005,
2017. DOI: 10.1088/2058-9565/aa913b.
[24] K. F. Ng and Q. Wang. A universal completion of the ZX-calculus. ArXiv e-prints,
jun 2017.
[25] JS Otterbach, R Manenti, N Alidoust, A Bestwick, M Block, B Bloom, S Caldwell,
N Didier, E Schuyler Fried, S Hong, et al. Unsupervised machine learning on a hybrid
quantum computer. arXiv preprint arXiv:1712.05771, 2017.
[26] R. Penrose. Applications of negative dimensional tensors. In Combinatorial Mathe-
matics and its Applications, pages 221–244. Academic Press, 1971.
[27] R. Raussendorf, D.E. Browne, and H.J. Briegel. Measurement-based quantum com-
putation on cluster states. Physical Review A, 68(2):22312, 2003. ISSN 1094-1622.
DOI: 10.1103/PhysRevA.68.022312.
[28] Robert Raussendorf and Hans J. Briegel. A One-Way Quantum Computer. Phys.
Rev. Lett., 86:5188–5191, May 2001. DOI: 10.1103/PhysRevLett.86.5188.
[29] Yaoyun Shi. Both Toffoli and controlled-NOT need little help to do universal quantum
computation. arXiv preprint quant-ph/0205115, 2002.
Accepted in Quantum 2019-04-04, click title to verify 20
[30] Anders Sørensen and Klaus Mølmer. Quantum computation with ions in thermal
motion. Physical review letters, 82(9):1971, 1999. DOI: 10.1103/PhysRevLett.82.1971.
[31] Yuki Takeuchi, Tomoyuki Morimae, and Masahito Hayashi. Quantum computational
universality of hypergraph states with Pauli-X and Z basis measurements. arXiv
preprint arXiv:1809.07552, 2018.
[32] R Versluis, S Poletto, N Khammassi, N Haider, DJ Michalak, A Bruno, K Ber-
tels, and L DiCarlo. Scalable Quantum Circuit and Control for a Superconducting
Surface Code. arXiv preprint arXiv:1612.08208, 2016. DOI: 10.1103/PhysRevAp-
plied.8.034021.
[33] 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:
169–176, 2005. DOI: 10.1038/nature03347.
Accepted in Quantum 2019-04-04, click title to verify 21