The Complexity of Stoquastic Sparse Hamiltonians

Cet article établit que le problème des Hamiltoniens clairsemés stoquastiques est $\mathsf{StoqMA}$-complet et que sa version séparable est $\mathsf{StoqMA}(2)$-complet, approfondissant ainsi la compréhension de la puissance de la classe de complexité $\mathsf{StoqMA}$.

L'essentiel

La Grande Image : L'Énigme de l'« Énergie »

Imaginez que vous possédez une machine géante et complexe constituée de milliers de petits interrupteurs (des bits quantiques, ou qubits). Cette machine possède un « état fondamental » spécifique, qui correspond à sa position de repos ou à son réglage d'énergie le plus bas.

Dans le monde de la physique quantique, déterminer exactement quel est ce réglage d'énergie le plus bas pour une machine complexe est incroyablement difficile. C'est comme essayer de trouver le point absolument le plus bas d'une vaste chaîne de montagnes enveloppée de brouillard, sans carte. Les informaticiens appellent cela le Problème de Hamiltonien Local.

Habituellement, ce problème est si difficile qu'il appartient à une classe de problèmes appelée QMA (Merlin-Arthur Quantique). Imaginez QMA comme un jeu où un magicien puissant (Merlin) tente de convaincre un juge sceptique (Arthur) qu'il a trouvé le point le plus bas. Le juge peut vérifier la réponse du magicien en utilisant un ordinateur quantique.

Le Cas Spécial : Les Machines « Stoquastiques »

Le document se concentre sur un type spécial de machine appelé Hamiltonien Stoquastique.

• L'Analogie : Imaginez une machine normale où les interrupteurs peuvent pousser ou tirer de manière confuse et négative (comme une partie de tir à la corde où la corde traverse un mur). Cela crée un « problème de signe » qui empêche les ordinateurs classiques (comme votre ordinateur portable) de les simuler.
• La Différence Stoquastique : Une machine stoquastique est « gentille ». Tous ses interrupteurs ne poussent ou ne tirent que d'une manière qui maintient les choses positives. Il n'y a pas de signes négatifs confus. Grâce à cela, les ordinateurs classiques peuvent les simuler beaucoup mieux en utilisant des méthodes comme les simulations de Monte Carlo (des devinettes aléatoires qui deviennent plus intelligentes avec le temps).

Même si ces machines sont « plus gentilles », déterminer leur énergie la plus basse reste difficile. Il s'avère que ce problème spécifique appartient à une classe appelée StoqMA. C'est une classe intermédiaire entre les devinettes classiques standard (MA) et les devinettes classiques plus avancées (AM).

La Découverte Principale : Sparsité vs Localité

Les auteurs voulaient mieux comprendre StoqMA. Pour ce faire, ils ont examiné un type spécifique de machine : les Hamiltoniens Creux (Sparse).

• Hamiltoniens Locaux : Imaginez une machine où chaque interrupteur ne parle qu'à ses voisins immédiats (comme des gens dans une file qui ne parlent qu'à la personne à côté d'eux).
• Hamiltoniens Creux : Imaginez une machine où un interrupteur peut parler à n'importe qui dans la pièce, mais chaque interrupteur ne parle qu'à un très petit nombre fixe de personnes (disons 10 personnes sur un million). C'est « creux » car la plupart des connexions sont vides.

L'Affirmation du Document :
Les auteurs ont prouvé que déterminer l'énergie la plus basse de ces machines « creuses » est exactement aussi difficile que celle des machines « locales ».

• Le Résultat : Le problème de l'« Hamiltonien Stoquastique Creux » est StoqMA-complet.
• Ce que cela signifie : Si vous pouvez résoudre la version creuse efficacement, vous pouvez résoudre la version locale, et vice versa. Elles sont également difficiles. C'est surprenant car les machines creuses sont beaucoup plus générales et flexibles que les locales, pourtant elles ne deviennent pas « plus faciles » à résoudre dans ce contexte quantique spécifique.

