Algoritmo mais simples para demonstrar intuitivamente a aceleração quântica?

Qual é o algoritmo mais simples (como o algoritmo de Deutsch e algoritmo de Grover ) para intuitivamente demonstrando aceleração quântica? E esse algoritmo pode ser explicado intuitivamente?

Idealmente, isso também ilustraria claramente como a interferência quântica está sendo utilizada e por que não é possível ou útil usar apenas a interferência das ondas clássicas .

Gostaria de sugerir que a descoberta de períodos (uma sub-rotina, se você preferir, do famoso algoritmo Shor) demonstra uma aceleração exponencial muito intuitiva: deve ficar intuitivamente claro que algo da ordem de (a raiz quadrada da incerteza) ) do período de avaliações de funções é exigido classicamente para encontrar um período desconhecido de uma função que é garantida como periódica em seu valor de entrada inteiro. Eu deliberadamente coloquei a parênteses, de modo que o conteúdo deles seja intuitivo para as pessoas que profundamente enraizaram o paradoxo do aniversário, para demonstrar uma aceleração superpolinomial, é suficiente entender intuitivamente que está em algum lugar próximo de , a resposta correta$\Delta p$$p$$p$$\Delta p$$\sqrt{\Delta p}$ , ou algum polinômio do mesmo e não algo como o número de dígitos de , .$p$$O(\log p)$

O algoritmo quântico para a descoberta de períodos, conforme empregado pelo algoritmo de Shor, simplesmente toma a transformada quântica de Fourier da função periódica aplicada à igual superposição de todos os estados. Naturalmente, apenas múltiplos inteiros do período podem ter uma amplitude de probabilidade diferente de zero; portanto, fazer isso (normalmente) duas vezes permitirá extrair rapidamente o fator comum como o maior denominador comum. Mas uma transformação quântica de Fourier é trivialmente implementável por rotações controladas por (uma por cada bit de entrada).$O(\log p)$

A maior aceleração intuitiva ocorre obviamente se você fizer a avaliação da função muito cara: O algoritmo quântico exige apenas uma avaliação constante (única)! Mas mesmo assim você obtém um ganho, pois possui um algoritmo que é executado, assumindo que as avaliações das funções são constantes, em e não em que, se você não tem idéia de o período correto é essencialmente .$O(\log p)$$O(\sqrt{\Delta p})$$p$$O(\sqrt{p})$

A dificuldade com a pergunta é a palavra intuitiva . A intuição reflete basicamente nossa compreensão do mundo ao nosso redor, descrito pela física clássica. A mecânica quântica é exatamente o regime em que nossa intuição se desintegra porque funciona de maneira muito diferente do mundo de nossa experiência cotidiana. Como Terry Pratchett disse:

É muito difícil falar de quantum usando uma linguagem originalmente projetada para dizer a outros macacos onde está a fruta madura.

É exatamente essa diferença que estamos usando para obter a velocidade computacional.

Há uma sequência de algoritmos padrão pelos quais a maioria dos textos de computação quântica progride: algoritmo de Deutsch , Deutsch-Jozsa , Simon / Bernstein-Vazirani. Estes são escolhidos porque são os mais fáceis de entender. Todos eles têm a mesma estrutura, mas aumentando a complexidade, com um ganho correspondente em velocidade computacional (com Simon dando aceleração exponencial). Você não os entenderá intuitivamente. Você tem que fazer as contas. Acho que o mais próximo que você chegará é da seguinte explicação do algoritmo de Deutsch:

$f(x)$$f(0)=f(1)$$f(0)$$f(1)$$f(0)\oplus f(1)$

Há um bom exemplo na palestra da Microsoft . Suponha que você tenha uma caixa preta clássica com 1 entrada e 1 saída. Quantas consultas você precisa para determinar se a saída é constante ou variável? Evidentemente você precisa de 2 consultas; primeiro você insere 0, depois você insere 1; se ambas as saídas forem idênticas, você terá constante, caso contrário, variável. Acontece que, depois de converter a caixa preta clássica em uma caixa preta quântica, você pode construir um circuito que precisa de apenas uma única consulta (a palestra explica como fazê-lo).