Résumé technique : Le problème du Hamiltonien Local Commutatif : Preuves relativisées contre la dureté BQP

1. Énoncé du problème et contexte

Le problème du Hamiltonien Local Commutatif (CLH) demande si l'énergie de l'état fondamental d'un hamiltonien local, où tous les termes locaux commutent deux à deux, est inférieure à un seuil $\alpha$ ou supérieure à $\beta$. Bien que le problème général du Hamiltonien Local soit QMA-complet, la complexité de la variante commutante reste une question centrale en théorie de la complexité quantique.

Des travaux antérieurs ont démontré que pour des familles spécifiques de hamiltoniens commutants (par exemple, 2-locaux, certains 3-locaux, ou ceux sur des réseaux spécifiques), le problème appartient à NP. Cependant, aucune preuve formelle n'existait pour exclure la possibilité que le problème CLH général soit QMA-complet.

La classe de complexité QIMA (Quantum Interactive Merlin-Arthur with Commuting units) a été introduite par Bostanci et Hwang pour capturer la puissance des vérificateurs quantiques dont les unités de test locales sont des réflexions mutuellement commutantes. Le problème CLH est complet pour QIMA. Par conséquent, la question de savoir si CLH est QMA-complet est équivalente à demander si QIMA = QMA.

Cet article étudie la relation entre QIMA et BQP (Bounded-error Quantum Polynomial time) dans un cadre relativisé. Plus précisément, il cherche à déterminer s'il existe un oracle classique $O$ tel que BQP$^O \not\subseteq$ QIMA$^O$. Un résultat positif fournirait une preuve relativisée contre la possibilité que le problème CLH général soit BQP-dur, et donc contre la possibilité qu'il soit QMA-complet.

2. Méthodologie et définitions

2.1 Le modèle d'oracle QIMA$^O$

Les auteurs définissent un analogue relativisé de QIMA, noté QIMA$^O$, avec des contraintes spécifiques pour garantir que le modèle reste une restriction non triviale de QMA$^O$ :

• Structure du vérificateur : Sur une entrée $x$, le vérificateur effectue un prétraitement classique (en effectuant des requêtes adaptatives à $O$) pour générer un ensemble d'« unités » $W_1^O, \dots, W_m^O$ agissant sur un témoin quantique.
• Commutativité : Sur les instances promises, toutes les unités doivent commuter deux à deux : $[W_i^O, W_j^O] = 0$.
• Exigence de réflexion : Crucialement, toute unité $W_j^O$ contenant au moins une requête d'oracle doit être une réflexion exacte (c'est-à-dire $(W_j^O)^\dagger = W_j^O$ et $(W_j^O)^2 = I$). Les unités sans oracle peuvent être des unitaires arbitraires.
• Vérification : Le vérificateur utilise le test de Hadamard pour vérifier si le témoin est dans l'espace propre $+1$ de chaque unité.
• Absence d'ancilla de confiance : Le vérificateur ne possède aucun espace de travail de confiance au-delà des qubits de contrôle frais utilisés pour les tests de Hadamard.

Les auteurs soutiennent que l'exigence de réflexion est essentielle. Ils montrent que relaxer cela pour permettre des unités commutantes arbitraires (même proches de réflexions) ou autoriser des qubits ancilla de confiance fait s'effondrer la classe vers QMA$^O$.

2.2 Le problème de Forrelation

La séparation est basée sur le problème de la Forrelation, défini par Aaronson. Étant donné un accès oracle à deux fonctions booléennes $f, g: \{0,1\}^n \to \{-1, +1\}$, la tâche est de distinguer entre :

• Oui : $f$ est fortement corrélé avec la transformée de Fourier de $g$ ($\Phi(f,g) \ge \alpha$).
• Non : La corrélation est faible ($|\Phi(f,g)| \le \beta$).

La Forrelation est soluble par un algorithme BQP avec un nombre constant de requêtes quantiques. L'article vise à prouver que tout vérificateur QIMA$^O$ pour la Forrelation nécessite un nombre exponentiel de requêtes.

3. Contributions clés et résultats

3.1 Séparation par oracle : BQP$^O \not\subseteq$ QIMA$^O$

Le résultat principal est la construction d'un oracle classique $O$ tel que BQP$^O \not\subseteq$ QIMA$^O$. Ceci est réalisé en prouvant une borne inférieure de requêtes exponentielle pour le problème de la Forrelation contre les vérificateurs QIMA$^O$.

Théorème 1.7 (Informel) : Tout vérificateur QIMA$^O$ décidant la Forrelation pour toutes les paires promises $(f, g)$ doit satisfaire :
$$C(n) + T(n) \ge \beta 2^n - O(1)$$
où $C(n)$ est le nombre de requêtes de prétraitement classique et $T(n)$ est le nombre total de requêtes d'oracle quantiques.

