Basic ideas of classical and quantum computational models and complexity classes

In this chapter we briefly describe the basic ideas of classical and quantum computational models. To be precise, we will provide an overview of the classical (irreversible, probabilistic and reversible) and quantum Turing machines, the need for error correction and the quantum circuit model of computation. We also describe a few complexity classes that are relevant for the study of quantum computing and quantum cryptography.