Quantum computers and dissipation

We analyse dissipation in quantum computation and its destructive impact on efficiency of quantum algorithms. We discuss relations between decoherence and computational complexity and show that quantum factorisation algorithm must be modified in order to be regarded as efficient and realistic. Our model od decoherence is quite general and incorporates reservoirs with a large coherence length. 1 Introduction Quantum computers can accept input states which represent a coherent superposition of many different possible inputs and subsequently evolve them into a corresponding superposition of outputs. Computation, i.e. a sequence of unitary transformations, affects simultaneously each element of the superposition generating a massive parallel data processing albeit within one piece of quantum hardware. As the result quantum computers can efficiently solve some problems which are believed to be intractable on any classical computer (Deutsch 1985, Deutsch and Jozsa 1992, Bernstein and Vazira...