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
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
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://teses.usp.br/teses/disponiveis/45/45134/tde-19062023-143615/. Acesso em: 07 maio 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://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 maio 07 ] Available from: https://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 maio 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-19062023-143615/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
