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

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(\sqrt{n})$

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

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\rangle$ et $|1\rangle$ états d'une chaîne de qubits. Ainsi, la chaîne de bits 0011serait codée dans l'état à quatre qubits $|0011\rangle$ , 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 \rangle = - | a \rangle, \,\,\,\,\,\,\,\,\,\,\,\,\, U | b \rangle = | b \rangle$

$a$True$b$False

$\frac{1}{\sqrt{2^n}}$$n$$U$$-\frac{1}{\sqrt{2^n}}$

$D$

$b_j$

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

$\mu = \sum_j \alpha_j$$\mu + \delta$$\mu - \delta$

$-\frac{1}{\sqrt{2^n}}$

$\frac{1}{\sqrt{2^n}}$

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.

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

• $|\psi\rangle$$|x\rangle$$\langle x|\psi\rangle\neq 0$
• $U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$
• $U_2=\mathbb{I}-2|x\rangle\langle x|$

$|\psi^\perp\rangle$$|x\rangle$$\{|x\rangle,|\psi^\perp\rangle\}$$\{|x\rangle,|\psi\rangle\}$$\{|x\rangle,|\psi^\perp\rangle\}$, 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.

$|\psi^\perp\rangle$$|x\rangle$

$|\psi\rangle$$|x\rangle$$|\psi^\perp\rangle$$|\psi\rangle$$|\psi\rangle$$|\psi^\perp\rangle$$\theta$

$U_1$$|\psi\rangle$$U_2$$|\psi^\perp\rangle$

$U_2$$U_1$$2\theta$$|x\rangle$

$|\psi\rangle$$\theta$$|x\rangle$$x$

$|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}}$

$1/\sqrt{N}$$\sqrt{N}$$1$