Introdução

Nesta primeira lição do curso, formularemos uma estrutura algorítmica simples - conhecida como modelo de consulta - e exploraremos as vantagens que os computadores quânticos oferecem dentro dessa estrutura.

O modelo de consulta da computação é como uma placa de Petri para ideias de algoritmos quânticos. Ele é rígido e antinatural no sentido de que não representa com precisão os tipos de problemas computacionais com os quais geralmente nos preocupamos na prática, mas, mesmo assim, provou ser incrivelmente útil como ferramenta para o desenvolvimento de técnicas algorítmicas quânticas. Isso inclui os que alimentam os algoritmos quânticos mais conhecidos, como o algoritmo de Shor para fatoração de números inteiros. O modelo de consulta também é uma estrutura muito útil para explicar as técnicas de algoritmo quântico.

Depois de apresentar o modelo de consulta em si, discutiremos o primeiro algoritmo quântico descoberto, que é o algoritmo de Deutsch, juntamente com uma extensão do algoritmo de Deutsch conhecida como algoritmo Deutsch-Jozsa. Esses algoritmos demonstram vantagens quantificáveis dos computadores quânticos em relação aos clássicos no contexto do modelo de consulta. Em seguida, discutiremos um algoritmo quântico conhecido como algoritmo de Simon, que oferece uma vantagem mais robusta e satisfatória da computação quântica em relação à clássica, por motivos que serão explicados quando chegarmos a ele.

Vídeo da aula

No vídeo a seguir, John Watrous orienta você pelo conteúdo desta lição sobre algoritmos de consulta quântica. Como alternativa, você pode abrir o vídeo YouTube para esta lição em uma janela separada. Faça o download dos slides para esta lição.