Resource-Efficient Digitized Adiabatic Quantum Factorization

Résumé Technique : Factorisation Quantique Adiabatique à l'Économie de Ressources Numérisée

Énoncé du Problème
L'article traite du défi de la mise en œuvre d'une factorisation quantique adiabatique efficace sur des ordinateurs quantiques numérisés (à base de portes). Les approches standard, telles que la méthode proposée par Peng et al. [1], formulent la factorisation d'entiers comme une recherche de l'état fondamental d'un Hamiltonien de problème dérivé d'une fonction d'Optimisation Binaire Non Contrainte Polynomiale (PUBO). Cette formulation aboutit à un Hamiltonien contenant des termes d'interaction non locaux à trois et quatre qubits ($Z^3$ et $Z^4$). Sur les dispositifs numérisés, ces interactions d'ordre élevé nécessitent la décomposition en de multiples portes à deux qubits natives (par exemple, des CNOT), ce qui conduit à des circuits profonds avec un nombre élevé de portes. Cette complexité limite sévèrement la fidélité et la scalabilité de l'algorithme, les probabilités de succès chutant drastiquement pour des nombres supérieurs à 91, même en employant des techniques d'apprentissage automatique.

Méthodologie
Les auteurs proposent un nouvel algorithme adiabatique numérisé qui reformule le problème de factorisation en utilisant un cadre d'Optimisation Binaire Quadratique Non Contrainte (QUBO). Le changement méthodologique central implique deux changements clés :

1. Encodage par Sous-espace de Noyau (Kernel Subspace Encoding) : Au lieu d'encoder la solution comme l'état fondamental (minimum d'énergie zéro) d'une fonction au carré $F^2$, les auteurs définissent l'Hamiltonien du problème $\hat{H}_{LP}$ comme étant la fonction linéaire $F(N, \hat{p}', \hat{q}')$ elle-même. Dans cette formulation, la solution correspond à l'état propre d'énergie nulle (le sous-espace noyau) de l'Hamiltonien, ce qui est un état excité par rapport au spectre global, plutôt qu'un état fondamental.
2. Formulation QUBO : En utilisant la fonction linéaire, l'Hamiltonien résultant ne contient que des interactions à deux corps, classant ainsi le problème comme un problème QUBO. Cela élimine le besoin de réductions polynomiales NP-difficiles et de variables auxiliaires typiquement requises pour mapper des problèmes PUBO vers des QUBO.

L'algorithme est implémenté à l'aide d'un Algorithme Quantique Variationnel (spécifiquement le QAOA). Le protocole initialise le système dans un état de superposition uniforme (spécifiquement $|+\rangle|-\rangle\dots$ pour s'aligner sur le sous-espace nul de $\hat{H}_{LP}$) et l'évolue en utilisant des unitaires alternés dérivés de l'Hamiltonien de coût ($\hat{H}_{LP}$) et d'un Hamiltonien de mélange ($\hat{H}_M$). La fonction de coût minimisée par les optimiseurs classiques est définie comme l'espérance de la valeur absolue de l'Hamiltonien, $C_{LP} = \langle |\hat{H}_{LP}| \rangle$, afin d'assurer la convergence vers la solution d'énergie nulle.

Contributions Clés

• Simplification de Circuit : L'approche QUBO proposée réduit l'Hamiltonien du problème à des interactions à deux corps. Cela élimine la nécessité de décomposer des portes multi-qubits complexes, réduisant ainsi considérablement la profondeur du circuit.
• Nouvelle Stratégie d'Encodage : L'article démontre que la factorisation adiabatique peut être réalisée avec succès en ciblant le sous-espace de noyau (l'état excité d'énergie nulle) plutôt que l'état fondamental, contournant ainsi les limitations des formulations PUBO.
• Analyse de Robustesse : Les auteurs analysent la densité spectrale des Hamiltoniens, montrant que la formulation QUBO offre une densité d'états plus éparse autour du sous-espace de la solution par rapport à la formulation PUBO, ce qui aide à éviter les minima locaux et les plateaux stériles (barren plateaus) lors de l'optimisation.

Résultats
Les auteurs ont comparé leur algorithme basé sur QUBO à l'approche PUBO standard pour la factorisation d'entiers allant jusqu'à 8 bits (spécifiquement $N=25, 119, 143$).

• Complexité de Portes : Pour une couche unique du circuit QAOA, l'approche QUBO nécessite nettement moins de portes CNOT. Par exemple, la factorisation de $N=25$ nécessite 8 CNOT par couche pour la méthode QUBO, contre 34 CNOT pour la méthode PUBO (après décomposition des portes à 3 et 4 qubits).
• Fidélité et Confiance : L'algorithme QUBO démontre une fidélité nettement plus élevée pour identifier les facteurs corrects. Pour des nombres plus grands comme $N=119$ et $N=143$, l'approche PUBO échoue à concentrer l'amplitude de probabilité sur la solution correcte, entraînant des scores de confiance faibles et une entropie de Shannon élevée. En revanche, l'approche QUBO parvient à peupler les états de solution corrects.
• Convergence de la Fonction de Coût : L'algorithme QUBO atteint une réduction plus profonde de la fonction de coût (jusqu'à 3 ordres de grandeur pour $N=143$) par rapport à l'approche PUBO (jusqu'à 2 ordres de grandeur), indiquant une optimisation plus efficace.
• Analyse Spectrale : L'analyse des spectres d'énergie révèle que l'Hamiltonien PUBO possède une haute densité d'états près de la solution, créant un paysage "plat" qui entrave les optimiseurs classiques. L'Hamiltonien QUBO présente un spectre plus largement dispersé avec des écarts d'énergie plus importants près du sous-espace de noyau, facilitant la préparation de l'état.

Signification et Revendications
L'article affirme que ce travail fournit une voie économiquement efficiente en ressources pour la factorisation quantique adiabatique numérisée. La signification principale réside dans la réduction substantielle de la complexité du circuit et l'augmentation correspondante de la fidélité algorithmique, rendant la factorisation d'entiers plus grands réalisable sur des dispositifs de génération actuelle (near-term).

Les auteurs soulignent que, bien que cibler un état excité (le noyau) soit difficile pour les recuits quantiques (quantum annealers) en raison de l'absence de protection par décohérence de l'état fondamental, cela est avantageux pour les recuits quantiques numérisés. Dans les systèmes à base de portes, où la décohérence est souvent régie par la décroissance locale d'un qubit unique, le nombre réduit de portes de l'approche QUBO minimise le temps d'exécution total et l'exposition aux erreurs. Les résultats suggèrent que les formulations basées sur QUBO peuvent surpasser celles basées sur PUBO dans l'optimisation par QAOA, remettant en question la littérature antérieure qui supposait que le PUBO était nécessaire ou supérieur pour certaines structures de problèmes. Ce travail motive l'exploration plus approfondie des protocoles adiabatiques numérisés pour des problèmes de théorie des nombres plus larges et des Hamiltoniens complexes.