Sujet de recherche

Modèles énergétiques du calcul quantique

Le calcul fondé sur l’énergie demande si une solution peut être représentée par le minimum d’un paysage énergétique.

Dans le modèle d’Ising classique, les spins si ∈ {−1, +1} minimisent

E(s) = ∑ij Jijsisj + ∑i hisi.

Les couplages Jij codent la compatibilité ou la frustration, tandis que les champs hi biaisent les spins individuels. Une configuration de spins de basse énergie peut donc représenter une bonne solution à un problème combinatoire.

Des verres de spin à l’optimisation

Barahona a précisé ce lien : trouver un état fondamental d’un verre de spin d’Ising est NP-difficile en deux dimensions lorsque des champs magnétiques sont permis [1]. Sans champs, le problème planaire se résout en temps polynomial ; l’ajout de champs change la classe de complexité.

Le modèle de Sherrington–Kirkpatrick apporte une image physique complémentaire : un verre de spin d’Ising en champ moyen, doté de couplages aléatoires et concurrents et d’une transition thermodynamique vers une phase de verre de spin [2]. Il ne s’agissait pas d’une transition de complexité algorithmique ; le recuit simulé a ensuite fourni le lien algorithmique [3].

La logique de spins à l’état fondamental a ensuite montré que des fonctions booléennes—et donc des circuits de commutation—peuvent être incorporées dans les espaces fondamentaux d’Ising [12]. Les minima d’énergie peuvent ainsi représenter des problèmes d’optimisation et des calculs, et non seulement des configurations physiques.

Le problème de l’hamiltonien local quantique

Pour un système quantique, la fonction d’énergie est remplacée par un hamiltonien H. Le problème de l’hamiltonien local demande, étant donnés des seuils a < b séparés par au moins l’inverse d’un polynôme, si l’énergie de son état fondamental vérifie

λmin(H) ≤ a    ou    λmin(H) ≥ b.

Il s’agit d’un problème avec promesse : les entrées situées entre a et b sont exclues. La construction d’état-histoire de Kitaev encode l’évolution acceptante d’un circuit quantique de vérification dans le secteur de basse énergie d’un hamiltonien local. L’acceptation du circuit peut ainsi être reformulée comme un problème de décision sur l’énergie fondamentale. Le problème de l’hamiltonien local qui en résulte est QMA-complet, où QMA est l’analogue quantique de NP [4][5].

Cette affirmation doit être distinguée de l’idée selon laquelle chaque bit de sortie serait littéralement une valeur propre d’énergie. Il s’agit plutôt de réduire un problème de vérification quantique spécifié efficacement à la question de savoir si un hamiltonien possède une énergie fondamentale suffisamment basse. La QMA-complétude subsiste pour des interactions 2-locales et même avec une restriction à un réseau carré bidimensionnel [5][6].

Calcul adiabatique

Farhi, Goldstone, Gutmann et Sipser ont donné à l’image de l’optimisation sa forme dynamique quantique. On part de l’état fondamental facile à préparer de Hinit, puis on évolue lentement vers Hfinal, dont l’état fondamental encode la réponse [7]. Le théorème adiabatique motive cette procédure : si le chemin est parcouru lentement par rapport à l’écart spectral pertinent, l’état reste proche de l’état fondamental instantané. Cet écart est essentiel—un écart minimal exponentiellement petit peut exiger un temps d’exécution exponentiellement long.

Aharonov et ses collaborateurs ont démontré que le calcul quantique adiabatique est polynomialement équivalent au modèle standard de circuits [8]. Leur résultat établit l’universalité du modèle de calcul ; il ne prouve pas qu’une instance arbitraire d’optimisation puisse être résolue efficacement.

Hamiltoniens universels réalisables

Biamonte et Love ont identifié des ensembles restreints d’interactions à deux corps qui demeurent universels : des champs locaux X et Z avec des couplages ZZ et XX, ou de type ZX. Ces modèles sont QMA-complets ; un terme XX réglable transforme le modèle d’Ising à champ transverse en un modèle universel [9].

Le modèle d’Ising à champ transverse est stoquastique : ses éléments non diagonaux sont non positifs dans une base appropriée. Bravyi et Hastings ont montré que son problème d’énergie fondamentale sur des graphes de degré trois est StoqMA-complet, plutôt que connu comme QMA-complet [10]. Les coupleurs de Biamonte–Love franchissent donc une frontière significative.

Modèles énergétiques en apprentissage automatique

L’apprentissage automatique fondé sur l’énergie emploie le même langage dans un autre but. Une machine de Boltzmann attribue une loi de probabilité

pθ(x) = e−Eθ(x)Zθ,