Esquisse de preuve :

1. Méthode polynomiale : La probabilité d'acceptation du vérificateur est exprimée comme un polynôme dans les entrées de la table de vérité de l'oracle.
2. Commutativité et réflexions : Parce que les unités contenant l'oracle sont des réflexions exactes et commutent, leur opérateur d'acceptation combiné est un produit de projecteurs orthogonaux. Cela permet aux auteurs de définir un projecteur unique $P_f$ représentant l'intersection de tous les sous-espaces d'acceptation.
3. Borne de degré : Le degré du polynôme représentant la probabilité d'acceptation est borné par le nombre total de requêtes quantiques $T(n)$.
4. Paires de Forrelation parfaites : Les auteurs utilisent des « paires de Forrelation parfaites » (fonctions bent) où $\Phi(g, h) = 1$. Ils montrent que la perturbation de $h$ par $k$ bits change la valeur de la Forrelation de manière linéaire : $\Phi(g, f) = 1 - 2k/N$.
5. Symétrisation : En fixant le transcript classique et en faisant la moyenne sur les fonctions ayant une distance de Hamming fixe d'une paire parfaite, ils construisent un polynôme univarié $q(k)$.
6. Comptage de racines : Le polynôme $q(k)$ doit être nul pour toutes les instances « Non » (une large plage de $k$) et non nul pour l'instance « Oui » ($k=0$). Un polynôme non nul ne peut pas avoir plus de racines que son degré, ce qui force le degré (et donc le nombre de requêtes) à être exponentiel.

3.2 Robustesse de la séparation

L'article démontre que la séparation tient même sous de légères relaxations du modèle :

• Déviations négligeables : Si les unités contenant l'oracle sont autorisées à être négligeablement proches (en norme d'opérateur) de réflexions exactes, la classe reste QIMA$^O$, et la borne inférieure tient toujours.
• Support d'adresse restreint : Les auteurs étendent la borne inférieure à des unités qui ne sont pas des réflexions mais qui effectuent une seule requête, à condition que les circuits sans oracle entourant la requête agissent de manière non triviale sur seulement un petit nombre de qubits d'adresse ($k$). Si $n - k(n) = \omega(\log n)$, la borne inférieure de requêtes reste superpolynomiale.

3.3 Étroitesse du modèle (Résultats d'effondrement)

Pour justifier les contraintes spécifiques de QIMA$^O$, les auteurs prouvent que la relaxation de ces contraintes fait s'effondrer la classe vers QMA$^O$ :

• Déviations inverse-polynomiales : Si les unités sont autorisées à être à une distance inverse-polynomiale d'une réflexion (plutôt que négligeable), la classe s'effondre en QMA$^O$. Ceci est montré en utilisant une variation du gadget d'amplification de Marriott-Watrous, construisant une unité unique qui simule un vérificateur QMA.
• Requête unique sans réflexion : Si l'exigence de réflexion est totalement supprimée mais que les unités sont restreintes à une seule requête, la classe s'effondre également en QMA$^O$. Cela utilise une construction d'horloge cyclique (similaire à Feynman-Kitaev) pour encoder une simulation multi-requêtes en une seule requête.
• Ancilla de confiance : Autoriser le vérificateur à posséder un seul qubit ancilla de confiance (initialisé à $|0\rangle$) fait s'effondrer QIMA en QMA et QIMA$^O$ en QMA$^O$. Cela repose sur le problème du « Pinned Commuting Local Hamiltonian », qui est connu pour être QMA-complet.

4. Signification et affirmations

L'article prétend fournir une preuve relativisée contre la possibilité que le problème CLH général soit BQP-dur. Puisque BQP est contenu dans QMA, si CLH était BQP-dur, cela impliquerait des propriétés structurelles fortes sur QMA. La séparation $BQP^O \not\subseteq QIMA^O$ suggère que la contrainte de commutativité dans QIMA (et par extension CLH) est une restriction significative qui empêche la classe de capturer toute la puissance de BQP, même en présence d'oracles.

De plus, ce travail clarifie la précision de la définition de QIMA. Les auteurs soutiennent que la combinaison spécifique de commutativité, de l'exigence de réflexion pour les requêtes d'oracle, et de l'absence d'ancillas de confiance est nécessaire pour définir une classe qui est strictement plus faible que QMA. Relaxer l'une de ces conditions permet de retrouver immédiatement toute la puissance de QMA, suggérant que la « nature quantique » de QIMA est fragile et repose précisément sur ces contraintes structurelles.

Les résultats ne résolvent pas la question non relativisée de savoir si CLH est QMA-complet, mais ils établissent que toute preuve d'une telle complétude nécessiterait des techniques non-relativisantes, car l'énoncé échoue par rapport à l'oracle construit.