# Magic state distillation with low overhead

###### Abstract

We propose a new family of error detecting stabilizer codes with an encoding rate that permit a transversal implementation of the gate on all logical qubits. The new codes are used to construct protocols for distilling high-quality ‘magic’ states by Clifford group gates and Pauli measurements. The distillation overhead scales as , where is the output accuracy and . To construct the desired family of codes, we introduce the notion of a triorthogonal matrix — a binary matrix in which any pair and any triple of rows have even overlap. Any triorthogonal matrix gives rise to a stabilizer code with a transversal -gate on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a two-fold overhead reduction for distilling magic states with accuracy compared with the best previously known protocol.

## I Introduction

Quantum error correcting codes provide a means of
trading quantity for quality when unreliable components
must be used to build a reliable quantum device.
By combining together sufficiently many unprotected noisy qubits
and exploiting their collective degrees of freedom
insensitive to local errors, quantum coding allows one to
simulate noiseless logical qubits and quantum gates up to any
desired precision provided that the noise level is below a constant threshold value Dennis *et al.* (2002); Shor (1996); Knill (2004); Aliferis *et al.* (2006).
Protocols for fault-tolerant quantum computation with the
error threshold close to have been proposed recently Knill (2005); Raussendorf and Harrington (2007); Fowler *et al.* (2009).

An important figure of merit of fault-tolerant protocols is the cost
of implementing a given logical operation such as a unitary gate or a measurement
with a desired accuracy . Assuming that elementary operations
on unprotected qubits
have unit cost, all fault-tolerant protocols proposed so far including the ones based on concatenated codes Aliferis *et al.* (2006) and topological codes Raussendorf and Harrington (2007); Raussendorf *et al.* (2007); Fowler *et al.* (2009)
enable implementation of a universal set of logical operations
with the cost ,
where the scaling exponent depends on a particular protocol.

For protocols based on stabilizer codes Gottesman
the cost of a logical operation may also depend on
whether the operation is a Clifford or a non-Clifford one.
The set of Clifford operations (CO) consists of
unitary Clifford group gates such as the Hadamard gate ,
the -rotation ,
and the CNOT gate,
preparation of ancillary states, and measurements in the
basis. Logical CO usually have a
relatively low cost as they can be implemented
either transversally Gottesman or, in the case of topological
stabilizer codes, by the code deformation method Raussendorf *et al.* (2007); Bombin and Martin-Delgado (2009); Fowler *et al.* (2009).
On the other hand, logical non-Clifford
gates, such as the -rotation
usually lack a transversal implementation Eastin and Knill (2009); Bravyi and Koenig (2012)
and have a relatively high cost that may exceed the one of CO
by orders of magnitude Raussendorf *et al.* (2007). Reducing the cost of
non-Clifford gates is an important problem since
the latter constitute a significant fraction of any
interesting quantum circuit.

The present paper addresses this problem by constructing
low overhead protocols for the magic state distillation — a
particular method of implementing logical non-Clifford
gates proposed in Bravyi and Kitaev (2005). A magic state is an ancillary resource
state that
combines two properties:

Universality: Some non-Clifford
unitary gate can be implemented using one copy of
and CO. The ancilla can be destroyed in the
process.

Distillability: An arbitrarily good approximation to can be prepared by
CO, given a supply of raw ancillas with the initial
fidelity above some constant
threshold value.

Since the Clifford group augmented by any non-Clifford gate is computationally
universal Nebe *et al.* (2000), magic state distillation can be used to achieve
universality at the logical level provided that logical CO and logical raw ancillas are readily available.

Below we shall focus on the magic state

A single copy of combined with a few CO
can be used to implement the -gate, whereby providing
a computationally universal set of gates Boykin *et al.* (2000); Bravyi and Kitaev (2005).
It was shown by Reichardt Reichardt (2005) that the state
is distillable if and only if the initial fidelity is above the threshold value
.

