• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2022.tde-19062023-143615
Documento
Autor
Nome completo
Lucas Silva Arenstein
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2022
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Coutinho, Gabriel de Morais
Cunha, Marcelo de Oliveira Terra
Título em inglês
An introduction to quantum: computing, communication complexity protocols, nonlocality and graph parameters
Palavras-chave em inglês
Grovers algorithm
Nonlocality
Quantum algorithms
Quantum chromatic number
Quantum communication complexity
Quantum computing
Quantum graph parameters
Resumo em inglês
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.
Título em português
Uma introdução à computação quântica, protocolos de complexidade de comunicação quânticos, não-localidade e parâmetros quânticos de grafos
Palavras-chave em português
Algoritmo de Grover
Algoritmos quânticos
Complexidade de comunicação quântica
Computação quântica
Não-localidade
Número cromático quântico
Parâmetros quânticos de grafos
Resumo em português
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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Arenstein_Msc_Thesis.pdf (780.06 Kbytes)
Data de Publicação
2023-06-22
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.