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. doi:10.1145/1147954.1147962.

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

Use this Persistent URL to link to this item:


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 Paper
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.
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Canadian Institute for Advanced Research (CIAR)UNSPECIFIED
Institute for Quantum ComputingUNSPECIFIED
Army Research Office (ARO)W911NF-05-1-0294
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:
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=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66277
Deposited On:19 Apr 2016 20:17
Last Modified:10 Nov 2021 23:55

Repository Staff Only: item control page