Our main objective will be to minimize the number of raw ancillas required to distill magic states with a desired accuracy . To be more precise, let be a state of qubits which is supposed to approximate copies of . We will say that has an error rate iff the marginal state of any qubit has an overlap at least with . Suppose such a state can be prepared by a distillation protocol that takes as input copies of the raw ancilla and uses only CO. We will say that the protocol has a distillation cost iff . For example, the original distillation protocol of Ref. Bravyi and Kitaev (2005) based on the -qubit Reed-Muller code has a distillation cost , where .

## Ii Summary of results

Our main result is a new family of distillation protocols for the state
with a distillation cost ,
where
and is an arbitrary even integer. By choosing large enough
the scaling exponent
can be made arbitrarily close to .
The protocol works by concatenating an elementary subroutine
that takes as input magic states with an error rate
and outputs magic states with an error rate .
For comparison, the best previously known
protocol found by Meier et al. Meier *et al.* has a distillation cost as above with
the scaling exponent .
Distillation protocols with the scaling exponent
were recently discovered by Campbell et al. Campbell *et al.* (2012)
who studied extensions of stabilizer codes, CO, and magic states to qudits. We conjecture that the scaling exponent cannot be smaller than
for any distillation protocol and give some arguments in support of this
conjecture in Section VI.

Our distillation scheme borrows two essential ideas from Refs. Bravyi and Kitaev (2005); Meier *et al.* .
First, as proposed in Bravyi and Kitaev (2005), we employ stabilizer codes that admit a special symmetry in favor of transversal -gates and measure the syndrome of such codes
to detect errors in the input magic states.
Secondly, as proposed by Meier et al. Meier *et al.* , we reduce the distillation cost
significantly by using distance- codes with multiple logical qubits.
The new ingredient is a systematic method of constructing stabilizer
codes with the desired
properties. To this end we introduce the notion of a triorthogonal matrix —
a binary matrix in which any pair and any triple of rows have even overlap.
We show that any triorthogonal matrix with odd-weight rows
can be mapped to a stabilizer code with logical qubits that admit a transversal -gate on all logical qubits, possibly augmented by Clifford gates.
Each even-weight row of gives rise to a stabilizer which is used in the distillation protocol to detect errors in the input magic states.
Finally, we propose a powerful numerical method for generating triorthogonal matrices.
To illustrate its usefulness,
we construct the first example of a distance- code with a transversal -gate
that encodes one qubit into qubits.

While the asymptotic scaling of the distillation cost is of great theoretical interest,
its precise value in the non-asymptotic regime may offer valuable insights
on practicality of a given protocol. Using raw ancillas with the initial
error rate and the target error rate between and
we computed the distillation cost numerically for the optimal
sequence composed of the -to- protocol of Ref. Bravyi and Kitaev (2005),
and the -to- protocol of Ref. Meier *et al.* . Combining these protocols
with the ones discovered in the present paper we observed
a two-fold reduction of the distillation cost for
and a noticeable cost reduction for the entire range of ,
see Table 1 in Section VIII.

Since a magic state distillation is meant to be performed
at the logical level of some stabilizer code, throughout this paper
we assume that CO themselves are perfect. Whether or not this simplification is justified depends on the chosen code. More precisely, let the cost of implementing logical CO
and the distillation cost be and
respectively, where is the desired precision. In the case ,
high-quality CO are cheap and one can safely assume that CO are perfect.
The opposite case when high-quality CO are expensive (i.e. ) is realized, for example, in the topological one-way quantum computer
based on the 3D cluster state introduced by Raussendorf et al. Raussendorf *et al.* (2007),
where . As was pointed out in Raussendorf *et al.* (2007), in this case
it is advantageous to use expensive high-quality CO only at the final rounds of distillation and use relatively cheap noisy CO for the initial rounds.
Using the -to- distillation protocol of Ref. Bravyi and Kitaev (2005)
with ,
the authors of Ref. Raussendorf *et al.* (2007) showed how to implement a universal set
of logical gates with the cost .
A detailed analysis of errors in logical CO was performed by
Jochym-O’Connor et al Jochym-O’Connor *et al.* .

