An introduction to quantum computing: communication complexity protocols, nonlocality and graph parameters (2022)
- Authors:
- Autor USP: ARENSTEIN, LUCAS SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2022.tde-19062023-143615
- Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; COMPUTAÇÃO QUÂNTICA
- Keywords: Algoritmo de Grover; Algoritmos quânticos; Complexidade de comunicação quântica; Grovers algorithm; Não-localidade; Nonlocality; Número cromático quântico; Parâmetros quânticos de grafos; Quantum algorithms; Quantum chromatic number; Quantum communication complexity; Quantum computing; Quantum graph parameters
- Agências de fomento:
- Language: Inglês
- Abstract: 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 feitoclassicamente. 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
- Imprenta:
- Data da defesa: 12.12.2022
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
ARENSTEIN, Lucas Silva. An introduction to quantum computing: communication complexity protocols, nonlocality and graph parameters. 2022. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2022. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-19062023-143615/. Acesso em: 05 jan. 2026. -
APA
Arenstein, L. S. (2022). An introduction to quantum computing: communication complexity protocols, nonlocality and graph parameters (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-19062023-143615/ -
NLM
Arenstein LS. An introduction to quantum computing: communication complexity protocols, nonlocality and graph parameters [Internet]. 2022 ;[citado 2026 jan. 05 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-19062023-143615/ -
Vancouver
Arenstein LS. An introduction to quantum computing: communication complexity protocols, nonlocality and graph parameters [Internet]. 2022 ;[citado 2026 jan. 05 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-19062023-143615/
Informações sobre o DOI: 10.11606/D.45.2022.tde-19062023-143615 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
