Quantum computation

We describe how physics of computation determines computational complexity. In particular we show how quantum phenomena lead to qualitatively new modes of computation. An ideal quantum computer would allow to face certain tasks out of reach of classical computers, the factorization problem being the most striking example. Experimentally, however, implementation of quantum computation faces some serious difficulties due to an interaction with the environment which causes decoherence. We mention quantum error-correction as a process which can, to some extent, protect quantum computers from unwelcome effects of dissipation and decoherence. This is a brief, introductory review of quantum computation. It is based on [1]