Comment Ils Ont Fait : Le Test « Hadamard »

Pour prouver cela, les auteurs ont dû inventer une nouvelle méthode permettant au juge (Arthur) de vérifier la réponse du magicien (Merlin).

• Le Problème : La manière habituelle de vérifier l'énergie implique des mathématiques quantiques complexes (Estimation de Phase) que le juge « stoquastique » n'est pas autorisé à effectuer car ses outils sont trop simples (ils ne peuvent pas gérer les mathématiques « négatives »).
• La Solution : Les auteurs ont inventé un tour de passe-passe ingénieux. Ils ont décomposé la grande machine en pièces minuscules à connexion unique (termes 1-creux). Ensuite, ils ont créé un test « de type Hadamard ».
  • La Métaphore : Imaginez que le juge demande au magicien de tenir une pièce de monnaie. Le juge actionne un interrupteur qui connecte aléatoirement la pièce à un voisin spécifique. Le juge vérifie ensuite si la pièce est tombée d'une manière particulière. En répétant cela de nombreuses fois avec différentes connexions aléatoires, le juge peut calculer l'énergie totale de la machine sans avoir besoin d'un superordinateur quantique complet.

La Touche « Séparable » : Deux Magiciens, Pas de Télépathie

Le document a également examiné une variation appelée Hamiltonien Stoquastique Creux Séparable.

• Le Scénario : Imaginez que la machine est divisée en deux moitiés (Gauche et Droite). Le juge veut connaître l'énergie la plus basse, mais avec une règle : le magicien doit fournir deux réponses séparées et non intriquées (une pour la moitié Gauche, une pour la moitié Droite). Ils ne peuvent pas partager un lien de « télépathie quantique » (intrication) entre eux.
• Le Résultat : Les auteurs ont montré que ce problème spécifique est StoqMA(2)-complet.
  • StoqMA(2) est une classe où le juge dispose de deux magiciens non intriqués.
  • C'est une chose importante car cela montre que même si vous forcez les magiciens à travailler séparément (pas d'équipe quantique), le problème reste aussi difficile que le cas général.

La Règle « Deux Magiciens Suffisent »

Enfin, les auteurs se sont demandé : « Et si nous avions trois magiciens, ou dix magiciens ? Est-ce que cela rendrait le travail du juge plus facile ou plus difficile ? »

• La Découverte : Ils ont prouvé que pour ce type spécifique de jeu quantique, deux magiciens suffisent.
• L'Analogie : Même si vous avez une équipe de 100 magiciens tentant de convaincre le juge, ce dernier peut simuler toute l'équipe en demandant simplement à deux d'entre eux d'envoyer exactement le même message et en vérifiant s'ils disent la vérité. Vous n'avez pas besoin de plus de deux pour capturer toute la puissance du système.

Résumé

1. Les machines stoquastiques sont un type spécial et « plus gentil » de machine quantique qui évite le « problème de signe ».
2. Les auteurs ont prouvé que trouver l'énergie la plus basse des machines stoquastiques creuses est tout aussi difficile que de la trouver pour les machines locales. Les deux sont StoqMA-complètes.
3. Ils ont développé une nouvelle méthode de test qui permet à un juge restreint de vérifier ces énergies sans avoir besoin d'une puissance quantique totale.
4. Ils ont montré que même si vous divisez la machine en deux et forcez les magiciens à travailler séparément, le problème reste difficile (StoqMA(2)-complet).
5. Ils ont prouvé que posséder plus de deux magiciens non intriqués ne vous donne aucun pouvoir supplémentaire ; deux suffisent pour simuler n'importe quel nombre d'entre eux.

Ce travail aide à cartographier le paysage de la complexité quantique, montrant exactement où résident les problèmes « difficiles » et comment différents types de machines quantiques sont liés les uns aux autres.

Résumé technique

Énoncé du problème

