Computing with highly mixed states
Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani · Journal of the ACM · 2006
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.