Hirvensalo M. Quantum Computing

Springer, 2001. — 202.In this book, we typically identify the alphabet and the distinguishable states of a physical system that represent the information. These identifiable states are called basis states. In quantum physical microsystems, there are also basis states that can be identified and, therefore, we could use such microsystems to represent information. But, unlike the systems of classical physics, these microsystems are also able to exist in a superposition of basis states, which, informally speaking, means that the state of such a system can also be a combination of basis states. We will call the information represented by such microsystems quantum information. One may argue that in classical physics it is also possible to speak about combinations of basis states: we can prepare a mixed state which is essentially a probability distribution of the basis states. But there is a difference between the superpositions of quantum physics and the probability distributions of classical physics: due to the interference effects, the superpositions cannot be interpreted as mixtures (probability distributions) of the basis states.
Richard Feynman pointed out in 1982 that it appears to be extremely difficult by using an ordinary computer to simulate efficiently how a quantum physical system evolves in time. He also demonstrated that, if we had a computer that runs according to the laws of quantum physics, then this simulation could be made efficiently. Thus, he actually suggested that a quantum computer could be essentially more efficient than any traditional one.
Therefore, it is an interesting challenge to study quantum computation, the theory of computation in which traditional information is replaced by its quantum physical counterpart. Are quantum computers more powerful than traditional ones? If so, what are the problems that can be solved more efficiently by using a quantum computer? These questions are still waiting for answers.
The purpose of this book is to provide a good introduction to quantum computation for beginners, as well as a clear presentation of the most important presently known results for more advanced readers. The latter purpose also includes providing a bridge (from a mathematician's point of view) between quantum mechanics and the theory of computation: it is not only my personal experience that the language used in research articles on these topics is completely different.Devices for Computation
Fast Factorization
Finding the Hidden Subgroup
Grover's Search Algorithm
Complexity Lower Bounds for Quantum Circuits
A: Quantum Physics
B: Mathematical Background