Quantum Computing

"This book is devoted to quantum computing, a new, multidisciplinary research area crossing quantum mechanics, theoretical computer science and mathematics. It contains an introduction to quantum computing as well as the most important recent results on the topic. Two famous algorithms, fast factorization and Grover search, are presented in separate chapters because these inventions are important structurally and developmentally." "The presentation of the topic is uniform and computer science-oriented. Thus, the book differs from most of the previous ones which are mainly physics-oriented. The special style of presentation makes the theory of quantum computing accessible to a larger audience, including also the mathematics-oriented readers. Many examples and exercises ease the understanding."--BOOK JACKET. Read more... 1. Introduction. 1.1. A Brief History of Quantum Computation. 1.2. Classical Physics. 1.3. Probabilistic Systems. 1.4. Quantum Mechanics -- 2. Devices for Computation. 2.1. Classical Computational Models. 2.2. Quantum Information. 2.3. Circuits -- 3. Fast Factorization. 3.1. Quantum Fourier Transform. 3.2. Shor's Algorithm for Factoring Numbers. 3.3. The Correctness Probability. 3.4. Exercises -- 4. Finding the Hidden Subgroup. 4.1. Generalized Simon's Algorithm. 4.2. Examples. 4.3. Exercises -- 5. Grover's Search Algorithm. 5.1. Search Problems. 5.2. Grover's Amplification Method. 5.3. Utilizing Grover's Search Method -- 6. Complexity Lower Bounds for Quantum Circuits. 6.1. General Idea The twentieth century witnessed the birth of revolutionary ideas in the phys­ ical sciences. These ideas began to shake the traditional view of the universe dating back to the days of Newton, even to the days of Galileo. Albert Ein­ stein is usually identified as the creator of the relativity theory, a theory that is used to model the behavior of the huge macrosystems of astronomy. An­ other new view of the physical world was supplied by quantum physics, which turned out to be successful in describing phenomena in the microworld, the behavior of particles of atomic size. Even though the first ideas of automatic information processing are quite old, I feel justified in saying that the twentieth century also witnessed the birth of computer science. As a mathematician, by the term'computer sci­ ence', I mean the more theoretical parts of this vast research area, such as the theory of formal languages, automata theory, complexity theory, and al­ gorithm design. I hope that readers who are used to a more flexible concept of'computer science'will forgive me. The idea of a computational device was crystallized into a mathematical form as a Turing machine by Alan Turing in the 1930s. Since then, the growth of computer science has been immense, but many problems in newer areas such as complexity theory are still waiting for a solution.