Existe uma explicação para um leigo sobre por que o algoritmo de Grover funciona?

Este post de blog de Scott Aaronson é uma explicação muito útil e simples do algoritmo de Shor .

Gostaria de saber se existe uma explicação para o segundo algoritmo quântico mais famoso: o algoritmo de Grover para pesquisar um banco de dados desordenado do tamanho em .$O(n)$$O(\sqrt{n})$

Em particular, gostaria de ver alguma intuição compreensível para o resultado inicialmente surpreendente do tempo de execução!

Há uma boa explicação de Craig Gidney aqui (ele também tem outro ótimo conteúdo, incluindo um simulador de circuito, em seu blog ).

Essencialmente, o algoritmo de Grover se aplica quando você tem uma função que retorna Truepara uma de suas possíveis entradas e Falsepara todas as outras. O trabalho do algoritmo é encontrar o que retorna True.

Para fazer isso, expressamos as entradas como cadeias de bits e as codificamos usando os estados e de uma cadeia de qubits. Portanto, a cadeia de bits seria codificada no estado de quatro qubit , por exemplo.$|0\rangle$$|1\rangle$0011$|0011\rangle$

Também precisamos ser capazes de implementar a função usando portas quânticas. Especificamente, precisamos encontrar uma sequência de portas que implementem um unitário tal que$U$

$U | a \rangle = - | a \rangle, \,\,\,\,\,\,\,\,\,\,\,\,\, U | b \rangle = | b \rangle$

onde é a cadeia de bits para o qual a função retornaria e é qualquer para que ele retornaria .$a$True$b$False

Se começarmos com uma superposição de todas as sequências de bits possíveis, o que é bastante fácil de fazer apenas com Hadamarding tudo, todas as entradas começam com a mesma amplitude de (onde é o comprimento das cadeias de bits que estamos pesquisando e, portanto, o número de qubits que estamos usando). Mas se aplicarmos o oráculo , a amplitude do estado que estamos procurando mudará para .$\frac{1}{\sqrt{2^n}}$$n$$U$$-\frac{1}{\sqrt{2^n}}$

Esta não é uma diferença facilmente observável, por isso precisamos amplificá-la. Para fazer isso, usamos o Grover Difusão Operator , . O efeito desse operador é essencialmente observar como cada amplitude é diferente da amplitude média e inverter essa diferença. Portanto, se uma certa amplitude for uma certa quantidade maior que a amplitude média, ela se tornará a mesma quantidade menor que a média e vice-versa.$D$

Especificamente, se você tiver uma superposição de cadeias de bits , o operador de difusão o efeito$b_j$

$D: \,\,\,\, \sum_j \alpha_j \, | b_j \rangle \,\,\,\,\,\, \mapsto \,\,\,\,\,\, \sum_j (2\mu \, - \, \alpha_j) \, | b_j \rangle$

onde é a amplitude média. Portanto, qualquer amplitude é transformada em . Para ver por que isso tem esse efeito e como implementá-lo, consulte estas notas de aula .$\mu = \sum_j \alpha_j$$\mu + \delta$$\mu - \delta$

A maioria das amplitudes será um pouco maior que a média (devido ao efeito do single ), então elas se tornarão um pouquinho menos que a média através esta operação. Não é uma grande mudança.$-\frac{1}{\sqrt{2^n}}$

O estado que estamos procurando será afetado mais fortemente. Sua amplitude é muito menor que a média e, portanto, se tornará muito maior após a aplicação do operador de difusão. O efeito final do operador de difusão é, portanto, causar um efeito de interferência nos estados que percorre uma amplitude de de todas as respostas erradas e a adiciona à correta. Repetindo esse processo, podemos chegar rapidamente ao ponto em que nossa solução se destaca tanto da multidão que podemos identificá-la.$\frac{1}{\sqrt{2^n}}$

Obviamente, tudo isso mostra que todo o trabalho é realizado pelo operador de difusão. A pesquisa é apenas um aplicativo que podemos conectar a ele.

Veja as respostas para outras perguntas para obter detalhes sobre como as funções e o operador de difusão são implementados.

Acho uma abordagem gráfica bastante boa para fornecer algumas dicas sem ser muito técnico. Precisamos de algumas entradas:

