Physique de pointe

Algorithmes quantiques (Shor, Grover)

Les algorithmes quantiques exploitent l’interférence et l’intrication pour accélérer certains problèmes, pas tous les calculs.

Un algorithme quantique enchaîne portes unitaires, mesures et traitement classique. Il vise une distribution de sorties utile avec moins de ressources que la meilleure approche classique connue dans un modèle de complexité donné.

T_{\mathrm{Grover}}=O(\sqrt{N}),\qquad T_{\mathrm{classique}}=O(N);\quad T_{\mathrm{Shor}}=\operatorname{poly}(n)\ (\text{portes quantiques})

Définition: Accélération quantique

Amélioration des ressources par rapport à un modèle classique précisé. Une revendication d’accélération doit compter l’accès aux données, l’échantillonnage, les erreurs et le pré/post-traitement classique.

Le vecteur d’état tourne dans un plan bidimensionnel ; illustration idéale de Grover, sans matériel bruité.

Grover et Shor

Grover amplifie l’amplitude d’un état marqué en alternant oracle et inversion autour de la moyenne ; la recherche non structurée requiert environ $\sqrt N$ requêtes. Shor utilise la transformée de Fourier quantique et la recherche de période pour factoriser en temps polynomial en nombre de bits, dans un modèle à portes avec correction d’erreurs.

Exemple: Nombre de requêtes de Grover

Pour $N=10^4$ éléments, estimez les requêtes classiques à l’oracle et l’ordre de grandeur des requêtes de Grover.

Solution

La recherche classique demande de l’ordre de $N=10^4$ requêtes, Grover de $\sqrt N=10^2$ . Les constantes dépendent de la probabilité de succès et de la convention de comptage.

Les algorithmes quantiques ne rendent pas toutes les réponses accessibles à la lecture : la mesure ne fournit qu’un échantillon, il faut donc amplifier l’amplitude voulue par interférence. Dans Grover, un oracle marque la cible et l’amplification fait tourner l’état d’environ $\pi/4$ par itération vers celle-ci, pour un nombre de requêtes de l’ordre de $\sqrt N$ . Shor exploite la périodicité de la multiplication modulaire pour factoriser en temps polynomial quantique, mais l’avantage pratique dépend de la correction d’erreurs et du matériel.

La complexité en requêtes n’est pas le temps total : les coûts de préparation d’état, de correction d’erreurs et de lecture comptent aussi. Une analyse doit préciser le modèle d’oracle et la distribution d’entrée ; un avantage asymptotique peut disparaître sur de petits jeux de données ou si le prétraitement est coûteux. Une question centrale est de savoir quelles classes de problèmes conservent un avantage sur des machines tolérantes aux fautes.

Quelle est la complexité en requêtes de Grover pour N éléments non structurés ?

Quelle affirmation décrit le mieux l’avantage de l’algorithme de Shor ?

Références

Michael A. Nielsen, Isaac L. Chuang (2010). Quantum Computation and Quantum Information