Teoría de la Complejidad en Computación Cuántica

Abstract

During the rst half of the 20th century, the need of faster calculations brought the rst computers to our world. Those machines were designed following the same abstract blueprint: a structure called Turing Machine. Since then, the creation and improvement of algorithms solvingwell known mathematical problems have continued. Following the same path, scientists from di erent areas studied the complexity theory around classical computers. In 1982 American physicist Richard Feynman stepped out of this paradigm when he realized that quantum systems could not be e ciently simulated using any of the previous computers. British physicist David Deutsch introduced a new machine based on this idea in 1985, named quantum Turing machines, given the similarities with Turing machines and the fact that it took advantage of the principles of quantum mechanics. After the formal de nition, quantum complexity theory and algorithms appeared hand by hand. In this memory we will take a look into the construction of an universal quantum Turing machine and its associated complexity theory, which is still an open and fruitful eld of current research. Next, we will present an algoritm stated by David Deutsch and Australian mathematician Richard Jozsa in 1992 as an example of the intrinsic power inside quantum Turing machines.