Universal quantum computation with ideal Clifford gates and noisy ancillas (14 pages)

By S. Bravyi, Alexei Y. Kitaev. 2004

1,639 citations recorded by the source corpus.

We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state |0>, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state rho, which should be regarded as a parameter of the model. Our goal is to determine for which rho universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of rho and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain "magic" directions. If the polarization of rho along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/74d84fc0b7435ccf199f77b39237313c8ad7efde

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Low-Depth Quantum Simulation of Materials (2017, background): “, physical qubits dedicated to the distillation and teleportation of magic states) than the number of physical qubits required to encode each logical qubit [47].”
Surface code quantum computing by lattice surgery (2011, result): “This allows for both state preparation and also arbitrary single-qubit rotations, in accordance with standard techniques [29].”
Quantum error correction for quantum memories (2013, neutral): “However, for gates such as the T gate [or Toffoli gate, also in C ð 3 Þ ] the method of magic state distillation has been developed (Bravyi and Kitaev, 2005).”
The XZZX surface code (2020, neutral): “[51] S.”
Quantum computing and the entanglement frontier (2012, background): “In most such proposals, the anyon braiding by itself is not sufficient for universal quantum computing, but can be supplemented by unprotected (and possibly quite noisy) nontopological operations to realize a universal gate set.(61) Indeed, in some cases(60) braiding of anyons can be modeled faithfu”
Wigner Function Negativity and Contextuality in Quantum Computation on Rebits (2014, methodology): “for which a distillation scheme relying on an intricate CSS-code construction was first presented by Bravyi and Kitaev [7].”
OpenQASM 3: A Broader and Deeper Quantum Assembly Language (2021, background): “For instance, defcal rx(angle[20] θ) $q defines the implementation of a rx gate of any angle on any physical qubit $q, whereas defcal rx(π) $0 specifically targets an X rotation of π radians on physical qubit $0.”
Quantum accuracy threshold for concatenated distance-3 codes (2005, background): “However, an optimized estimate using topological codes of the computation threshold has not been attempted, as the purification protocol for the C3 ancilla is rather complicated in this case [40].”
Why I am optimistic about the silicon-photonic route to quantum computing (2016, background): “However, with magic state injection techniques [2] the measurements need only be Pauli-X and Z basis measurements, and the whole tree structure is designed to allow inference of these outcomes counterfactually when a photon is lost.”
Superconducting nanocircuits for topologically protected qubits (2008, methodology): “Together with the measurements and R (π/8) rotations, these operations are sufficient for an arbitrary quantum computatio”
Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer (2020, background): “Several different magic state distillation procedures exist [133–138].”
Many-Body Quantum Magic (2020, methodology): “However, adding a non-Clifford unitary gate restores universality, and it was observed by Bravyi and Kitaev [42] that the same results when a pure “magic” state is made available.”
Toward the first quantum simulation with quantum speedup (2017, background): “Finally, rather than using only the T = Rz(π/4) gate, one may also distill Rz(π/6) with comparable or better efficiency as the T gate [18].”
Scalable designs for quasiparticle-poisoning-protected topological quantum computation with Majorana zero modes (2016, background): “The fundamental virtue of magic states is that they may be distilled using only Clifford operations [81].”
Protected gates for superconducting qubits (2013, methodology): “The analysis in [12] then shows that, by applying the state distillation ideas from [11], scalable quantum computing can achieved by augmenting the CNOT gadget with |−i〉 and |e−iπ/4〉 preparations having the relatively high error rate εm.”
The resource theory of stabilizer quantum computation (2013, methodology): “The resolution is to perform “magic state distillation” [6], wherein stabilizer operations are used to distill a large number of these highly mixed resource states into a small number of very pure resource states.”