Y a-t-il une explication du profane pour expliquer pourquoi l'algorithme de Grover fonctionne?

27

Cet article de blog de Scott Aaronson est une explication très utile et simple de l'algorithme de Shor .

Je me demande s'il existe une telle explication pour le deuxième algorithme quantique le plus célèbre: l'algorithme de Grover pour rechercher une base de données non ordonnée de taille dans O ( O(n)temps.O(n)

En particulier, j'aimerais voir une intuition compréhensible pour le résultat initialement surprenant du temps de course!

Lézard discret
la source

Réponses:

20

Il y a une bonne explication de Craig Gidney ici (il a aussi d'autres excellents contenus, y compris un simulateur de circuit, sur son blog ).

Essentiellement, l'algorithme de Grover s'applique lorsque vous avez une fonction qui renvoie Truepour l'une de ses entrées possibles, et Falsepour toutes les autres. Le travail de l'algorithme est de trouver celui qui revient True.

Pour ce faire, nous exprimons les entrées sous forme de chaînes de bits et les codons à l'aide de la |0 et |1 états d'une chaîne de qubits. Ainsi, la chaîne de bits 0011serait codée dans l'état à quatre qubits |0011 , par exemple.

Nous devons également être en mesure d'implémenter la fonction en utilisant des portes quantiques. Plus précisément, nous devons trouver une séquence de portes qui implémentera un U unitaire tel que

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

aTruebFalse

12nnU12n

D

bj

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

μ=jαjμ+δμδ

12n

12n

Bien sûr, tout cela montre que tout le travail est effectué par l'opérateur de diffusion. La recherche n'est qu'une application à laquelle nous pouvons nous connecter.

Voir les réponses à d'autres questions pour plus de détails sur la façon dont les fonctions et l' opérateur de diffusion sont implémentés.

James Wootton
la source
4

Je trouve une approche graphique assez bonne pour donner un aperçu sans être trop technique. Nous avons besoin de quelques entrées:

  • |ψ|xx|ψ0
  • U1=(I2|ψψ|)
  • U2=I2|xx|

|ψ|x{|x,|ψ}{|x,|ψ}{|x,|ψ}, et ils renvoient un état dans l'intervalle. De plus, les deux sont unitaires, la longueur du vecteur d'entrée est donc préservée.

|ψ|xentrez la description de l'image ici

|ψ|x|ψ|ψ|ψ|ψθentrez la description de l'image ici

U1|ψU2|ψentrez la description de l'image ici

U2U12θ|xentrez la description de l'image ici

|ψθ|xx

|x|ψp1O(1/p)p=sinθθθrsin((2r+1)θ)1rπ2θπ2p

DaftWullie
la source
3

1/NN1

pyramides
la source