{"data":{"id":"10.48550/arxiv.quant-ph/0403025","type":"dois","attributes":{"doi":"10.48550/arxiv.quant-ph/0403025","prefix":"10.48550","suffix":"arxiv.quant-ph/0403025","identifiers":[{"identifier":"quant-ph/0403025","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"quant-ph/0403025"}],"creators":[{"name":"Bravyi, Sergei","nameType":"Personal","givenName":"Sergei","familyName":"Bravyi","affiliation":[],"nameIdentifiers":[]},{"name":"Kitaev, Alexei","nameType":"Personal","givenName":"Alexei","familyName":"Kitaev","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Universal Quantum Computation with ideal Clifford gates and noisy ancillas"}],"publisher":"arXiv","container":{},"publicationYear":2004,"subjects":[{"lang":"en","subject":"Quantum Physics (quant-ph)","subjectScheme":"arXiv"},{"subject":"FOS: Physical sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2004-03-03T03:05:21Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2009-12-01T03:24:50Z","dateType":"Updated","dateInformation":"v1"},{"date":"2004-12-16T12:49:57Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2020-11-07T03:40:39Z","dateType":"Updated","dateInformation":"v2"},{"date":"2004-03","dateType":"Available","dateInformation":"v1"},{"date":"2004","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1103/physreva.71.022316","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004","rightsUri":"http://arxiv.org/licenses/assumed-1991-2003/"}],"descriptions":[{"description":"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.","descriptionType":"Abstract"},{"description":"15 pages, 4 figures, revtex4","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi5RVUFOVC1QSC8wNDAzMDI1PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+cXVhbnQtcGgvMDQwMzAyNTwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5CcmF2eWksIFNlcmdlaTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+U2VyZ2VpPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkJyYXZ5aTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5LaXRhZXYsIEFsZXhlaTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+QWxleGVpPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPktpdGFldjwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+VW5pdmVyc2FsIFF1YW50dW0gQ29tcHV0YXRpb24gd2l0aCBpZGVhbCBDbGlmZm9yZCBnYXRlcyBhbmQgbm9pc3kgYW5jaWxsYXM8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMDQ8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5RdWFudHVtIFBoeXNpY3MgKHF1YW50LXBoKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IFBoeXNpY2FsIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwNC0wMy0wM1QwMzowNToyMVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwOS0xMi0wMVQwMzoyNDo1MFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDA0LTEyLTE2VDEyOjQ5OjU3WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIwLTExLTA3VDAzOjQwOjM5WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDQtMDM8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8cmVsYXRlZElkZW50aWZpZXJzPgogICAgPHJlbGF0ZWRJZGVudGlmaWVyIHJlbGF0ZWRJZGVudGlmaWVyVHlwZT0iRE9JIiByZWxhdGlvblR5cGU9IklzVmVyc2lvbk9mIj4xMC4xMTAzL1BoeXNSZXZBLjcxLjAyMjMxNjwvcmVsYXRlZElkZW50aWZpZXI+CiAgPC9yZWxhdGVkSWRlbnRpZmllcnM+CiAgPHZlcnNpb24+MjwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL2Fzc3VtZWQtMTk5MS0yMDAzLyI+QXNzdW1lZCBhclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2UgdG8gZGlzdHJpYnV0ZSB0aGlzIGFydGljbGUgZm9yIHN1Ym1pc3Npb25zIG1hZGUgYmVmb3JlIEphbnVhcnkgMjAwNDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGNvbnNpZGVyIGEgbW9kZWwgb2YgcXVhbnR1bSBjb21wdXRhdGlvbiBpbiB3aGljaCB0aGUgc2V0IG9mIGVsZW1lbnRhcnkgb3BlcmF0aW9ucyBpcyBsaW1pdGVkIHRvIENsaWZmb3JkIHVuaXRhcmllcywgdGhlIGNyZWF0aW9uIG9mIHRoZSBzdGF0ZSAkfDBccmFuZ2xlJCBjb21wdXRhdGlvbmFsIGJhc2lzLiBJbiBhZGRpdGlvbiwgd2UgYWxsb3cgdGhlIGNyZWF0aW9uIG9mIGEgb25lLXF1Yml0IGFuY2lsbGEgaW4gYSBtaXhlZCBzdGF0ZSAkz4EkLCB3aGljaCBzaG91bGQgYmUgcmVnYXJkZWQgYXMgYSBwYXJhbWV0ZXIgb2YgdGhlIG1vZGVsLiBPdXIgZ29hbCBpcyB0byBkZXRlcm1pbmUgZm9yIHdoaWNoICTPgSQgdW5pdmVyc2FsIHF1YW50dW0gY29tcHV0YXRpb24gKFVRQykgY2FuIGJlIGVmZmljaWVudGx5IHNpbXVsYXRlZC4gVG8gYW5zd2VyIHRoaXMgcXVlc3Rpb24sIHdlIGNvbnN0cnVjdCBwdXJpZmljYXRpb24gcHJvdG9jb2xzIHRoYXQgY29uc3VtZSBzZXZlcmFsIGNvcGllcyBvZiAkz4EkIGFuZCBwcm9kdWNlIGEgc2luZ2xlIG91dHB1dCBxdWJpdCB3aXRoIGhpZ2hlciBwb2xhcml6YXRpb24uIFRoZSBwcm90b2NvbHMgYWxsb3cgb25lIHRvIGluY3JlYXNlIHRoZSBwb2xhcml6YXRpb24gb25seSBhbG9uZyBjZXJ0YWluICJtYWdpYyIgZGlyZWN0aW9ucy4gSWYgdGhlIHBvbGFyaXphdGlvbiBvZiAkz4EkIGFsb25nIGEgbWFnaWMgZGlyZWN0aW9uIGV4Y2VlZHMgYSB0aHJlc2hvbGQgdmFsdWUgKGFib3V0IDY1JSksIHRoZSBwdXJpZmljYXRpb24gYXN5bXB0b3RpY2FsbHkgeWllbGRzIGEgcHVyZSBzdGF0ZSwgd2hpY2ggd2UgY2FsbCBhIG1hZ2ljIHN0YXRlLiBXZSBzaG93IHRoYXQgdGhlIENsaWZmb3JkIGdyb3VwIG9wZXJhdGlvbnMgY29tYmluZWQgd2l0aCBtYWdpYyBzdGF0ZXMgcHJlcGFyYXRpb24gYXJlIHN1ZmZpY2llbnQgZm9yIFVRQy4gVGhlIGNvbm5lY3Rpb24gb2Ygb3VyIHJlc3VsdHMgd2l0aCB0aGUgR290dGVzbWFuLUtuaWxsIHRoZW9yZW0gaXMgZGlzY3Vzc2VkLjwvZGVzY3JpcHRpb24+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJPdGhlciI+MTUgcGFnZXMsIDQgZmlndXJlcywgcmV2dGV4NDwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/quant-ph/0403025","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-18T15:45:12.000Z","registered":"2022-03-18T15:45:14.000Z","published":"2004","updated":"2022-03-18T15:45:14.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.quant-ph/0403025","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}