Le papier aborde la complexité computationnelle du problème de l'Hamiltonien creux stoquastique (StoqSH). Alors que la complexité des Hamiltoniens stoquastiques locaux est bien comprise (connue pour être StoqMA-complète), celle des Hamiltoniens stoquastiques creux n'avait pas été directement établie.

Les Hamiltoniens creux constituent une classe plus large que les Hamiltoniens locaux ; un Hamiltonien $k$-local avec $m$ termes est $2^{km}$-creux. Le problème StoqSH demande, étant donné un Hamiltonien stoquastique $d$-creux $H$ (où les éléments hors diagonale sont non positifs) et des paramètres $\alpha, \beta$, si l'énergie de l'état fondamental $\lambda_{\min}(H) \le \alpha$ ou $\lambda_{\min}(H) \ge \beta$, avec la promesse qu'un seul de ces cas est vrai.

Le défi central réside dans le fait que les techniques standard pour prouver l'appartenance à StoqMA pour les Hamiltoniens locaux (qui reposent sur la conversion des termes locaux en projections spécifiques) ne s'étendent pas au contexte creux. De plus, les méthodes de vérification quantique standard comme l'estimation de phase (utilisée pour les Hamiltoniens creux généraux dans QMA) sont intrinsèquement quantiques et ne peuvent pas être simulées par les vérificateurs stoquastiques restreints, qui sont limités aux circuits réversibles classiques et aux mesures dans la base de Hadamard.

Méthodologie

Les auteurs emploient une procédure de vérification qui comble le fossé entre la structure des Hamiltoniens creux et les limitations des vérificateurs stoquastiques. La méthodologie se compose de trois composants principaux :

1. Décomposition creuse :
   Les auteurs utilisent une décomposition connue (de [BCC+14]) où tout Hamiltonien $d$-creux $H$ peut s'écrire comme une somme de $d^2$ termes 1-creux ($H = \sum H_j$). De manière cruciale, si $H$ est stoquastique, chaque terme $H_j$ de cette décomposition est également stoquastique, et les éléments de matrice non nuls sont attribués de manière unique à des termes spécifiques.

2. Vérificateurs StoqMA généralisés (gStoqMA) :
   Pour gérer la vérification, les auteurs introduisent une généralisation du vérificateur StoqMA. Les vérificateurs StoqMA standards mesurent un seul qubit dans la base de Hadamard. Les auteurs définissent gStoqMA, où le vérificateur peut mesurer un nombre polynomial de qubits dans les bases de Hadamard, $|0\rangle$, ou $|1\rangle$.

   • Ils prouvent que cette généralisation n'augmente pas la puissance computationnelle de la classe ; elle peut être simulée par un vérificateur StoqMA standard avec une perte linéaire dans l'écart complétude/soundness (Théorème 1.2). Cela permet l'utilisation de mesures multi-qubits (spécifiquement des tests d'échange) dans le cadre stoquastique.

3. Procédure de vérification pour StoqSH :
   La contribution centrale est un protocole de vérification pour StoqSH qui accepte un état témoin $|\psi\rangle$ avec une probabilité linéairement liée à l'espérance d'énergie $\langle \psi | H | \psi \rangle$. Le vérificateur choisit aléatoirement entre deux sous-procédures ($V_1$ et $V_2$) :

   • Procédure $V_1$ : Utilise l'oracle pour les éléments de matrice de l'Hamiltonien pour construire un état dépendant de $|\psi\rangle$ et du terme 1-creux $H_j$. Elle effectue un test « de type Hadamard » impliquant une requête d'oracle contrôlée et des mesures dans les bases $X$ et $Z$. La probabilité d'acceptation est liée aux éléments hors diagonale et à l'énergie.
   • Procédure $V_2$ : Une procédure complémentaire qui mesure le dernier qubit dans la base $Z$.
   • Résultat combiné : En moyennant les probabilités d'acceptation de $V_1$ et $V_2$, la probabilité totale d'acceptation devient $1/2 - \frac{1}{4d^2}\langle \psi | H | \psi \rangle$. Cette relation linéaire permet au vérificateur de distinguer les instances de basse énergie (OUI) et de haute énergie (NON).

