Introduction to Quantum Physics and Information Processing

Chapter 6

Computation Models and

Computational Complexity

Now that we have the laws for qubits, we need to develop a system for meaning-

fully manipulating them. Much of the current paradigm for quantum comput-

ing is motivated by classical computation theory, especially the circuit model

for computation. In this chapter, we will briefly overview the classical model

of Boolean circuit theory, and also some of the theoretical concepts involved

in classifying the computational complexity of problems. Roger Penrose [53]

has a beautiful account of the history of the theory of computation. Another

wonderful book on similar lines is that of Douglas Hofstadter ...