Magic state parity-checker
with pre-distilled components
Earl T. Campbell and Mark Howard
Department of Physics & Astronomy, University of Sheffield, Sheffield, S3 7RH, United Kingdom.
February 23, 2018
Magic states are eigenstates of non-Pauli operators. One way of suppressing
errors present in magic states is to perform parity measurements in their non-
Pauli eigenbasis and postselect on even parity. Here we develop new protocols
based on non-Pauli parity checking, where the measurements are implemented
with the aid of pre-distilled multiqubit resource states. This leads to a two step
process: pre-distillation of multiqubit resource states, followed by implementa-
tion of the parity check. These protocols can prepare single-qubit magic states
that enable direct injection of single-qubit axial rotations without subsequent
gate-synthesis and its associated overhead. We show our protocols are more
efficient than all previous comparable protocols with quadratic error reduction,
including the protocols of Bravyi and Haah.
Error corrected quantum computers require additional gadgets and tricks to enable fully
universal, fault-tolerant quantum computation (see Ref. [1] for a review). Of the various
competing approaches, magic state distillation is especially efficient. At first, magic state
distillation was conceived of as a way to implement the T gate (also called the π/8 phase
gate), with successive generations of protocols making ever greater improvements [2–6].
Any desired unitaries could be approximated by efficient synthesis of T gates and Clifford
gates, with recent years also bringing new, optimised synthesis methods [7–11]. However,
we can circumvent the need for synthesis if we instead prepare magic states tailored for
injecting specific gates. Preparing tailored single qubit magic states can directly provide
single qubit rotations other than the T -gate and distillation routines for these states have
been proposed [12–16]. Complex multi-qubit circuits can also be directly injected once
multi-qubit magic states have been distilled [6, 17–20].
Here we propose a family of two-step protocols for distilling magic states that are
tailored for injecting a desired single-qubit Z-axis rotation. A distinctive feature is that
the first step creates a multi-qubit magic state using the synthillation protocol [19, 20]. In
the second step, this multi-qubit resource is then used to fault-tolerantly perform a parity
check in a non-Pauli basis. Combined, the protocol takes in single qubit states and outputs
single qubit states, with multi-qubit magic states appearing only fleetingly.
A single round of our protocol will quadratically reduce errors using fewer inputs per
output than any previous protocol with quadratic error reduction. Higher order error re-
ductions can be achieved by concatenation of our protocols. Higher order reductions in
noise are possible without concatenation by using sophisticated protocols that give a large
Earl T. Campbell: earltcampbell@gmail.com, https://earltcampbell.com/
Mark Howard: m.howard@sheffield.ac.uk, https://markhoward.info
Accepted in Quantum 2018-02-21, click title to verify 1
arXiv:1709.02214v3 [quant-ph] 22 Feb 2018
error reduction in a single round [5, 6, 21, 22], but there are important practical consider-
ations for why one might favour a concatenated approach (see Sec. 6.2 for a discussion).
We begin by covering some basic notation. Sec. 2 gives an overview of our approach.
Note that the first step is our previously proposed synthillation method [19, 20], so the
details will not be repeated here. Rather we focus on how non-Pauli parity checking is
possible given these pre-distilled resources, giving a detailed explanation in Sec. 3. The
protocol’s performance is analysed in Sec. 4. In Sec. 5, we present a small bonus result
that proves equivalent performance is unlikely to be possible using codes with conventional
transversal gate constructions.
1 Notation
We denote axial rotations about the Pauli-Z axis as
R(θ) = exp(iθZ) = cos(θ)1l + i sin(θ)Z. (1)
If the angle is θ = π/2
`
for integer ` then R(θ) belongs in the `
th
level of the Clifford hier-
archy [23]. Therefore, R(π/8) is the π/8-phase gate, also known at the T gate. Unitaries
inside the Clifford hierarchy are special because they can be realised using state-injection
and a bounded number of appropriate magic states. However, all the analysis in this paper
holds for any θ, even values corresponding to unitaries and magic states not connected to
the Clifford hierarchy.
We use W (θ) for the Hermitian operator W (θ) := R(θ)XR(θ)
†
= R(2θ)X. Note that
W (π/8) is a Clifford and plays a similar role to the Hadamard; it interchanges X and Y
whereas the Hadamard interchanges X and Z. The relevant magic states are eigenstates
of W (θ) and sit on the equator of the Bloch sphere
|R(θ)i = W (θ)|R(θ)i = R(θ)|+i. (2)
More generally, when U is a diagonal gate (acting on n qubits) we use |Ui := U(|+i
⊗n
).
In this notation, the familiar T state is |R(π/8)i. We use CZ for control-Z and CCZ for
control-control-Z.
2 Overview of new protocols
2.1 Protocols for π/8 phase gates
The protocols presented here can be used both for distillation of T -states that can imple-
ment π/8 phase gates, or more generally for distillation of |R(θ)i magic states for smaller
angle rotations. We begin by sketching the simple case of T -state distillation. We say a
protocol is an n → k protocol if it takes n inputs and outputs k magic states with some
success probability (typically this probability approaches unity in the low noise limit).
Our two-step protocols for T -state distillation are 3k + 4 → k protocols for even k with
quadratic reduction of noise. The resource overhead of the protocol is roughly captured by
n/k = 3 +
4
k
, which approaches 3 for large k. For k = 2 we have a 10 → 2 protocol and so
the protocol is very similar to the MEK proposal proposed by Meier, Eastin and Knill [3].
Therefore, compared to MEK, we reduce the n/k overhead from 5 to 3 by going to larger
blocks sizes (larger k). Another class of protocols was proposed by Bravyi and Haah [4],
which are 3k + 8 → k protocols for even k with quadratic reduction of noise. The Bravyi-
Haah protocols also have n/k → 3 in the large protocol limit. Both our protocols and the
Accepted in Quantum 2018-02-21, click title to verify 2
π/8
π/8
π/8
π/8
π/8
π/8
π/8
π/8
π /
8
#
= O(
2
π /8
)
step one: synthillaon
step two: parity check
θ
θ
θ
θ
θ
R(2θ)
η
= O(
2
π /8
+
2
θ
+ η
)
C
|
CCZ
Figure 1: An illustration of how the two steps of our protocol are chained together for the special case
N = 1. The combined process is described in Eq. (9) for general N.
Bravyi-Haah protocols have the same asymptotic limit, but our protocols approach this
limit faster. For example, to achieve n/k = 4 we can use modest size 16 → 4 protocols,
whereas the comparable Bravyi-Haah protocol is 32 → 8 with double the block size. This
effect becomes more pronounced as the protocol is concatenated.
Furthermore, our work presents a different approach to distillation as we break the
process up into two steps, making use of a multi-qubit magic state resource. Let us
describe how this two-step process works, first considering the 10 → 2 case. In the first
step we prepare a “pre-distilled” magic state that can inject a CCZ (or Toffoli) gate. It
has been known for several years that a single CCZ magic state can be prepared from 8
T -states with quadratic error reduction [17, 18]. It is no longer appropriate to describe
this process in simple n → k notation and so we introduce the more detailed description
of these protocols as being
8
|R(π/8)i
π/8
→
1
|CCZi
O(
2
π/8
)
. (3)
In this notation, the left hand side gives the input resources and the right hand size gives
the output resources. The top line gives the quantity of resources, the middle describes
the species of magic state and the bottom line gives the infidelity. Our second step, which
was not previously known, is to notice that a single |CCZi resource can be used to check
Accepted in Quantum 2018-02-21, click title to verify 3
the parity in a pair of |R(π/8)i states, which implements the transform
2 1
|R(π/8)i |CCZi
π/8
#
→
2
|R(π/8)i
O(
2
π/8
+
#
)
. (4)
Chaining these steps together so that
#
= O(
2
π/8
) yields
10
|R(π/8)i
π/8
→
2 1
|R(π/8)i |CCZi
π/8
O(
2
π/8
)
→
2
|R(π/8)i
O(
2
π/8
)
, (5)
or simply 10 → 2 for short.
Next we outline the two-step process for larger block protocols. Instead of using |CCZi
resources, larger block protocols will use a resource that we denote as |CCZ
#N
i. This
resource can inject a gate CCZ
#N
, which is N copies of the CCZ gate all sharing one
control qubit in common, and the relevant magic state is simply
|CCZ
#N
i := CCZ
#N
(|+i
⊗2N+1
). (6)
In the first step, we borrow results on synthillation [19, 20] that provide protocols imple-
menting
4N + 4
|R(π/8)i
π/8
→
1
|CCZ
#N
i
O(
2
π/8
)
. (7)
This protocol is described in the section "U
N#
family" of Ref. [20]. To avoid repetition, here
we simply treat this synthillation routine as a black box with known properties. Rather,
here we focus on the second step — the main technical contribution of this work — by
showing that a pre-distilled |CCZ
#N
i can be used to parity check on 2N magic states
2N 1
|R(π/8)i |CCZ
#N
i
π/8
#
→
2N
|R(π/8)i
O(
2
π/8
+
#
)
. (8)
Chaining steps one and two, so that
#
= O(
2
π/8
), we obtain a family of protocols for all
integer N
6N + 4
|R(π/8)i
π/8
→
2N 1
|R(π/8)i |CCZ
#N
i
π/8
O(
2
π/8
)
→
2N
|R(π/8)i
O(
2
π/8
)
, (9)
or simply 6N + 4 → 2N for short. Alternatively, using k = 2N we have a family of
3k + 4 → k protocols with even k. So we have returned to the choice of symbols used by
Bravyi and Haah who found 3k + 8 → k protocols with even k. Fig. 1 illustrates this for
the N = 1 (k = 2) case. This completes the outline of our protocols for T -state distillation.
Accepted in Quantum 2018-02-21, click title to verify 4
2.2 Protocols for general phase gates
Next, we describe a family of protocols for other equatorial magic states |R(θ)i. Step one
will remain the same, again making use of synthillation of |CCZ
#N
i resource states. Step
two generalises to
2N 1 N
|R(θ)i |CCZ
#N
i R(2θ)
θ
#
η
→
2N
|R(θ)i
O(
2
θ
+
#
+ η)
. (10)
When R(2θ) appears uncluttered by a ket, as it does above, it refers to inputting a phase
gate R(2θ) rather than a magic state. Most interesting is the case when R(2θ) sits in
the Clifford hierarchy and so can be injected using appropriate magic states. Proving the
validity of the above mapping is at the core of this paper. Chaining this with synthillation
yields an overall protocol
2N 4N + 4 N
|R(θ)i |R(π/8)i R(2θ)
θ
π/8
η
→
2N 1 N
|R(θ)i |CCZ
#N
i R(2θ)
θ
O(
2
π/8
) η
→
2N
|R(θ)i
O(
2
θ
+
2
π/8
+ η)
.
(11)
It is important to notice that there is no noise reduction in η. Therefore, it is crucially
important they are predistilled (e.g. η ∼
2
) and so we refer to the rotations R(2θ) as
pivotal. Despite the need for high fidelity pivotal rotations, other protocols have used
pivotal rotations and found significant reductions of resource costs compared against using
gate-synthesis. For instance, the N = 1 two-step protocol has an identical resource cost
to the protocols introduced by Campbell and O’Gorman [15]. Pivotal rotations (though
not under this name) played a similar role in the protocols proposed by Duclos-Cianci and
Poulin [14], which in our notation can be described as
2N 8N + 4 N
|R(θ)i |R(π/8)i R(2θ)
θ
π/8
η
→
2N
|R(θ)i
O(
2
θ
+
2
π/8
+ η)
. (12)
Note that for the majority of their paper, Duclos-Cianci and Poulin only discuss the N = 1
case, but they do sketch the higher N case later in the paper.
One could say our protocols are compressed as they essentially give a slight compression
in T -cost of the Duclos-Cianci and Poulin protocols [14]. Our protocols also have very dif-
ferent inner workings. This provides a new perspective on magic state distillation, but also
the two-step feature has a potentially significant practical advantage. The exotic resources
are higher value since the R(2θ) pivotal rotation and |R(θ)i resources are more difficult to
prepare than standard |R(π/8)i magic states. However, in the two-step protocols, one does
not risk using the exotic resources until the first step has succeeded. This contrasts, with
both the Duclos-Cianci-Poulin protocols and Campbell-O’Gorman protocols for which all
the resources are committed at the same time, with a single error anywhere leading to loss
of all resources.
3 Implementing step two
Here we show how to use CCZ circuits, implemented using synthillation, to perform a
parity check. We will construct circuits that measure the parity of 2N qubits in the basis
Accepted in Quantum 2018-02-21, click title to verify 5
|+
•
H
W (θ)
W (θ)
•
X
•
X H
W (θ)
W (θ)
|+
•
H
W (θ)
W (θ) W(θ)
|+
=
=
(a) two-qubit parity checker
|+
•
•
H
R(2θ)
R(2θ)
R(2θ)
R(2θ)
R(2θ)
.
.
.
.
.
.
.
.
.
.
.
.
|+
H
W(θ)
.
.
.
.
.
.
.
.
.
W(θ)
W(θ)
W(θ)
W(θ)
W(θ)
=
(b) parity checker decomposion
V
Circuit notaon / idenes
control-X
X X
control-Z
(CZ)
control-
control-Z
(CCZ)
measurement
in basis
|
0 ,
|
1
Figure 2: Gadgets for measuring parity in the W (θ) basis. In (a) we illustrate how control-W (θ) gates
are used to measure parity. In (b) we show how the control-W (θ) gates can be decomposed into CNOT
and control-phase gates. In the text we describe this phase-gate circuit by V (see Eq. (14)), which can
be broken up into a product of U
j
gates (see Eq. (17)).
Accepted in Quantum 2018-02-21, click title to verify 6
of W (θ). Using an ancilla and a control-W(θ)
⊗2N
gate would achieve this, but a smaller
resource overhead is needed if we instead use the parity check gadgets in Fig. 2. We use
a combination of control-W (θ) that triggers when the control bit is in the |1i state with
an unconventional control-W(θ) (shown with open circles) that triggers when the control
bit is in the |0i state. This parity check gadget measures in the W (θ) basis, but with an
additional W (θ) rotation on half the qubits. This resulting Kraus operator for the desired
even parity outcome is
K =
1
2
(1l
⊗N
⊗ W (θ)
⊗N
+ W (θ)
⊗N
⊗ 1l
⊗N
)
=
1
2
(1l
⊗N
⊗ W (θ)
⊗N
)(1l
⊗2N
+ W (θ)
⊗2N
). (13)
We assume the noisy |R(θ)i magic states are diagonal in the W(θ) basis, and so the
additional W (θ) rotations have no effect. The assumption of diagonal noise is mild and
can be removed at the expense of hideously complicating the noise analysis (see e.g. App
D of Ref. [15]).
Using W (θ) = R(2θ)X it follows that this parity measurement circuit can be split into
a sequence of control-X gates followed by a phase gate circuit (see Fig. 2b). Algebraically,
this phase gate circuit is
V =
Y
j=1,...,N
[|0ih0|
0
R
2j
(2θ) + |1ih1|
0
R
2j−1
(2θ)] , (14)
where the subscripts denote which qubits the rotations act on, with qubit labels running
from 0 to 2N. Using the shorthand
U
j
:= |0ih0|
0
R
2j
(2θ) + |1ih1|
0
R
2j−1
(2θ), (15)
we have
V =
Y
j=1,...,N
U
j
. (16)
To recap, given |R(θ)i of error rate and the ability to implement V we can parity check in
the W (θ) basis, outputting |R(θ)i of error rate O(
2
) with some probability p = 1 − O().
Next, we show how to implement V with some pre-distilled resources. First, we use
the decomposition R(2θ) = cos(2θ)1l + i sin(2θ)Z to expand out U
j
as
U
j
=|0ih0|
0
(cos(2θ)1l + i sin(2θ)Z
2j
) + |1ih1|
0
(cos(2θ)1l + i sin(2θ)Z
2j−1
). (17)
Collecting the cos and sin terms, we have
U
j
= cos(2θ)1l + i sin(2θ)[|0ih0|
0
Z
2j
+ |1ih1|
0
Z
2j−1
] (18)
= cos(2θ)1l + i sin(2θ)M
j
,
where we have introduced further shorthand
M
j
:= |0ih0|
0
Z
2j
+ |1ih1|
0
Z
2j−1
= Z
2j
(|0ih0|
0
+ |1ih1|
0
Z
2j
Z
2j−1
)
= Z
2j
CZ
0,2j
CZ
0,2j−1
, (19)
which is unitary, Hermitian and Clifford.
Accepted in Quantum 2018-02-21, click title to verify 7
=
U
j
|+ •
HR(2θ)H
Z
=
•
R(2θ)
0
2j − 1
2j
2j − 1
2j
0
−j
M
j
coherently
controlled
M
j
classically
controlled
• •
•
•
• •
• •
•
•
•
=
• •
•
•
•
• •
•
•
•
=
•
•
•
•
• •
•
•
=
•
•
•
•
• •
•
•
CCZ#2
(a) phase-gate decomposion
CCZ
(b) CCZ identy
(c) repeated CCZ identy
R(2θ)
2j − 1
2j
0
−j
0
1
2
3
4
-1
-2
0
2j − 1
2j
Figure 3: In (a) we show how U
j
(a pair of control phase gates) can be implemented using an ancilla,
a control-M
j
gate and a pivotal rotation. An algebraic proof of this equivalence starts at Eq. (17) and
ends after Eq. (23). In (b) we show how a pair of CCZ gates, which share a pair of controls, is Clifford
equivalent to only a single CCZ gate. In (c) we uses this identity twice to simplify a more complex
circuit down to a CCZ
#2
. In general, one finds that a sequence of N control-M
j
can be simplified to
a CCZ
#N
circuit (see Eq. (24) and Eq. (26)).
Next we show that each U
j
can be implemented with access to a single |+i ancilla, a
control-M
j
unitary and a R(2θ) rotation (see Fig. 3a). We prepare the ancilla in the |+i
state and use it as the control qubit for the control-M
j
unitary, which gives the state |0i|ψi+
|1i(M
j
|ψi). Next we rotate the ancilla by HR(2θ)H and measure in the computational
basis. This is equivalent to measuring with projections
h0|HR(2θ)H = cos(2θ)h0| + i sin(2θ)h1| (20)
h1|HR(2θ)H = cos(2θ)h1| + i sin(2θ)h0|. (21)
In the eventuality of a “+1” outcome, we find
|0i|ψi + |1i(M
j
|ψi) → (cos(2θ)1l + i sin(2θ)M
j
)|ψi = U
j
|ψi, (22)
as desired. However, when a “1” outcome is measured we have
|0i|ψi + |1i(M
j
|ψi) → (i sin(2θ)1l + cos(2θ)M
j
)|ψi = M
j
U
j
|ψi. (23)
We see that an M
j
gate will correct for the different measurements outcomes, and since
M
j
is Clifford this does not contribute to the resource cost. This completes the proof of
the identity in Fig. 3a.
Similarly we chain together N such circuits, assuming we have access to N copies of
R(2θ) and the circuit
˜
V =
Y
j=1,...,N
(|0ih0|
−j
+ |1ih1|
−j
M
j
), (24)
=
Y
j=1,...,N
CZ
−j,2j
CCZ
−j,0,2j
CCZ
−j,0,2j−1
. (25)
Accepted in Quantum 2018-02-21, click title to verify 8
This is composed of a sequence of control-M
j
gates, where each gate is controlled from a
different ancillary qubit. We have labelled these new ancilla with negative integers from
−1 to −N. Each control-M
j
consists of a CZ gate and two CCZ gates. On first inspection
this seems to imply 2N CCZ gates are needed. However, using the identity in Fig. 3b we
see a pair of CZZ gates can sometimes be realised using a single CCZ. Note this identity
only works because the pair of CCZ gates share two control bits in common. Applying
this identity repeatedly (see e.g. Fig. 3c) can reduce the circuit to one using only N CCZ
gates. Algebraically, the identity is
˜
V =
N
Y
j=1
CX
2j,2j−1
N
Y
j=1
CCZ
−j,0,2j−1
N
Y
j=1
CX
2j,2j−1
N
Y
j=1
CZ
−j,2j
, (26)
where CX
c,t
is a control-X gate with control qubit c and target qubit t. The resource
intensive part is the non-Clifford component of N CCZ gates all sharing one single control
qubit in common (qubit 0). Here we denote such a circuit as CCZ
#N
, which has been
elsewhere called Tof
#N
. For these gates, the problem of optimal synthesis into CNOT +
T gates has been solved and the circuit requires 4N + 3 T gates (see Example IV.2. of
Ref. [20]). Recall that we are requiring that CCZ
#N
is predistilled to a higher fidelity. The
most efficient known method to achieve this is to use the synthillation protocol that can
perpare CCZ
#N
using only (4N + 4) T -states of
π/8
error rate, and so this is the first-step
of our two-step protocol.
We have demonstrated how step two works using a series of circuit identities (for any
integer N). For completeness, we show in Fig. 4 how these circuit identities plug together
for N = 1 and N = 2. The circuits could be further expanded by replacing the non-Clifford
gate CCZ
#N
with the magic state |CCZ
#N
i and the appropriate Clifford injection circuit.
4 Noise analysis
This section presents a performance analysis for one round of our protocols. Subsection 4.1
reports some results of numerical simulations for smaller size protocols with N = 1 and
N = 2. Subsection 4.2 focuses on providing a simple, yet rigorous derivation, of analytic
upper bounds on output noise. The analytic results hold for all N, but are loose and actual
performance will be much better than analytically bounded.
4.1 Numerical analysis
We performed full state vector numerical simulations using IBM’s QISKit (code available
as ancillary file). We simulated the effect of leading order errors for circuits with N = 1 and
N = 2. The output error probabilities are for a single qubit with other output qubits traced
out. Numerical results were independent of which output qubit is chosen and independent
of θ (up-to numerical accuracy of 2 significant figures).
For N = 1, we found that
0
= 8
2
π/8
+
2
θ
+
1
4
η + O(
3
π/8
,
2
θ
, η
2
, . . .). (27)
The leading order coefficients for output error are identical to those for the MEK
k
protocols
proposed by Campbell and O’Gorman (themselves a modified form of MEK) and so it seems
that our new protocols (with N = 1) perform identically in this regard. We have a slight
Accepted in Quantum 2018-02-21, click title to verify 9
|+ HR(2θ)H
|+
H
ρ(θ )
ρ(θ )
SUCCESS
with +1 outcome
CCZ gate injected
using CCZ magic state
error rate=
CCZ
pivotal rotaon
error rate=
η
{
noisy
magic states
error rate=
output error rate
{
|+ HR(2θ)H
|+
ρ(θ )
ρ(θ )
CCZ#2 gate injected
using CCZ#2 magic state
error rate=
#
two pivotal rotaons
each with error rate=
η
{
|+ HR(2θ)H
ρ(θ )
ρ(θ )
output error rate
{
(b) Protocol overview for
N = 2
(a) Protocol overview for
N = 1
noisy
magic states
error rate=
Circuit notaon / idenes
control-X
X X
control-Z
(CZ)
control-
control-Z
(CCZ)
measurement
in basis
SUCCESS
with +1 outcome
Z
Z
Z
˜
V
• •
•
•
• •
˜
V
• •
•
•
=
=
˜
V
•
• •
• •
•
• •
•
•
=
=
˜
V
Gate prepared in step one
Gate prepared in step one
θ
θ
O (
2
θ
) + O(
#
) + O(η
)
O
(
2
θ
) + O(
CCZ
) + O(η
)
H
|0 , |1
Figure 4: An overview of the second-step of our protocol for N = 1 and N = 2, which can be extended
to any integer N. The first-step is to use synthillation to inject the non-Clifford gates shown in the
pink section of the circuit. The only other non-Clifford elements of the circuits are the pivotal rotations
R(θ). Input to the circuit are 2N mixed states ρ(θ), which are |R(θ)i magic states with phase
noise. In the absence of noise, the circuit measures the parity in the W (θ) bases. Therefore, when we
see a SUCCESS event, the ρ(θ) states are output with quadratically reduced noise. In the event of a
FAILURE, we discard the qubits and attempt again.
Accepted in Quantum 2018-02-21, click title to verify 10
performance advantage in terms of success probability due to the two step nature. We
found
p
synth
= 1 − 8
π/8
+ O(
2
π/8
), (28)
p
parity
= 1 − 2
θ
−
1
2
η + O(
2
π/8
,
2
θ
, η
2
, . . .),
where p
synth
is the probability of step one succeeding and p
parity
is the probability of step
two succeeding. To leading order, the previous MEK
k
protocols had a success probability
equal to p
mek
= p
synth
p
parity
. Here, we don’t commit to the second step until the first
step is successful, which will lead to superior rates of generating magic states. For the
setting θ = π/8, the protocol simplifies to a 10 → 2 protocol with
0
= 9
2
π/8
+ O(
3
π/8
) and
overhead n/k = 10/2 = 5, very similar to the original MEK protocol.
For N = 2, we found that
0
= 16
2
π/8
+ 3
2
θ
+
1
4
η + O(
3
π/8
,
2
θ
, η
2
, . . .), (29)
p
synth
= 1 − 12
π/8
+ O(
2
π/8
), (30)
p
parity
= 1 − 6
θ
− η + O(
2
π/8
,
2
θ
, η
2
, . . .), (31)
By going to N = 2, we incur only mildly worse constant prefactors, but gain a significant
efficiency improvement in terms of magic states output per input. For the setting θ = π/8,
the protocol simplifies to a 16 → 4 protocol with
0
= 19
2
π/8
+O(
3
π/8
) and overhead n/k =
16/4 = 4. To obtain the same n/k overhead using Bravyi-Haah protocols (which are limited
to θ = π/8), we need to go to a larger size 32 → 8 protocol with
0
= 25
2
π/8
+ O(
3
π/8
).
This confirms that our protocols can obtain similar resource overheads with a smaller scale
quantum computer, and without any sacrifice in terms of error suppression or success
probability.
4.2 Algebraic analysis
Here we take an analytic approach. We do not know of an analytic method of determining
the exact expressions for
0
, but can prove a rigourous upper bound using standard norm
inequalities. Actual performance will be much better than proven here. We begin by
considering the effect of noise on the input states
ρ(θ) := (1 −
θ
)|R(θ)ihR(θ)| +
θ
Z|R(θ)ihR(θ)|Z. (32)
We extend later to account for CCZ
#N
noise and pivotal rotation noise, but when these
components work perfectly the circuit implements
ρ(θ)
⊗2N
→ E(ρ(θ)
⊗2N
) = Kρ(θ)
⊗2N
K
†
(33)
where K is the parity projecting Kraus operator introduced in Eq. (13). Rather than the
whole multi-qubit output, we are interested in the fidelity of a single output qubit, and so
introduce the channel
E
i
(ρ(θ)
⊗2N
) = tr
i
[Kρ(θ)
⊗2N
K
†
], (34)
where tr
i
[· · · ] is the partial trace over all but the i
th
qubit. The output of this channel is
the unnormalised state
E
i
(ρ(θ)
⊗2N
) = p
good
|R(θ)ihR(θ)| + p
bad
Z|R(θ)ihR(θ)|Z. (35)
Accepted in Quantum 2018-02-21, click title to verify 11
The renormalisation constant p
good
+ p
bad
is the probability of the parity check yielding a
“+1" outcome. When the parity check process is error-free, this occurs whenever the input
states contains no errors or an even number of errors, and so
p
good
+ p
bad
=
1
2
(1 + (1 − 2
θ
)
2N
) (36)
The term p
bad
is the probability of an error on i
th
qubit and an odd number of errors on
the remaining 2N − 1 qubits
p
bad
=
θ
N
X
j=1
2N−1
2j−1
2j−1
θ
(1 −
θ
)
2N−2j
, (37)
=
θ
2
(1 − (1 − 2
θ
)
2N−1
),
< (2N − 1)
2
θ
,
where in the first line we have a binomial coefficient. The inequality follows from Bernoulli’s
inequality. This shows quadratic noise suppression in
θ
.
Next, we account for
#
noise in the CCZ
#N
gate. We can write the corresponding
magic state as
ρ
#N
= (1 −
#
)Ψ
#N
+
#
σ
#N
, (38)
where
Ψ
#N
= |CCZ
#N
ihCCZ
#N
|, (39)
and σ
#N
carries some Z noise. We define F as the channel describing the action of
the whole circuit (including implicit injection gadget for CCZ
#N
), assuming ideal pivotal
rotations, acting on ρ
#N
and ρ(θ)
⊗2N
. We will use that Ψ
#N
leads to a parity
F(Ψ
#N
⊗ ρ(θ)
⊗2N
) = E(ρ(θ)
⊗2N
) (40)
and by linearity of F we deduce
F(ρ
#N
⊗ ρ(θ)
⊗2N
) = (1 −
#
)E(ρ(θ)
⊗2N
) +
#
F(σ
#N
⊗ ρ(θ)
⊗2N
). (41)
Again, we are interested in only the single output qubit, and so introduce F
i
= tr
i
E
i
, which
straightforwardly yields
F
i
(ρ
#N
⊗ ρ(θ)
⊗2N
) = (1 −
#
)E
i
(ρ(θ)
⊗2N
) +
#
F
i
(σ
#N
⊗ ρ(θ)
⊗2N
). (42)
This yields a single qubit state of the form in Eq. (35) with new parameters p
0
good
and
p
0
bad
, which are tricky to exactly calculate but can again be bounded. The joint probability
p
0
good
+ p
0
bad
can be lower bounded by assuming F
i
(σ
#N
⊗ ρ(θ)
⊗2N
) = 0 and so
p
0
good
+ p
0
bad
≥ (1 −
#
)(p
good
+ p
bad
) (43)
The p
0
bad
term can be upper bounded by considering the worst-case scenario that F
i
(σ
#N
⊗
ρ(θ)
⊗2N
) leads to a logical error with unit probability, and so
p
0
bad
≤ (1 −
#
)p
bad
+
#
< (2N − 1)(1 −
#
)
2
θ
+
#
, (44)
where the second inequality follows from Eq. (37). These bounds are very loose and
overestimate p
0
bad
by quite a lot. Nevertheless, they are simple to obtain and rigorous.
Accepted in Quantum 2018-02-21, click title to verify 12
Next, we further consider phase noise on the pivotal rotation, each failing with prob-
ability η. In other words, all pivotal rotations act perfectly with probability (1 − η)
N
.
Therefore, the channel implemented is not F
i
but something of the form
G
i
= (1 − η)
N
F
i
+ (1 − (1 − η)
N
)F
0
i
, (45)
where F
0
i
is the noisy part of the channel with diamond norm not exceeding unity. There-
fore,
G
i
(ρ
#N
⊗ ρ(θ)
⊗2N
) =(1 − η)
N
(p
0
good
|R(θ)ihR(θ)| + p
0
bad
Z|R(θ)ihR(θ)|Z) (46)
+ (1 − (1 − η)
N
)F
0
i
(ρ
#N
⊗ ρ(θ)
⊗2N
).
The worst case scenario is that F
0
i
always generates an error, adding a (1 − (1 − η)
N
)
contribution to the error term. Therefore, after renormalising the error probability is
bounded by
0
≤
(1 − η)
N
p
0
bad
+ (1 − (1 − η)
N
)
(1 − η)
N
(p
0
good
+ p
0
bad
) + (1 − (1 − η)
N
)
≤
(1 − η)
N
((2N − 1)(1 −
#
)
2
θ
+
#
) + (1 − (1 − η)
N
)
(1 − η)
N
(1 −
#
)(p
good
+ p
bad
) + (1 − (1 − η)
N
)
The result scales as O(
#
), but this error rate is itself the output of performing the synthilla-
tion protocol using noisy |R(π/8)i-states of error rate
π/8
. In particular, Eq. (128) of
Ref. [20] shows that
#
≤ 1 −
2(1 −
π/8
)
4N+4
1 + (1 − 2
π/8
)
4N+4
= (6 + 14N + 8N
2
)
2
π/8
+ O(
3
π/8
) (47)
This suffices to conclude that
0
≤ (2N − 1)
2
θ
+ (6 + 14N + 8N
2
)
2
π/8
+ N η + O(
3
θ
,
3
π/8
, η
2
, . . .) (48)
where O(
3
) collects all higher order terms. For instance, for N = 1 and N = 2 this yields
0
≤
2
θ
+ 28
2
π/8
+ η + O(
3
θ
,
3
π/8
, η
2
, . . .) for N = 1
3
2
θ
+ 66
2
π/8
+ 2η + O(
3
θ
,
3
π/8
, η
2
, . . .) for N = 2
(49)
Comparing this with the numerical expressions Eq. (27) and Eq. (29), we see the analytic
upper bound is very loose and grossly overestimates the prefactors.
5 No small triorthogonal codes
Many other distillation protocols are based upon projections into codespaces with a transver-
sal non-Clifford, with transversality proofs typically using some notion of triorthogonal
matrices [4]. While the protocols proposed here do not manifestly have this form, it is
natural to ask whether there is some codespace projection with equivalent performance.
Indeed, Jones’ first-level distiller protocol [5] is effectively equivalent to projecting onto
the codespace of Bravyi-Haah triorthogonal codes [4], and Haah has recently introduced
level-lifting as a general methodology for finding such equivalences [16]. Furthermore, it
has long been known that for any distillation protocol there exists a codespace projection
Accepted in Quantum 2018-02-21, click title to verify 13
that achieves the same error suppression [24], though it may not achieve the same success
probability or admit a transversal non-Clifford gate.
In this section, we show that there exist no triorthogonal codes with fewer than 14
qubits. This bound is tight since the smallest Bravyi-Haah code is a 14 qubit triorthogonal
construction. It follows that the 10 → 2 MEK protocol is not equivalent to a projection
onto a triorthogonal code. What distinguishes MEK is that it is a highly compressed circuit
that is obtained from taking a larger circuit and cancelling some T -gates. This suggests
that something happens during the compression process of eliminating extraneous T -gates
that breaks the equivalence to triorthogonal codes. Since our protocols can be understood
as a generalisation of MEK protocols, it seems unlikely similar performance parameters
will be achievable using projections onto codes with exotic transversality properties.
We present the definition of triorthogonality
Definition 1 (Def 1. of Ref. [4])A binary matrix G of size m × n is called triorthogonal
iff the supports of any pair and any triple of its rows have even overlap, that is,
n
X
j=1
G
a,j
G
b,j
= 0 (mod 2) (50)
for all pairs of rows 1 ≤ a < b ≤ m and
n
X
j=1
G
a,j
G
b,j
G
c,j
= 0 (mod 2) (51)
for all triples of rows 1 ≤ a < b < c ≤ m.
The definition of triorthogonality allows a matrix to have either odd or even rows, and it
is standard to use a horizontal line to demarcate the split
G =
G
1
G
0
, (52)
so G
1
contains odd weight rows and G
0
contains even weight rows. Assuming G is row-wise
linearly independent, it describes an [[n, k, d]] quantum code where: n is the number of
columns in G; k is the number of rows in G
1
; and d ≥ 2 if and only if G
0
is non-trivially
supported on every column. We also use the notion of a biorthogonal matrix, which obeys
the constraint for pairs of rows but not for triples of rows.
Let G be a triorthogonal matrix with block matrix form
G =
G
1
G
0
=
A B
C D
1 0
, (53)
where 1 and 0 are the all-1 and all-0 row vectors of appropriate width. Using column
permutation the matrix can always be brought into this form. Without loss of generality,
we assume that the last row has weight w and is the highest weight row in the span of G
0
.
Let B and D be width u, so that the total matrix width is n = w + u.
From triorthogonality of G, it follows that the submatrix
L =
A
C
!
, (54)
Accepted in Quantum 2018-02-21, click title to verify 14
is biorthogonal with all rows being even weight and that
R =
B
D
!
, (55)
is biorthogonal with B containing odd weight rows. Since B contains odd weight rows, the
matrix D cannot contain the all-1 vector as this would violate biorthogonality. However,
since the code is distance 2, the matrix D must be supported on every column. Therefore,
there must exist at least 2 non-trivial rows in D. The smallest possible width for D is then
achieved by
D =
1 1 1 1 0 0
1 1 0 0 1 1
!
, (56)
which has width u = 6 and contains weight 4 vectors, and so we can infer that w ≥ 4.
Other D are possible, but one cannot obtain smaller parameters: There are at least two
rows and for any pair of rows they must overlap on at least 2 columns and also have support
on at least 2 other non-overlapping columns. From this we see that n = w +u ≥ 4+6 = 10.
So this is already enough to prove there are no [[n, k, 2]] triorthogonal codes with k ≤ 1
and n less than 10.
However, the bound w ≥ 4 was obtained based on the rows of D only, but w is the
max weight across all rows in the span of G
0
. If C contains a row of weight w
c
, then we
know that w ≥ w
c
+ 4. For any row of C we can add the last row of G
0
, which generates
a row of weight w
0
c
= w − w
c
, entailing that w ≥ w
0
c
+ 4 = w − w
c
+ 4 and so w
c
≥ 4.
Putting this together yields w ≥ 8 and u ≥ 6 so that n ≥ 14. There are no triorthogonal
codes with fewer than 14 qubits.
6 Discussion
6.1 Variation of the two-step protocol
This subsection discusses one possible variant of the two-step protocol. Consider a quantum
algorithm that needs many magic states of the form |R(θ)i, but with different values of
θ. As presented, our main protocol cannot be used to full effect as the very large N limit
assumes that we need many magic states with the same θ. However, it is straightforward
to check that one can distill pairs of states with the same θ
j
. That is, we may input states
of the form
N
N
j=1
ρ(θ
j
)
⊗2
and use N pivotal rotations with corresponding angles 2θ
j
.
6.2 Quadratic vs higher order error suppression
In our introduction, we remarked on the existence of distillation routines that offer much
larger reductions in errors without using concatenation [5, 6, 21, 22]. The appeal of these
protocols is better asymptotic performance in the limit of large quantum computers and
large error reduction. The analysis underpinning these results assumes that it is appropri-
ate to quantify resource costs by the ratio of input to output states. But a more realistic
picture is given by an involved full space time analysis; also accounting for the cost of
Clifford gates and quantum error correction. In such an analysis, it is possible to scale
the size of error correction codes between rounds of magic state distillation [25–27]. This
scaling trick is extremely effective, and is arguably the most important tool in the arsenal
of magic state distillation techniques. Although the idea has been known for some time, it
has gone without a name. In an effort to popularise this trick, O’Gorman and Campbell
recently proposed the phrase “balanced investment” [27].
Accepted in Quantum 2018-02-21, click title to verify 15
Balanced investment relies on distinct rounds of magic state distillation with successive
error reduction. Therefore, balanced investment is more compatible with protocols giving
quadratic error reduction, such as presented here, than with the protocols of Refs. [5, 6].
This argument is qualitative, and we need detailed resource analyses to make concrete
quantitative statements. However, such full resource investigations are difficult and time-
consuming and have only been undertaken for the Reed-Muller and Bravyi-Haah protocols.
Naturally, such a numerical investigation also falls outside the scope of this paper.
7 Conclusions
We presented a new two-step method of magic state distillation that is very competitive
at preparing single-qubit magic states, offering a way to circumvent the need for costly
gate-synthesis of single-qubit rotations. An important aspect of these new protocols are
the preparation of multi-qubit magic states using synthillation. Pressing open questions
include how these competing approach fare when all resource costs are considered, though
such an analysis will depend heavily on the architecture considered.
We would also like to explore whether the synthillation driven techniques proposed
here could be extended to protocols with larger than quadratic error reduction [5, 6]. After
completing this work, Hastings and Haah proposed some new approaches to synthillation
that may provide a starting point for attacking this problem [28].
8 Acknowledgements
This research was supported by the EPSRC (grant ref EP/M024261/1). We thank IBM
and developers of the QISKit, which was used for numerical simulations.
References
[1] Earl T Campbell, Barbara M Terhal, and Christophe Vuillot. Roads towards
fault-tolerant universal quantum computation. Nature, 549(7671):172, 2017. DOI:
10.1038/nature23460.
[2] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clif-
ford gates and noisy ancillas. Phys. Rev. A, 71:022316, 2005. DOI: 10.1103/Phys-
RevA.71.022316.
[3] Adam M. Meier, Bryan Eastin, and Emanuel Knill. Magic-state distillation with the
four-qubit code. Quant. Inf. and Comp., 13:195, 2013.
[4] Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead. Phys.
Rev. A, 86:052329, Nov 2012. DOI: 10.1103/PhysRevA.86.052329.
[5] Cody Jones. Multilevel distillation of magic states for quantum computing. Phys.
Rev. A, 87:042305, Apr 2013. DOI: 10.1103/PhysRevA.87.042305.
[6] Jeongwan Haah, Matthew B. Hastings, D. Poulin, and D. Wecker. Magic state distil-
lation with low space overhead and optimal asymptotic input count. Quantum, 1:31,
October 2017. ISSN 2521-327X. DOI: 10.22331/q-2017-10-03-31.
[7] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Asymptotically optimal ap-
proximation of single qubit unitaries by clifford and t circuits using a constant number
of ancillary qubits. Phys. Rev. Lett., 110:190502, May 2013. DOI: 10.1103/Phys-
RevLett.110.190502.
Accepted in Quantum 2018-02-21, click title to verify 16
[8] David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo. An algorithm
for the t-count. Quant. Inf. & Comp., 14(15-16):1261–1276, 2014.
[9] Neil J Ross and Peter Selinger. Optimal ancilla-free clifford+ t approximation of
z-rotations. Quant. Inf. and Comp., 16:901, 2016.
[10] Adam Paetznick and Krysta M Svore. Repeat-until-success: Non-deterministic de-
composition of single-qubit unitaries. Quant. Inf. & Comp., 14(15-16):1277–1301,
2014.
[11] Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of prob-
abilistic quantum circuits with fallback. Phys. Rev. A, 91:052317, May 2015. DOI:
10.1103/PhysRevA.91.052317.
[12] Andrew J Landahl and Chris Cesare. Complex instruction set computing architec-
ture for performing accurate quantum z rotations with less magic. arXiv preprint
arXiv:1302.3240, 2013. URL https://arxiv.org/pdf/1302.3240.pdf.
[13] Cody Jones. Distillation protocols for fourier states in quantum computing. arXiv
preprint arXiv:1303.3066, 2013. URL https://arxiv.org/pdf/1303.3066.pdf.
[14] Guillaume Duclos-Cianci and David Poulin. Reducing the quantum-computing over-
head with complex gate distillation. Phys. Rev. A, 91:042315, Apr 2015. DOI:
10.1103/PhysRevA.91.042315.
[15] Earl T Campbell and Joe O’Gorman. An efficient magic state approach to small
angle rotations. Quantum Science and Technology, 1(1):015007, 2016. DOI:
doi:10.1088/2058-9565/1/1/015007.
[16] Jeongwan Haah. Towers of generalized divisible quantum codes. arXiv preprint
arXiv:1709.08658, 2017. URL https://arxiv.org/pdf/1709.08658.pdf.
[17] Cody Jones. Low-overhead constructions for the fault-tolerant toffoli gate. Phys. Rev.
A, 87:022328, Feb 2013. DOI: 10.1103/PhysRevA.87.022328.
[18] Bryan Eastin. Distilling one-qubit magic states into toffoli states. Phys. Rev. A, 87:
032321, Mar 2013. DOI: 10.1103/PhysRevA.87.032321.
[19] Earl T. Campbell and Mark Howard. Unifying gate synthesis and magic state distilla-
tion. Phys. Rev. Lett., 118:060501, Feb 2017. DOI: 10.1103/PhysRevLett.118.060501.
[20] Earl T. Campbell and Mark Howard. Unified framework for magic state distillation
and multiqubit gate synthesis with reduced resource cost. Phys. Rev. A, 95:022316,
Feb 2017. DOI: 10.1103/PhysRevA.95.022316.
[21] Jeongwan Haah, Matthew B Hastings, D Poulin, and D Wecker. Magic state distilla-
tion at intermediate size. Quant. Inf. and Comp., 18:0114, 2018.
[22] Matthew B. Hastings and Jeongwan Haah. Distillation with sublogarithmic overhead.
Phys. Rev. Lett., 120:050504, Jan 2018. DOI: 10.1103/PhysRevLett.120.050504.
[23] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal
quantum computation using teleportation and single-qubit operations. Nature, 402:
390, 1999. DOI: 10.1038/46503.
[24] Earl T. Campbell and Dan E. Browne. On the structure of protocols for magic state
distillation. Lecture Notes in Computer Science, 5906:20, 2009. DOI: 10.1007/978-3-
642-10698-9_3. arXiv:0908.0838.
[25] R. Raussendorf, J. Harrington, and K. Goyal. A fault-tolerant one-way quantum
computer. Annals of Physics, 321(9):2242 – 2270, 2006. ISSN 0003-4916. DOI:
10.1016/j.aop.2006.01.012.
[26] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland.
Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86:
032324, Sep 2012. DOI: 10.1103/PhysRevA.86.032324.
Accepted in Quantum 2018-02-21, click title to verify 17
[27] Joe O’Gorman and Earl T. Campbell. Quantum computation with realistic
magic-state factories. Phys. Rev. A, 95:032338, Mar 2017. DOI: 10.1103/Phys-
RevA.95.032338.
[28] Jeongwan Haah and Matthew B Hastings. Codes and protocols for distilling t,
controlled-s, and toffoli gates. arXiv preprint arXiv:1709.02832, 2017. URL https:
//arxiv.org/pdf/1709.02832.pdf.
Accepted in Quantum 2018-02-21, click title to verify 18