# Universal Quantum Computation with ideal Clifford gates and noisy ancillas

Preprint · Sergei Bravyi, Alexei Kitaev

- Archive id: arxiv:quant-ph/0403025
- Published: 2004-03-03
- Venue: Phys. Rev. A 71, 022316 (2005)
- DOI: https://doi.org/10.1103/physreva.71.022316
- arXiv: https://arxiv.org/abs/quant-ph/0403025
- Source URL: https://arxiv.org/abs/quant-ph/0403025
- PDF: https://arxiv.org/pdf/quant-ph/0403025
- Provenance: arxiv

## Abstract

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\\rangle$ computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state $ρ$, which should be regarded as a parameter of the model. Our goal is to determine for which $ρ$ universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of $ρ$ 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 $ρ$ 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Error Correction & Fault Tolerance](https://space-kitty.com/topics/quantum-error-correction)

Cited in dossiers:
- [Quantum Error Correction & Fault Tolerance: State of the Field (October 2026)](https://space-kitty.com/dossiers/quantum-error-correction)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.