CaltechAUTHORS
  A Caltech Library Service

Computing with Highly Mixed States

Ambainis, Andris and Schulman, Leonard J. and Vazirani, Umesh (2006) Computing with Highly Mixed States. Journal of the ACM, 53 (3). pp. 507-531. ISSN 0004-5411. https://resolver.caltech.edu/CaltechAUTHORS:20160419-113716190

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160419-113716190

Abstract

Device initialization is a difficult challenge in some proposed realizations of quantum computers, and as such, must be treated as a computational resource. The degree of initialization can be quantified by k, the number of clean qubits in the initial state of the register. In this article, we show that unless m ∈ O(k + log n), oblivious (gate-by-gate) simulation of an ideal m-qubit quantum circuit by an n-qubit circuit with k clean qubits is impossible. Effectively, this indicates that there is no avoiding physical initialization of a quantity of qubits proportional to that required by the best ideal quantum circuit.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/1147954.1147962DOIArticle
http://dl.acm.org/citation.cfm?doid=1147954.1147962PublisherArticle
http://arxiv.org/abs/quant-ph/0003136arXivDiscussion Paper
ORCID:
AuthorORCID
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2006 ACM. RECEIVED AUGUST 2004; REVISED SEPTEMBER 2005; ACCEPTED SEPTEMBER 2005. A. Ambainis was supported in part by NSERC, ARDA, CIAR, and an IQC University Professorship. L. J. Schulman was supported in part by National Science Foundation (NSF) grant CCF-0524828 and by the Institute for Quantum Information under NSF EIA-0086038, NSF PHY-0456720, and ARO W911NF-05-1-0294. U. Vazirani was supported in part by NSF CCF-0524837 and ARO DAAD19-03-1-0082.
Funders:
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
ARDAUNSPECIFIED
Canadian Institute for Advanced Research (CIAR)UNSPECIFIED
Institute for Quantum ComputingUNSPECIFIED
NSFCCF-0524828
NSFEIA-0086038
NSFPHY-0456720
Army Research Office (ARO)W911NF-05-1-0294
NSFCCF-0524837
Army Research Office (ARO)DAAD19-03-1-0082
Institute for Quantum InformationUNSPECIFIED
Subject Keywords:Algorithms, Theory, Quantum Computation
Issue or Number:3
Classification Code:F.1 [Theory of Computation]: Computation by Abstract Devices
Record Number:CaltechAUTHORS:20160419-113716190
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160419-113716190
Official Citation:Andris Ambainis, Leonard J. Schulman, and Umesh Vazirani. 2006. Computing with highly mixed states. J. ACM 53, 3 (May 2006), 507-531. DOI=http://dx.doi.org/10.1145/1147954.1147962
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66277
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:19 Apr 2016 20:17
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page