Quantum Search without Global Diffusion

1. Problématique

L'algorithme de recherche de Grover et l'amplification d'amplitude quantique reposent fondamentalement sur deux opérations globales :

1. L'oracle ($S_x$) : Marque l'état cible en appliquant un déphasage de $-1$.
2. L'opérateur de diffusion ($S_\psi$) : Réfléchit l'état par rapport à l'état initial $|\psi\rangle$.

Bien que l'oracle soit spécifique au problème, l'opérateur de diffusion est une opération globale agissant sur l'ensemble des $n$ qubits du registre de recherche. Cette opération globale est coûteuse à implémenter sur le matériel quantique actuel (NISQ), nécessitant des portes contrôlées multi-qubits complexes et augmentant la profondeur du circuit, ce qui accroît la sensibilité au bruit et aux erreurs de décohérence.

Les travaux antérieurs sur la « diffusion partielle » ont tenté de réduire cette charge en agissant sur des sous-ensembles de qubits, mais ils ont souvent brisé la géométrie rotationnelle bidimensionnelle simple de l'amplification d'amplitude standard, rendant l'analyse dynamique extrêmement complexe (nécessitant l'évaluation de puissances de matrices unitaires de grande dimension).

Le défi central : Peut-on supprimer entièrement l'opérateur de diffusion global tout en préservant l'accélération quadratique ($O(\sqrt{N})$) et en obtenant une solution analytique exacte pour la dynamique de l'algorithme ?

2. Méthodologie

Les auteurs proposent une construction récursive qui remplace l'opérateur de diffusion global par une série d'opérateurs de réflexion locaux, agissant uniquement sur des partitions non chevauchantes du registre de recherche.

Hypothèses de base

