Computing with highly mixed states

Andris Ambainis, Leonard J. Schulman, Umesh Vazirani

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…