«Quantum computers are capable of executing algorithms whilst tolerating modest rates of faults or errors. Stabilizer codes encode information in ...»
Catalysis and activation of magic states in fault tolerant architectures
Earl T. Campbell
Institute of Physics and Astronomy, University of Potsdam, 14476 Potsdam, Germany.
In many architectures for fault tolerant quantum computing universality is achieved by a combination of
Clifford group unitary operators and preparation of suitable nonstabilizer states, the so-called magic states.
Universality is possible even for some fairly noisy nonstabilizer states, as distillation can convert many copies into a purer magic state. Here we propose novel protocols that exploit multiple species of magic states in surprising ways. These protocols provide examples of previously unobserved phenomena that are analogous to catalysis and activation well known in entanglement theory. The full article is available as Ref. .
Quantum computers are capable of executing algorithms whilst tolerating modest rates of faults or errors. Stabilizer codes encode information in subspaces of larger Hilbert spaces and allow a proportion of errors to be actively detected and corrected .
Whereas some anyonic systems with topologically protected ground states provide a passive method of safely storing quantum information . However, fault tolerant quantum computing is not just about archiving quantum information, but also processing the information whilst stored in its protected form. However, by employing stabilizer codes and topological systems we restrict how the quantum information may be fault-tolerantly manipulated. Stabilizer codes only allow coherent implementation of a limited group of fault tolerant gates, the so-called transversal gates. Unfortunately, recent research has shown that no stabilizer code can both protect against generic errors and offer a universal set of transversal gates . Similarly, topologically protected groups of gates, implemented by braiding anyons, are not universal for the most physically plausible species of anyons [5, 6].
Consequently, an alternative route to universal and fault tolerant quantum computing must be sought out.
This obstacle is overcome by gate injection techniques. A suitable resource state is identiﬁed, and through fault tolerant gates and measurements, this resource is consumed in exchange for a new fault-tolerant unitary operator that promotes the group of gates to full universality. For both stabilizer codes and anyonic systems, the most common set of manifestly fault tolerant gates are the Clifford group, the group of unitary operators that conjugate the Pauli operators. What resource states might promote the Clifford group to universality? Since the Clifford group maps stabilizer states — eigenstates of Pauli operators — to other stabilizer states, and such evolutions are efﬁciently classically simulable , we know that stabilizer states fail to provide universality.
However, numerous nonstabilizer states do provide universality, including all single-qubit pure nonstabilizer states . Bravyi and Kitaev proposed the appellation magic states for such resources . In their seminal article, Bravyi and Kitaev showed that some mixed nonstabilizer states can enable universal quantum computing via a process of distillation into purer magic states.
Since preparation of the raw resources is not fault tolerant, we expect them to be noisy, and so distillation is essential.
The paradigm of magic states as a resource for promoting the Clifford group is analogous to other resource theories, such as:
how entanglement is a resource when only local operations are available ; and how continuous variable Gaussian entangled states can be utilized provided with just local gaussian operations . In both these alternative examples of resource theories we have a thorough understanding of the fundamental principles behind what state transformations are possible. The role of magic states is not yet understood as comprehensively as entanglement, although lately several results have begun to illuminate the subject [8, 12–17]. We will not review these works here, but a brief survey can be found in the full manuscript.
This article explores the fundamental principles that govern magic states, and we uncover several new phenomena previously not observed. Many of the new phenomena have analogous, though subtly distinct, counterparts in entanglement theory, such as entanglement catalysis  and entanglement activation . Previous work on magic states has focused on what is achievable with many copies of the same quantum state. Whereas, a unifying theme of the protocols introduced here are the counterintuitive ways that two different sorts of resource can be jointly exploited.
I. MAGIC CATALYSIS
Magic catalysis can be described as a scenario involving two agents: a “magic state banker”; and an operator of a computer capable of only Clifford group operations. The banker is willing to loan magic states to the operator, but requires that the operator returns exactly the same quantum state at a later time. We identify a protocol where the loaned magic state acts as a catalyst, enabling the operator to perform state transformations that would have been impossible otherwise. Our protocol counteracts the misleading but intuitive idea that resources must be consumed to serve a function.
Speciﬁcally, our protocol uses the so-called H-magic state, which is an eigenstate of the Hadamard operation. Denoting the two Hadamard eigenstates as |H0 and |H1, we show that the following transformation can be deterministically implemented using Clifford group operations;
Such a transformation is surprising because without the presence of the second quantum state, the transformation is impossible with Clifford group operations; such that,
where the crossed arrow denotes impossibility. For these Hadamard eigenstates, this catalytic process is a very close analog of entanglement catalysis. Our catalysis protocol makes use of the symmetries of the Hadamard magic states, and so it seems unlikely that more generic quantum states can serve as catalysts.
II. MAGIC ACTIVATION
Magic activation again involves a special resource, this time called the activator, that enables a probabilistic transformation that was impossible without this assistance. This phenomena differs from catalysis in several key ways. The activator is not returned to a banker, and the transformation may succeed with nonunit probability. Furthermore, the probabilistic transformation also consumes a supply of bound magic states [15, 16] that alone have limited computational power when in ﬁnite quantity. This is a previously established notion that is analogous to bound entanglement. However, existing theorems have the weakness of requiring that we have only a ﬁxed and ﬁnite number of the bound magic states. It remains unclear whether one can prove the existence of bound magic states in the asymptotic regime. Subtleties aside, it is interesting to ask whether a ﬁnite number of bound states can ever be useful for a computational task, and this is exactly what our protocol proves.
Speciﬁcally, we consider noisy T -magic states, which are eigenstates of the Clifford gate, T, that cyclically permutes Pauli operators ( T X = Y T, T Y = ZT, T Z = T X). We denote the two T eigenstates as |T0 and |T1. Our results show that there
exists a single qubit state, say ρout, such that:
These equations assert that neither initial state is capable of producing ρout with Clifford group operations that succeed with some non-zero probability. However, we show that combined it is possible to output the target state;
Indeed, we show that this is possible for any ﬁdelity, f, for which the state is not a mixture of stabilizer states. Our result establishes for the ﬁrst time that all noisy T states are useful for some task, and it follows that the same can be said for all single qubit non-stabilizer states.
A natural question to ask is whether the protocol can be iterated or extended in any way. Typically, the output state ρout is still quite impure, and we might expect that an iterative protocol is capable of producing an output of arbitrarily high purity.
Indeed, this is the case with activation in entanglement theory and so a sturdy analog should exhibit this property. Our article also describes a more involved protocol that is stronger in two key respects: ﬁrstly it can be extended to consume arbitrarily many bound resources, with an output ﬁdelity asymptotically approaching unity; secondly, the activating resources are also computational weak states that we call irreducible magic states. However, even this extended protocol exhibits dissimilarities from entanglement activation.
III. IRREDUCIBLE MAGIC STATES
Next we discuss the existence of, the aforementioned, computationally weak multi-qubit states that were ﬁrst observed by Reichardt , which we call irreducible magic states. The deﬁning feature of irreducible magic states is that, on their own, no single-qubit nonstabilizer state can be extracted from one copy. Understanding irreducibility states is an enlightening pursuit in its own right. However, we introduce irreducible magic states with the purpose of using them in our extended asymptotic activation protocol.
Formally, if σn is an n-qubit non-stabilizer state, then it is irreducible if for all single-qubit nonstabilizer states, ρout, we have that
Our ﬁnal protocol exploits a combination of irreducible magic states and bound magic states. Despite both resources being of limited utility we can, with some probability, extract a magic state of arbitrarily high ﬁdelity. In many ways this protocol is more surprising than the previous magic state activation protocol. However, this latter protocol relies on a variable number of resources. Depending on your preferred deﬁnition of activation, this protocol may also qualify as such. However we prefer to stress its unique aspects and so refer to it as an asymptotic activation protocol.
n Speciﬁcally, we show that there exists an n-qubit irreducible magic state, σirreducible, and a probabilistic Clifford group protocol such that
provided only that the initial noisy T states are not stabilizer states.
Unlike the previous activation protocol we are allowing for the number of copies to vary, with the phenomena becoming more pronounced in the large n limit. Since the number of copies is varying, and not ﬁxed to some ﬁnite n, previous no-go results on the non-distillability of noisy T -states do not apply, and hence we cannot guarantee that the transformation would be impossible without the addition of the irreducible magic state. That is, we have not strictly proven (f |T0 T0 | + (1 − f )|T1 T1 |)⊗n−1 fout |T0 T0 | + (1 − fout )|T1 T1 |, (8) probabilistic As such, we have exercised caution and have not described this as a vanilla activation protocol. However, for small ﬁdelities, f (1 + 3/7)/2, there is no known protocol  that allows this transformation, even in the limit of many copies. The lesson this protocol teaches us is that large numbers of noisy T -states can be exploited to great effect when accompanied by another resource state. It remains the most fundamental open question in this research area to determine whether asymptotically many copies of all nonstabilizer states can be puriﬁed when completely unassisted by other resources.
V. DISCUSSION AND CONCLUSIONS
Combined, these results provide a signiﬁcant advance in our understanding of the principles governing magic states and their manipulation. However, the work actually prompts many more new problems that it solves. Personally, I ﬁnd the topic appealing because so it is relatively unexplored compared to entanglement theory. Whilst there are many parallels with entanglement theory, there are also striking dissimilarities.
 E. T. Campbell, preprint available at http://arxiv.org/abs/1010.0104.
