Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2006 | public
Journal Article

Computing with Highly Mixed States


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.

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.

Additional details

August 19, 2023
October 18, 2023