Contributions et résultats clés

1. Complétude StoqMA de StoqSH
Le résultat principal est le Théorème 1.1, qui énonce que le problème de l'Hamiltonien creux stoquastique est StoqMA-complet.

• Difficulté : Suit immédiatement car les Hamiltoniens stoquastiques locaux sont un cas particulier des Hamiltoniens stoquastiques creux et sont déjà connus pour être StoqMA-durs.
• Contenance : Établie via la procédure de vérification décrite ci-dessus, prouvant que StoqSH $\in$ StoqMA.

2. Hamiltoniens creux stoquastiques séparables et StoqMA(2)
Les auteurs étendent leur analyse au problème de l'Hamiltonien creux stoquastique séparable (SepStoqSH), où le témoin est restreint à être un état produit $|\psi\rangle = |\chi_A\rangle \otimes |\chi_B\rangle$.

• Ils définissent StoqMA(k), l'analogue stoquastique de QMA(k), impliquant $k$ prouveurs non intriqués.
• Théorème 1.4 (Simplifié) : Ils montrent que pour certains paramètres de complétude et de soundness, $k$ prouveurs peuvent être simulés par 2 prouveurs ($StoqMA(k) \subseteq StoqMA(2)$). La preuve adapte le protocole de « Test de produit » de [HM13] au contexte stoquastique, en tirant parti de la capacité des vérificateurs stoquastiques à effectuer des mesures multi-qubits (via la généralisation gStoqMA).
• Théorème 4.5 : Le problème SepStoqSH est StoqMA(2)-complet. La preuve de difficulté adapte la construction circuit-vers-Hamiltonien pour les Hamiltoniens creux séparables [CS12] au contexte stoquastique, en utilisant la théorie des perturbations pour gérer l'absence d'amplification d'erreur dans StoqMA(2).

3. Généralisation de StoqMA
Le papier introduit gStoqMA et prouve que l'autorisation de mesures de taille polynomiale n'augmente pas la puissance de la classe au-delà d'un décalage de paramètre (Théorème 3.5). Cette propriété est soulignée comme potentiellement d'intérêt indépendant pour l'étude des systèmes de preuve stoquastiques.

Signification et affirmations

Le papier prétend faire progresser la compréhension de la classe de complexité StoqMA, qui se situe entre les classes randomisées MA et AM ($NP \subseteq MA \subseteq StoqMA \subseteq AM$).

• Complétude : En identifiant StoqSH comme un problème complet pour StoqMA, les auteurs fournissent un problème naturel plus général pour cette classe, allant au-delà des modèles locaux restreints.
• Preuves séparables : Le travail place StoqMA(2) comme un modèle intermédiaire intéressant entre la vérification stoquastique à un seul prouveur et la vérification quantique multi-prouveurs générale. Il fournit un problème complet naturel (SepStoqSH) pour StoqMA(2), analogue au rôle des Hamiltoniens creux séparables pour QMA(2).
• Robustesse : Les résultats suggèrent que la puissance des vérificateurs stoquastiques est robuste même lorsque le témoin est restreint à être séparable, à condition que l'Hamiltonien soit creux.

Les auteurs notent que, bien qu'ils montrent que StoqMA(k) s'effondre vers StoqMA(2) pour des paramètres spécifiques, la robustesse de cet effondrement sous des bornes d'erreur plus strictes reste une question ouverte. De plus, la complexité du problème de l'Hamiltonien local stoquastique séparable reste ouverte, car les techniques actuelles pour la cohérence des matrices densité locales ne s'appliquent pas directement au contexte stoquastique.

En résumé, le papier établit la difficulté computationnelle des Hamiltoniens creux stoquastiques, introduit une nouvelle technique de vérification utilisant des mesures multi-qubits, et caractérise la puissance des systèmes de preuve stoquastiques avec plusieurs prouveurs non intriqués.