The rest of the paper is organized as follows. We begin with the definition of triorthogonal matrices and state their basic properties in Section III. The correspondence between triorthogonal matrices and stabilizer codes with a transversal -gate is described in Section IV. We introduce our distillation protocols for the magic state in Sections V,VI and Appendix A. A family of distance- codes with an encoding rate that admit a transversal -gate is presented in Section VII. We compute the distillation cost of the new protocols and make comparison with the previously known protocols in Section VIII. A numerical method of generating triorthogonal matrices is presented in Section IX. Finally, Appendix B presents the code with a transversal -gate.

Notations: Below we adopt standard notations and terminology pertaining to quantum stabilizer codes Nielsen and Chuang (2000). Given a pair of binary vectors , let be their inner product and be the weight of , that is, the number of non-zero entries in . Given a linear space , its dual space consists of all vectors such that for any . We shall use notations for the single-qubit Pauli operators. Given any single-qubit operator and a binary vector , the tensor product will be denoted . In particular, . The Pauli group consists of -qubit Pauli operators , where , and . The Clifford group consists of all unitary operators such that . It is well known that is generated by one-qubit gates (the Hadamard gate), (the -gate), and the controlled- gate . All quantum codes discussed in this paper are of Calderbank-Shor-Steane (CSS) type Calderbank and Shor (1996); Steane (1996). Given a pair of linear spaces such that , the corresponding CSS code has stabilizer group and will be denoted as .

## Iii Triorthogonal matrices

To describe our distillation protocols let us define a new class of binary matrices.

###### Definition 1.

A binary matrix of size is called triorthogonal iff the supports of any pair and any triple of its rows have even overlap, that is,

(1) |

for all pairs of rows and

(2) |

for all triples of rows .

An example of a triorthogonal matrix of size is

(3) |

where only non-zero matrix elements are shown. The two submatrices of formed by even-weight and odd-weight rows will be denoted and respectively. The submatrix is highlighted in bold in Eq. (3). We shall always assume that consists of the first rows of for some . Define linear subspaces spanned by the rows of , , and respectively. Using Eq. (1) alone one can easily prove the following.

###### Lemma 1.

Suppose is triorthogonal. Then (i) all rows of are linearly independent over , (ii) , (iii) , and (iv) .

###### Proof.

Let be the rows of such that the first row form . By definition, any vector can be written as for some . From Eq. (1) we infer that for all and for any . Hence . If or then for all . This proves (i) and (ii). Since any row of is orthogonal to itself and any other row of , we get for all and . This implies . If , then for all , that is, . This proves (iii). Finally, (iv) follows from , , and dimension counting. ∎

As we show in Section IV, any binary matrix with columns and odd-weight rows satisfying Eq. (1) gives rise to a stabilizer code encoding qubits into qubits. Condition Eq. (2) ensures that this code has the desirable transversality properties, namely, the encoded state can be prepared by applying the transversal -gate to the encoded , possibly augmented by some Clifford operator. To state this more formally, define -qubit unnormalized states

(4) |

Define also a state

(5) |

where are the rows of .

###### Lemma 2.

Suppose a matrix is triorthogonal. Then there exists a Clifford group operator composed of and gates only such that

(6) |

###### Proof.

Below we promote the elements of binary field to the normal integers of ; we associate and . Unless otherwise noted by “” or “”, every sum is the usual sum for integers and no modulo-reduction is performed.

When is a string of or , let be the parity of . Let us derive a formula for a phase factor as a function of components . Observe that

(7) |

Since the binomial coefficient is the number of ways to choose non-zero components of , we may write

(8) |

By definition of the state , one has

Since depends on the linear space rather than the matrix presentation , we may assume that all rows of are linearly independent over . Let be the rows of , and decompose , where are uniquely determined by .

Each component of is the parity of the bit string , and is the sum of ’s. Hence, Eq. (8) implies

(9) |

