Computing with highly mixed states

Abstract

We consider quantum computing in the k-qubit model where the starting state of a quantum computer consists of k qubits in a pure state and n-k qubits in a maximally mixed state. We ask the following question: is there a general method for simulating an arbitrary m-qubit pure state quantum computation by a quantum computation in the k-qubit model? We show that, under certain constraints, this is impossible, unless m=O(k+ log n).

8 pages, 3 figures, to appear in proceedings of STOC'00

References in corpus (2)

• On the Power of One Bit of Quantum Information
• Experimental realization of a quantum algorithm

Cited by in corpus (6)

• Unknown Quantum States: The Quantum de Finetti Representation
• Quantum Computing Without Entanglement
• Introduction to NMR Quantum Information Processing
• Quantum and Stochastic Branching Programs of Bounded Width
• Studies on the Role of Entanglement in Mixed-state Quantum Computation
• On the hardness of distinguishing mixed-state quantum computations