Introdução
Os algoritmos quânticos oferecem vantagens comprovadas sobre os algoritmos clássicos no modelo de computação por consultas. Mas e quanto a um modelo de computação mais padrão, onde as entradas do problema são fornecidas explicitamente, em vez de na forma de um oráculo ou caixa-preta? Essa acaba sendo uma questão muito mais difícil de responder e, para abordá-la, precisamos primeiro estabelecer uma base sólida sobre a qual fundamentar nossa investigação. Esse é o objetivo principal desta lição.
Começaremos discutindo o custo computacional, tanto para computações clássicas quanto quânticas, e como ele pode ser medido. Trata-se de uma noção geral que pode ser aplicada a uma ampla variedade de problemas computacionais — mas, para manter as coisas simples, vamos examiná-la principalmente pela perspectiva da teoria computacional dos números, que aborda tarefas computacionais que provavelmente são familiares à maioria dos leitores, incluindo aritmética básica, cálculo do máximo divisor comum e fatoração de inteiros. Embora a teoria computacional dos números seja um domínio de aplicação restrito, esses problemas servem bem para ilustrar as questões fundamentais (e também são altamente relevantes para a lição seguinte).
Nosso foco está nos algoritmos, e não no hardware em constante melhoria no qual eles são executados. Consequentemente, estaremos mais preocupados em como o custo de execução de um algoritmo escala à medida que as instâncias específicas do problema crescem em tamanho, do que em quantos segundos, minutos ou horas uma determinada computação exige. Focamos nesse aspecto do custo computacional reconhecendo que os algoritmos têm importância fundamental e, naturalmente, serão aplicados a instâncias de problemas cada vez maiores usando hardware mais rápido e confiável à medida que a tecnologia avança.
Por fim, abordaremos uma tarefa de importância crítica: a execução de computações clássicas em computadores quânticos. O motivo pelo qual essa tarefa é importante não é que esperamos substituir os computadores clássicos por computadores quânticos — o que parece extremamente improvável de acontecer tão cedo, se é que vai acontecer — mas sim porque ela abre muitas possibilidades interessantes para algoritmos quânticos. Especificamente, computações clássicas executadas em computadores quânticos tornam-se disponíveis como sub-rotinas, aproveitando efetivamente décadas de pesquisa e desenvolvimento em algoritmos clássicos na busca por vantagens computacionais quânticas.
Vídeo da lição
No vídeo a seguir, John Watrous guia você pelo conteúdo desta lição sobre fundamentos algorítmicos quânticos. Como alternativa, você pode abrir o vídeo no YouTube desta lição em uma janela separada. Baixe os slides desta lição.