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

27

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(n)

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

Lagarto discreto
fonte

Respostas:

20

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|10011|0011

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 queU

U|a=|a,U|b=|b

onde é a cadeia de bits para o qual a função retornaria e é qualquer para que ele retornaria .aTruebFalse

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 .12nnU12n

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 efeitobj

D:jαj|bjj(2μαj)|bj

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 .μ=jαjμ+δμδ

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.12n

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.12n

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.

James Wootton
fonte
4

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 0|ψ|xx|ψ0
  • podemos implementar uma operaçãoU1=(I2|ψψ|)
  • podemos implementar uma operação.U2=I2|xx|

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 }|ψ|x{|x,|ψ}{|x,|ψ}{|x,|ψ}

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 |ψ|xinsira a descrição da imagem aqui

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 q|ψ|x|ψ|ψ|ψ|ψθinsira a descrição da imagem aqui

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 . U1|ψU2|ψinsira a descrição da imagem aqui

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 . U2U12θ|xinsira a descrição da imagem aqui

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.|ψθ|xx

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|ψp1O(1/p)p=sinθθθrsin((2r+1)θ)1rπ2θπ2p

DaftWullie
fonte
3

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/N 1N1

pirâmides
fonte