Quantum Walks and Search Algorithms

Book Preface

Quantum mechanics has changed the way we understand the physical world and has introduced new ideas that are difficult to accept, not because they are complex, but because they are different from what we are used to in our everyday lives. Those new ideas can be collected in four postulates or laws. It is hard to believe that Nature works according to those laws, and the difficulty starts with the notion of the superposition of contradictory possibilities. Do you accept the idea that a billiard ball could rotate around its axis in both directions at the same time? Quantum computation was born from this kind of idea. We know that digital classical computers work with zeroes and ones and that the value of the bit cannot be zero and one at the same time. The classical algorithms must obey Boolean logic. So, if the coexistence of bit-0 and bit-1 is possible, which logic should the algorithms obey?

Quantum computation was born from a paradigm change. Information storage, processing and transmission obeying quantum mechanical laws allowed the development of new algorithms, faster than the classical analogues, which can be implemented in physics laboratories. Nowadays, quantum computation is a wellestablished area with important theoretical results within the context of the theory of computing, as well as in terms of physics, and has raised huge engineering challenges to the construction of the quantum hardware.

The majority of people, who are not familiar with the area and talk about quantum computers, expect that the hardware development would obey the famous Moore’s law, valid for classical computer development for fifty years. Many of those people are disappointed to learn about the enormous theoretical and technological difficulties to be overcome to harness and control memory size of a few atoms, where quantum laws hold in their fullness. The construction of the quantum computer requires a technology beyond the semiclassical barrier, which guides the construction of semiconductors used in classical computers, and something equivalent, completely quantum, should be developed to implement elementary logical operations in some sub-nano scale.