Why are quantum computers fast? Magic states are a special ingredient, or resource, that allows quantum computers to run faster than traditional computers.
Everyday resources are things like food, water and energy. They are resources for life and without them we could not exist. They are valuable and often scarce.
Magic is a resource for quantum computing. Without magic, a device is no better than any other piece of traditional computing equipment. More precisely, a computing device without magic could be emulated by a traditional computer at essentially the same speed (at most a polynomial overhead). To run a quantum computer, magic must be consumed like fuel, and so must be continually replenished. Harnessing magic within the laboratory is difficult and yet essential, and so many practical problems in building quantum computers can be cast in the language of quantifying and creating magic. Specifically, magic appears naturally in the design of protocols for protecting quantum computers against noise.
Magic is contained within the qubits of a quantum computer, which are said to be in a magic state. This may sound abstract but is the same language we use for energy. For instance, an electron can be in a highly excited and energetic state or in its ground state. But the concept of energy is not tied to electrons. Any material thing can hold energy. In principle, anything can be in a magic state. But magic states are a quantum state of matter, and so mainly relevant on the quantum scale of individual electrons, photons and atoms.
Other wacky quantum resources include entanglement and coherence. Other scientists have argued that the secret behind quantum computers is actually entanglement, coherence or some other resource. But thinking about magic provides a unique perspective. There are entangled states and coherent superposition states that are not magical, and using only these states will give no quantum speed-up over traditional computing. To me, this signals that thinking about magic states teaches us something that is missed when we learn about entanglement or coherence.
The bloch sphere representation of a single qubit. The six red points are called stabiliser states: the north and south poles are the and states; the four states on the equator are (upto normalisation) , , and . These stabiliser states have no magic. Mixed, or noisy, states reside on the interior of the sphere, with zero-magic states forming an eight sided shape called an octahderon. For states outside the octahderon, the amount of magic increases with the distance from the octahderon.
The Bloch sphere picture above gives a geometric intuition to quantifying magic. But the are many different ways to measure distance. Also, for more than one qubit we can no longer rely on the Bloch sphere. How to quantify magic is a topic that I’ve been interested in for a long time. I even did some calculations back in 2008 that never made it into a publication. I gave up on those early results because I felt they didn’t teach us anything substantially new. Entanglement theory provides many tools for quantifying entanglement, and many of these ideas can be ported over to magic state theory. But so what! If quantum state has units of magic (by some measure) then what have we really learnt? Me and Mark Howard hit upon the idea of using a robustness metric of magic:
Phys. Rev. Lett. 118 090501 (2017)
The advantage of this particular way of measuring magic is that it has several nice practical applications. For instance, we can write software for a traditional computer that will emulate a quantum computer with a runtime that scales with the amount of magic (as measured in this particular way). Fortunately, this quantity grows exponentially with the number of magic states. But this does tell us that a little bit of magic isn’t enough, it is needed in large quantities for there to be a quantum speed-up.
Magic state distillation
Given a qubit protected from noise in an error correcting code, we can usually only prepare stabiliser states (with zero magic) while retaining this protection. So preparing a magic state is subject to noise, but we want pure noise-free magic states to fuel a reliable quantum computation. In the first paper to use the phrase “magic state”, Bravyi and Kitaev showed how to distill two different types of single qubit magic state. The suggestive language is used because the process is analogous to the distillation of alcoholic beverages. One starts with a lot of qubits, each with a small amount of magic, and distillation produces a smaller quantity of more potent magic states. The distillation process does not create any magic but rather concentrates it.
Magic state distillation is an area where I have made a number of contributions over many years. I will list some highlights in the following subsections.
Realistic magic state distillation
Magic state distillation is often described and costed at a high-level of abstraction, which is independent of the details of a particular quantum computing architecture. This highly abstracted approach gives a reasonable back of the envelope assessment of magic state distillation. But we need to do a lot more work to get an accurate picture of what a commercially competitive quantum computer would look like. With Joe O’Gorman, we undertook such an analysis and provided several useful tweaks to distillation routines:
Phys. Rev. A. 95 032338 (2017)
Exotic magic state distillation
Early work on magic states focused on very specific examples, usually the so-called T-state. One T-state allows us to implement one specific quantum logic gate, the T-gate. A quantum algorithm will use a very large number of such gates. However, if we can prepare an exotic magic state, we could gain direct access to a more complex quantum logic gate. Recently, I have been very interested in how we could distill exotic forms of magic states, and how this can reduce the overall cost of building a quantum computer. We proposed a family of synthillation protocols that distill multiqubit magic states
Phys. Rev. Lett. 118 060501 (2017) (the short version)
Phys. Rev. A 95 022316 (2017) (the long version)
I have also worked on refining earlier ideas on distill of single qubit magic states that enable small single qubit rotations
Quantum Science and Technology 1, 015007 (2016)
Qudit magic state distillation
In a series of papers, I worked on the first protocols for distillation in the qudit setting of quantum computing.
Phys. Rev. Lett. 113 230501 (2014)
Phys. Rev. X. 2 041021 (2012)
New J. Phys. 14 063006 (2012)
The NJP paper dealt only with qutrits (three level systems). The latter two papers took advantage of quantum Reed-Muller codes and provided protocols for larger qudits (with a prime number of levels).
Fundemental insights into magic state distillation
Dan Browne introduced me to the magic state model of quantum computing, and our first papers together proved some no-go theorems on distillation. For instance, we showed some noisy magic states are bound: they could not be distilled (at least not in batches of constant size)
Physical Review Letters 104 030503 (2010)
Cryptography 4th Workshop, TQC 5906 Page 20 (2009)
I later developed magic state theory analogs to fundemental concepts in entanglements theory, such as catalysis and activation:
Physical Review A 83 032317 (2011)