CaltechAUTHORS
  A Caltech Library Service

Universal quantum computation with ideal Clifford gates and noisy ancillas

Bravyi, Sergey and Kitaev, Alexei (2005) Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (Art no). pp. 1-14. ISSN 1050-2947. http://resolver.caltech.edu/CaltechAUTHORS:BRApra05

[img]
Preview
PDF
See Usage Policy.

184Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRApra05

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>, 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.


Item Type:Article
Additional Information:©2005 The American Physical Society (Received 6 May 2004; published 22 February 2005) We thank Mikhail Vyalyi for bringing to our attention many useful facts about the Clifford group. This work has been supported in part by the National Science Foundation under Grant No. EIA-0086038.
Record Number:CaltechAUTHORS:BRApra05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BRApra05
Alternative URL:http://dx.doi.org/10.1103/PhysRevA.71.022316
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1053
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:14 Dec 2005
Last Modified:26 Dec 2012 08:42

Repository Staff Only: item control page