• podemos produzir um estado com sobreposição diferente de zero com o estado 'marcado' : .| x ⟩ ⟨ x | ip ⟩ ≠ $|\psi\rangle$$|x\rangle$$\langle x|\psi\rangle\neq 0$
• podemos implementar uma operação$U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$
• podemos implementar uma operação.$U_2=\mathbb{I}-2|x\rangle\langle x|$

Esta última operação é a que pode marcar nosso item marcado com uma fase -1. Também podemos definir um estado como ortogonal para modo que o forme uma base ortonormal para o período de . As duas operações que definimos preservam esse espaço: você começa com algum estado no intervalo de e eles retornam um estado dentro do intervalo. Além disso, ambos são unitários, portanto, o comprimento do vetor de entrada é preservado.| x ⟩ { | x ⟩ , | ip ⊥ ⟩ } { | x ⟩ , | ip ⟩ } { | x ⟩ , | ip ⊥ ⟩ $|\psi^\perp\rangle$$|x\rangle$$\{|x\rangle,|\psi^\perp\rangle\}$$\{|x\rangle,|\psi\rangle\}$$\{|x\rangle,|\psi^\perp\rangle\}$

Um vetor de comprimento fixo dentro de um espaço bidimensional pode ser visualizado como a circunferência de um círculo. Então, vamos configurar um círculo com duas direções ortogonais correspondentes a e . | x $|\psi^\perp\rangle$$|x\rangle$

Nosso estado inicial terá pequena sobreposição com e grande sobreposição com . Se fosse o contrário, a pesquisa seria fácil: basta preparar , medir e testar a saída usando a unidade de marcação, repetindo até obter o item marcado. Não demoraria muito. Vamos chamar o ângulo entre e o ângulo . | x ⟩ | ip ⊥ ⟩ | ip ⟩ | ip ⟩ | ip ⊥ ⟩ $|\psi\rangle$$|x\rangle$$|\psi^\perp\rangle$$|\psi\rangle$$|\psi\rangle$$|\psi^\perp\rangle$$\theta$

Agora vamos pensar um pouco no que nossas duas ações unitárias fazem. Ambos têm um autovalor -1 e todos os outros autovalores +1. Em nosso subespaço bidimensional, isso reduz a um autovalor +1 e um autovalor -1. Essa operação é um reflexo no eixo definido pelo vetor próprio +1. Portanto, é um reflexo no eixo , enquanto é um reflexo no eixo . $U_1$$|\psi\rangle$$U_2$$|\psi^\perp\rangle$

Agora, pegue um vetor arbitrário nesse espaço e aplique seguido por . O efeito final é que o vetor é girado por um ângulo direção ao eixo . $U_2$$U_1$$2\theta$$|x\rangle$

Portanto, se você começar com , poderá repeti-lo o suficiente várias vezes e chegar a um ângulo de . Assim, quando medimos esse estado, obtemos o valor com alta probabilidade.$|\psi\rangle$$\theta$$|x\rangle$$x$

Agora precisamos de um pouco de cuidado para encontrar a velocidade. Suponha que a probabilidade de encontrar em seja . Então, classicamente, precisamos de tentativas para encontrá-lo. Em nosso cenário quântico, temos que (já que é pequeno) e queremos um número de execuções tais que . . Então, . Você pode ver a aceleração da raiz quadrada ali.$|x\rangle$$|\psi\rangle$$p\ll 1$$O(1/p)$$\sqrt{p}=\sin\theta\approx\theta$$\theta$$r$$\sin((2r+1)\theta)\approx 1$$r\approx \frac{\pi}{2\theta}\approx \frac{\pi}{2\sqrt{p}}$

A explicação simples de como (e, portanto, por que) o algoritmo de Grover funciona é que uma porta quântica só pode reorganizar (ou distribuir) amplitudes de probabilidade. Usando um estado inicial com amplitudes de probabilidade iguais para todos os estados da base computacional, começa-se com uma amplitude de . Isso pode ser "adicionado" ao estado desejado (solução) em cada iteração, de forma que após as iterações chegue a uma amplitude de probabilidade de significa que o estado desejado foi destilado.$1/\sqrt{N}$$\sqrt{N}$$1$