et l’apprentissage modifie les paramètres θ afin que les données observées occupent des régions de basse énergie et de forte probabilité. L’apprentissage automatique quantique utilise de même des modèles de type Ising et Boltzmann comme paysages de probabilité entraînables, plutôt que comme problèmes de décision QMA [11].

Calcul variationnel : une boucle de rétroaction quantique–classique

Le calcul variationnel partage cette architecture de rétroaction : une procédure classique modifie des paramètres en réponse à l’information fournie par un système quantique. Pour un observable écrit H = ∑α hαPα, une procédure variationnelle prépare |ψ(θ)⟩ et estime

E(θ) = ⟨ψ(θ)|H|ψ(θ)⟩ = ∑α hα⟨Pα⟩θ.

Le dispositif quantique estime les termes individuels Pα ; une boucle externe classique agrège ces estimations et met à jour θ. Cette architecture quantique–classique entraînable rend le calcul variationnel pertinent pour l’apprentissage automatique, sans faire de tout algorithme variationnel un algorithme d’apprentissage automatique [13].

Le QAOA est un ansatz variationnel particulier : il alterne un hamiltonien de coût et un hamiltonien de mélange non commutant, initialement afin de rechercher des solutions de faible coût [15]. Le calcul quantique variationnel universel construit des fonctions objectif dont les minima préparent les sorties de circuits quantiques arbitraires, établissant ainsi un modèle universel de calcul [14]. Séparément, certaines séquences QAOA ont été démontrées universelles au sens d’un ensemble de portes, sous des conditions explicites portant sur leurs interactions et leurs symétries [16].

La séparation possible avec les modèles énergétiques classiques se situe ici. Étant donnée une configuration classique de spins, son énergie s’évalue directement en sommant les termes affichés. Pour un hamiltonien quantique suffisamment général et un état de circuit fortement intriqué, aucune méthode classique efficace n’est connue pour évaluer fidèlement à grande échelle le paysage correspondant de valeurs d’espérance. L’hypothèse de travail—et non un théorème général—est que cette tâche exigera des ressources classiques exponentielles dans le cas général. La simulation brutale par vecteur d’état utilise 2n amplitudes, mais ce fait n’est pas une borne inférieure inconditionnelle : de nombreux hamiltoniens, états et circuits peu profonds structurés demeurent classiquement traitables. La QMA-complétude du problème de l’hamiltonien local fournit un solide indice d’une barrière de complexité [4][5] ; elle ne prouve pas que tout calcul quantique de valeur d’espérance soit exponentiellement difficile.

Références

  1. F. Barahona, On the Computational Complexity of Ising Spin Glass Models, Journal of Physics A 15, 3241–3253 (1982).
  2. D. Sherrington et S. Kirkpatrick, Solvable Model of a Spin-Glass, Physical Review Letters 35, 1792–1796 (1975).
  3. S. Kirkpatrick, C. D. Gelatt, Jr. et M. P. Vecchi, Optimization by Simulated Annealing, Science 220, 671–680 (1983).
  4. A. Yu. Kitaev, A. H. Shen et M. N. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics 47 (American Mathematical Society, 2002).
  5. J. Kempe, A. Kitaev et O. Regev, The Complexity of the Local Hamiltonian Problem, SIAM Journal on Computing 35, 1070–1097 (2006).
  6. R. Oliveira et B. M. Terhal, The Complexity of Quantum Spin Systems on a Two-Dimensional Square Lattice, Quantum Information & Computation 8, 900–924 (2008).
  7. E. Farhi, J. Goldstone, S. Gutmann et M. Sipser, Quantum Computation by Adiabatic Evolution, arXiv:quant-ph/0001106 (2000).
  8. D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd et O. Regev, Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation, SIAM Journal on Computing 37, 166–194 (2007).
  9. J. D. Biamonte et P. J. Love, Realizable Hamiltonians for Universal Adiabatic Quantum Computers, Physical Review A 78, 012352 (2008).
  10. S. Bravyi et M. B. Hastings, On Complexity of the Quantum Ising Model, Communications in Mathematical Physics 349, 1–45 (2017).
  11. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe et S. Lloyd, Quantum Machine Learning, Nature 549, 195–202 (2017).
  12. J. D. Biamonte, Non-Perturbative k-Body to Two-Body Commuting Conversion Hamiltonians and Embedding Problem Instances into Ising Spins, Physical Review A 77, 052331 (2008).
  13. A. Peruzzo et al., A Variational Eigenvalue Solver on a Photonic Quantum Processor, Nature Communications 5, 4213 (2014).
  14. J. Biamonte, Universal Variational Quantum Computation, Physical Review A 103, L030401 (2021).
  15. E. Farhi, J. Goldstone et S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014).
  16. M. E. S. Morales, J. D. Biamonte et Z. Zimborás, On the Universality of the Quantum Approximate Optimization Algorithm, Quantum Information Processing 19, 291 (2020).