Polynomial simulations of decohered quantum computers

Recently it has become clear, that a key issue in quantum computation is understanding how interaction with the environment, or "decoherence", affects the computational power of quantum computers. We adopt the standard physical method of describing systems which are interwound with their environment by "density matrices", and within this framework define a model of decoherence in quantum computation. Our results show that the computational power of decohered quantum computers depends strongly on the amount of parallelism in the computation. We first present a simulation of decohered sequential quantum computers, on a classical probabilistic Turing machine, and prove that the expected slowdown of this simulation is polynomial in time and space of the quantum computation, for any non zero decoherence rate. Similar results hold for quantum computers that are allowed to operate on logarithmic number of qubits at a time. For decohered quantum circuits (with local gates), the situation is more subtle and depends on the decoherence rate, /spl eta/. We find that our simulation is efficient for circuits with decoherence rate /spl eta/ higher than some constant /spl eta//sub 1/ but exponential for a general (random) circuit subjected to decoherence rate lower than some constant /spl eta//sub 2/. The transition from exponential cost to polynomial cost happens in a short range of decoherence rates. We use computer experiments to exhibit the phase transitions in various quantum circuits.