where denotes the bitwise AND operation. Triorthogonality condition Eq. (2) implies that the triple overlap is even, so we may drop the last term in Eq. (9). This is in fact one of the main motivations we consider triorthogonal matrices.

Let the first rows of have odd weight and all others even weight, and put

In addition, Eq. (1) implies for distinct that

Here all and are integers. Thus

where

Let us show that the unwanted phase factor can be canceled by a unitary Clifford operator that uses only and gates. To this end, we rewrite as a function of . As noted earlier, are uniquely determined by . Indeed, there is a matrix over such that , since is a basis of the linear space . (There could be many such .) We again use Eq. (7) with the observation that is the parity of the bit string to infer

for all . Therefore, we can express as

where are some integers determined by , and , all of which depend only on our choice of the matrix . Explicitly, and .

The extra phase factor is canceled by applying gate for each pair of qubits , and the gate to every qubit . This defines the desired Clifford operator composed of and gates such that

(10) |

for all . Therefore,

∎

For the later use let us state the following simple fact.

###### Lemma 3.

Let be a triorthogonal matrix without zero columns. If is non-empty and has less than rows, then must have at least one zero column.

###### Proof.

Suppose on the contrary all columns of are nonzero. If has only one row, it must be the all-ones vector . Then, the inner product between and any row of is the weight of modulo 2, which is odd. But, the orthogonality Eq. (1) requires it to be even. This is a contradiction.

## Iv Stabilizer codes based on triorthogonal matrices

Given a triorthogonal matrix with odd-weight rows, define a stabilizer code with -type stabilizers , , and -type stabilizers , . The inclusion implies that all stabilizers pairwise commute.

###### Lemma 4.

###### Proof.

Indeed, the assumption that have odd weight and Eq. (1) ensure that the operators defined in Eq. (11) obey the correct commutation rules, that is, . It remains to check that and commute with all stabilizers. Given any -type stabilizer , , one has since and . Given any -type stabilizer , , one has since and , see Lemma 1. This shows that and are indeed logical Pauli operators on encoded qubits.

Using Lemma 4 one can show that the operator defined in Lemma 2 implements an encoded gate on each logical qubit of the code . Indeed, for any , the encoded state is

Using Eq. (10) from the proof of Lemma 2 one arrives at

This provides a generalization of a transversal -gate to multiple logical qubits.

## V Distillation subroutine

We are now ready to describe the elementary distillation subroutine. It takes as input copies of a (mixed) one-qubit ancilla such that . We shall refer to as the input error rate. Define single-qubit basis states and . We shall assume that is diagonal in the -basis, that is,

(12) |

This can always be achieved by applying operators and with probability each to every copy of . Note that , that is, the random application of is equivalent to the dephasing in the -basis which destroys the off-diagonal matrix elements without changing the fidelity .

Define linear maps

(13) |

describing the ideal -gate and the -error respectively. Using Clifford operations and one copy of as in Eq. (12) one can implement a noisy version of the -gate, namely, . A circuit implementing is shown on Fig. 2, where the -error is shown by the -gate box with a subscript indicating the error probability. One can easily show that this circuit indeed implements by commuting through the CNOT gate and the classically controlled gate.

The entire subroutine is illustrated on Fig. 1. The first step is to prepare copies of the state and encode them using the code . This results in the state defined in Eq. (4) and requires only CO.

The state is then acted upon by the map . The latter can be implemented using CO and copies of as shown on Fig. 2. This results in a state

where . Next we apply the Clifford unitary operator constructed in Lemma 2. Since involves only and gates, it commutes with any -type error. Hence the state prepared at this point is

where we have used Eq. (6). The next step is a non-destructive eigenvalue measurement for -type stabilizers of the code , that is, the Pauli operators , where are the rows of . If at least one of the measurement returns the outcome ‘’, the subroutine returns ‘FAILED’ and the final state is discarded. If all measured eigenvalues are ‘’, the state has been projected onto the code space of the code and the subroutine is deemed successful (since we do not have any -type errors, the syndrome of all -type stabilizers is automatically trivial). This results in a state

