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

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2006-05, Vol.53 (3), p.507-531
Main Authors: AMBAINIS, Andris, SCHULMAN, Leonard J, VAZIRANI, Umesh
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Circuits
Classical and quantum physics: mechanics and fields
Cleaning
Computation
Computer programming
Computer science
Computer science
control theory
systems
Computer simulation
Computers
Cooling
Devices
Exact sciences and technology
Hilbert space
Laboratories
Physics
Probability
Quantum computation
Quantum computers
Quantum computing
Quantum information
Qubits (quantum computing)
Registers
Simulation
Studies
Theoretical computing
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0004-5411
1557-735X
DOI:10.1145/1147954.1147962