Relações entre classes de problemas computacionais: um estudo sobre classes de complexidade quânticas

Abstract

Computadores quânticos são cada vez uma realidade menos distante e, com eles, vem a grande expectativa de melhorar a eficiência de algoritmos que buscam resolver diversos tipos de problemas considerados intratáveis classicamente. Neste sentido, será feito neste trabalho um estudo sobre modelos teóricos de computação e as principais classes de complexidade clássicas e quânticas, mostrando relações de contingência e equivalência entre elas, de forma a definir os limites da computação quântica sobre aspectos teóricos de computabilidade e tratabilidade. Definindo também as principais relações em aberto e conjecturas na literatura sobre a teoria da complexidade computacional quântica.

Quantum computers are increasingly less distant reality and, with them, comes a great expectation of improving the efficiency of algorithms that seek to solve different types of problems considered classically intractable. In this sense, a study on theoretical models of computation and the main classical and quantum complexity classes will be done, showing contingency and equivalence relations between them, in order to define the limits of quantum computing on theoretical aspects of computability and treatability. Also defining the main open relationships and conjectures in the literature on the theory of quantum computational complexity.