What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.

Quais são as vantagens que a computação quântica pode oferecer em relação à computação clássica? O objetivo desta tese é responder a esta pergunta sob diferentes perspectivas, com este intuito, dividimos este trabalho em três partes. Na primeira parte começamos a estudar os princípios básicos da computação quântica. Em seguida apresentamos dois algoritmos quânticos; o algoritmo de Deutsch-Jozsa e o algoritmo de Grover. O primeiro possui uma menor complexidade de query, já o segundo possui uma menor complexidade de tempo quando comparados aos melhores algoritmos clássicos para os mesmos problemas. O último tópico é uma explicação detalhada com um exemplo de como utilizar o algoritmo de Grover para resolver uma fórmula booleana expressa na forma normal conjuntiva. Na segunda parte abordamos problemas de complexidade de comunicação. Estes problemas normalmente envolvem duas pessoas, Alice e Bob, que em locais separados recebem um input de um juiz. O objetivo deles é calcular o valor de uma função que depende dos seus inputs com a menor quantidade de comunicação entre eles. Nesta parte, apresentamos protocolos nos quais a transmissão de bits quânticos (qubits), ao invés de bits, podem reduzir a quantidade de comunicação necessária para resolver estes tipos de problemas. Também estudamos como Alice e Bob podem utilizar o emaranhamento quântico para resolver dois problemas de complexidade de comunicação sem que haja comunicação entre ambos, algo que não pode ser feito classicamente. Na Parte III estudamos jogos não-locais inspirados em parâmetros usuais da teoria dos grafos. Jogos não-locais são definidos como jogos em que jogadores que podem compartilhar e operar em um estado emaranhado possuem algum tipo de vantagem sobre jogadores clássicos. Iniciamos esta última parte apresentando o número cromático quântico de um grafo. Esta quantidade representa o menor número de cores necessárias para Alice e Bob convencerem um juiz que possuem uma coloração própria de um grafo ao jogarem um jogo não-local. Terminamos esta tese apresentando outros dois parâmetros quânticos de grafos, um relacionado ao homomorfismo de grafos e o outro ao número de independência de um grafo.