D. Gottesman, Phys. Rev. A 57, 127 (1998).
 A. Kitaev, Ann. Phys. 303, 2 (2003).
 B. Eastin and E. Knill, Phys. Rev. Lett. 102, 110502 (2009).
 M. Freedman, C. Nayak, and K. Walker, Phys. Rev. B 73, 245307 (2006).
 L. S. Georgiev, Phys. Rev. B 74, 235112 (2006).
 S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004).
 B. W. Reichardt, Quantum Inf. Comput. 9, 1030 (2009), arXiv:quant-ph/0608085v1.
 S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005).
 R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Rev. Mod. Phys. 81, 865 (2009).
 J. Eisert and M. Plenio, Int. J. Quant. Inf. 1, 479 (2003).
 B. W. Reichardt, Quantum Information Processing, Vol. 4, No. 3, August ( 2005) 4, 251 (2005).
  B. W. Reichardt, in Algorithmica. DOI: 10.1007/s00453-007-9069-7 (Springer New York, 2007).
W. van Dam and M. Howard, Phys. Rev. Lett. 103, 170504 (2009).
 E. T. Campbell and D. E. Browne, Lecture Notes in Computer Science 5906, 20 (2009), arXiv:0908.0838.
 E. T. Campbell and D. E. Browne, Phys. Rev. Lett. 104, 030503 (2010).
  N. Ratanje and S. Virmani, arXiv:1007.3455.
D. Jonathan and M. B. Plenio, Phys. Rev. Lett. 83, 3566 (1999).
 P. Horodecki, M. Horodecki, and R. Horodecki, Phys. Rev. Lett. 82, 1056 (1999).