where is the projector onto the code space of and is the success probability. The state has only contribution from errors with , see Lemma 1, since these are the only -type errors commuting with all -type stabilizers. Hence the success probability is

(14) |

where the second equality uses the MacWilliams identity MacWilliams and Sloane (1983). Any vector can be written as , where and are the rows of . Since is a stabilizer, we conclude that

Here we used definition of the logical -type operators, see Eq. (11). Hence the state coincides with an encoded -qubit mixed state

(15) |

where and

(16) |

The last step of the subroutine is to decode whereby mapping to . The -qubit state is the output state of the distillation subroutine. The reduced density matrix describing the -th output qubit can be written as

where is the output error rate on the -th qubit:

Let be the sum of and the space spanned by all rows of except for . Lemma 1 implies that . On the other hand, , where is the one-dimensional subspace spanned by . Hence and thus

(17) |

We shall be mostly interested in the worst-case output error rate

(18) |

Output qubits with can be additionally dephased in the -basis to achieve . From Eq. (17) we infer that , where is the minimum weight of a vector such that for some . Equivalently,

(19) |

is the distance of the code against -type errors. Using the MacWilliams identity, we also get

(20) |

This expression can be easily evaluated numerically in the important case when has only a few rows.

The above subroutine requires extra qubits to prepare the encoded state, while the total number of Pauli measurements is . In Appendix A we describe an alternative subroutine which is slightly less intuitive but does not require any extra qubits and uses only Pauli measurements. Both subroutines output the same state and have the same success probability.

## Vi Full distillation protocol

The final goal of the distillation is to prepare a state of qubits such that the overlap between and -copies of the magic state is sufficiently close to , say, at least . Such state can be used as a resource to simulate any quantum circuit that contains Clifford gates and at most gates using only CO with an overall error probability at most . Each qubit of allows one to simulate one -gate using the scheme shown on Fig. 2.

Let be the reduced density matrix describing the -th qubit of . For any given target error rate our full protocol will distill a state which is diagonal in the basis and such that

(21) |

The standard union bound then implies that the overlap is close to whenever .

In order to distill magic states with the target error rate , the elementary
subroutine described in Section V will be applied recursively
such that each input state consumed by a level- distillation
subroutine is one of the output states distilled by some level-
subroutine. The recursion starts at a level with input states,
where is the distillation cost.
In the limit the distillation rounds can be organized such
that all input states consumed by any elementary subroutine at a level
have been distilled at different subroutines at the level , see Lemma IV in Meier *et al.* .
It allows one to disregard correlations between errors and analyze
the full protocol using the average yield

that is, the average number of output states with an error rate per one input state with an error rate . Here is defined in Eqs. (18,20). Neglecting the fluctuations, the distillation cost , the input error rate , the target error rate , and the required number of levels are related by the following obvious equations:

(22) |

In the limit of small one has and thus . Taking into account that , where the distance is defined in Eq. (19), one arrives at

(23) |

provided that the input error rate is below a constant threshold value , that depends on the chosen triorthogonal matrix.

We conjecture that the scaling exponent of the distillation cost cannot be smaller than for any concatenated distillation protocol based on a triorthogonal matrix. Indeed, suppose the output error rate satisfies for and . As noted above, the potential correlation in the error probabilities among the output states may be ignored. Then, after levels of distillation the output error rate should satisfy

where . Let be the inverse yield in the small input error rate limit. Clearly, . Since , the probability that the output is the desired magic state can be at most . It follows that , and therefore, . We conclude that

## Vii A family of triorthogonal matrices

To construct explicit distillation protocols, triorthogonal matrices with high yield are called for. A natural strategy to maximize the yield is to keep the number of even-weight rows in as small as possible. Indeed, each extra row in increases the number of constraints due to Eqs. (1,2) without increasing the yield. However, the number of rows in cannot be too small. Recall that the distillation subroutine of Section V improves the quality of magic states only if , where is the distance of the code