L'algorithme suppose que l'état initial $|\psi\rangle$ (préparé par l'algorithme $A$) et l'état cible $|x\rangle$ se décomposent tous deux en produits tensoriels sur une partition du registre en $m$ sous-espaces (registres) :
$$A = \bigotimes_{i=1}^m A_i, \quad |x\rangle = \bigotimes_{i=1}^m |x_i\rangle$$
où $A_i$ agit sur le registre $i$ et $|x_i\rangle$ est l'état cible local.

Construction Récursive

L'algorithme procède par étapes itératives :

1. Définition des opérateurs : Pour chaque registre $i$, un opérateur de diffusion partiel $S_{\psi_i}$ est défini comme une réflexion locale autour de $|\psi_i\rangle$.
2. Opérateur récursif $W_i$ : L'itérateur global est construit récursivement. À l'étape $i$, l'opérateur $W_i$ est défini comme :
   $$W_i = (S_{\psi_i} W_{i-1})^{t_i} S_{\psi_i} (W_{i-1} S_{\psi_i})^{t_i}$$
   avec $W_0 = S_x$ (l'oracle global).
3. Processus séquentiel :
   • On amplifie d'abord la probabilité de trouver la cible dans le dernier registre $m$ en appliquant l'itérateur $(S_{\psi_m} W_{m-1})$ un nombre optimal de fois $t_m$.
   • Les registres $1$à$m-1$ sont mesurés et réinitialisés à leur état initial $|\psi\rangle$.
   • Le processus est répété sur le registre $m-1$, puis $m-2$, etc., jusqu'à ce que tous les registres soient traités.

Analyse Mathématique Clé

La contribution théorique majeure réside dans l'analyse des angles principaux entre les sous-espaces réfléchis. Bien que les sous-espaces impliqués croissent exponentiellement en dimension ($2^{i-1}$), les auteurs démontrent une dégénérescence remarquable :

• Les angles principaux entre les opérateurs de réflexion successifs ne prennent que deux valeurs distinctes : $\gamma_i$ et $\pi/2 - \gamma_i$.
• Ces angles sont gouvernés par une seule relation récursive :
  $$\sin(2\gamma_i) = \sin(2\theta_i) \sin(2t_{i-1}\gamma_{i-1})$$
  où $\theta_i$ est l'angle de recouvrement local entre $|\psi_i\rangle$ et $|x_i\rangle$.
• Cette dégénérescence permet de réduire le problème dynamique complexe à un problème scalaire $2 \times 2$, permettant une solution en forme close exacte pour la probabilité de succès.

3. Contributions Clés

1. Suppression de la diffusion globale : Preuve qu'un opérateur de diffusion global n'est pas nécessaire pour obtenir l'accélération quadratique, à condition que l'oracle reste l'unique opérateur global.
2. Solution analytique exacte : Fourniture d'une expression fermée pour la dynamique de l'algorithme, contournant la complexité exponentielle habituelle des algorithmes de recherche partielle.
3. Analyse de la complexité :
   • Complexité en requêtes (Oracle) : L'algorithme conserve une complexité de $O(\sqrt{N})$ lorsque la taille de chaque partition $s$ satisfait $s \ge \log_2(\log_2 N)$. Le surcoût en appels à l'oracle est borné par un facteur $O(1/\prod \cos(\theta_i))$, qui tend vers 1 pour de grandes tailles de partition.
   • Profondeur du circuit : Réduction drastique de la profondeur des circuits non-oracles en remplaçant des réflexions globales $n$-qubits par des réflexions locales $s$-qubits.

4. Résultats Expérimentaux et Simulations

Les auteurs ont évalué leur approche sur un problème de recherche non structurée à 18 qubits ($N=2^{18}$) et extrapolé les résultats jusqu'à 50 qubits.

• Réduction de la profondeur de circuit :
  • Pour une configuration à 2 étages (9 qubits par étage), la profondeur du circuit de diffusion est réduite de 51 % à 96 % par rapport à l'algorithme de Grover standard, selon la décomposition des portes (avec ou sans qubits auxiliaires).
  • Pour une configuration à 3 étages (6 qubits par étage), la réduction atteint jusqu'à 97 % (sans qubits auxiliaires).
  • Ces gains sont obtenus avec un surcoût modeste en appels à l'oracle (jusqu'à 9 % pour 2 étages, 30 % pour 3 étages sur 18 qubits).
• Évolutivité :
  • Pour des problèmes plus grands ($n=50$), le surcoût en oracle et le taux d'échec diminuent rapidement.
  • Même lorsque l'oracle est significativement plus profond que l'opérateur de diffusion (par exemple, 10 fois plus profond, comme dans le cas de la cryptanalyse AES-128), l'approche récursive offre toujours une réduction nette de la profondeur totale du circuit (environ 5 % à 35 % selon les configurations).
• Robustesse : Les simulations montrent que la probabilité de succès reste élevée (>96 %) et que la structure séquentielle permet d'obtenir des résultats partiels (préfixes de la cible) avec une probabilité encore plus élevée.

5. Signification et Implications

• Pratique (Matériel NISQ) : La réduction de la profondeur du circuit est cruciale pour les dispositifs quantiques actuels, car elle diminue l'accumulation d'erreurs de portes et la sensibilité au bruit. La capacité à exécuter des opérations non-oracles localement est particulièrement avantageuse pour les architectures distribuées où la connectivité entre nœuds est limitée.
• Théorique :
  • Rôle de l'intrication : Ce travail remet en question la nécessité de l'intrication globale à chaque étape de l'amplification d'amplitude. Il démontre que la structure non-locale nécessaire à l'accélération quantique réside entièrement dans l'oracle, tandis que les opérations de diffusion peuvent être purement locales.
  • Nouvelles perspectives : La dégénérescence des angles principaux découverte ici ouvre de nouvelles voies pour la conception d'algorithmes quantiques, suggérant que d'autres algorithmes pourraient bénéficier de réductions similaires de complexité analytique en exploitant des structures de produits tensoriels.

En conclusion, cette recherche établit que l'amplification d'amplitude peut être réalisée sans opérateur de diffusion global, offrant un compromis pratique entre la complexité des portes et le nombre d'appels à l'oracle, tout en maintenant l'avantage quantique fondamental.