Conséquences de$MIP^\ast=RE$À propos des algorithmes quantiques

Question

La preuve (en attente d'examen par les pairs) de$MIP^\ast=RE$dans cette pré-publication a été saluée comme une percée significative. La signification de ce résultat est abordée par Henry Yuen (l'un des auteurs) dans ce billet de blog . Scott Aaronson énumère également certaines des implications majeures dans ce billet de blog .

Pour un jeu non local ($G$), définissent le supremum des probabilités de succès pour les stratégies de produits tensoriels non relativistes comme$\omega^\ast(G)$, et le supremum des probabilités de succès pour une stratégie d'opérateur de navette relativiste (QFT) comme$\omega^{co}(G)$. Étant donné que la QM non relativiste est un cas particulier de QFT, il est clair qu'une stratégie optimale basée sur l'opérateur de navettage est au moins aussi bonne qu'une stratégie optimale basée sur le produit tenseur,$\omega^\ast(G) \le \omega^{co}(G)$.

Ma compréhension du message de Yuen est qu'une conséquence de$MIP^\ast=RE$est qu'il existe des jeux non locaux pour lesquels$\omega^\ast(G) < \omega^{co}(G)$. Plus précisément, dit-il

Il doit y avoir un jeu$G$, alors, pour lequel la valeur quantique est différente de la valeur de l'opérateur commutant. Mais cela implique que le problème de Tsirelson a une réponse négative, et donc la conjecture d'intégration de Connes est fausse.

Je comprends que cela signifie qu'il existe une classe de problèmes pour lesquels les algorithmes utilisant des techniques de QFT (opérateurs de commutation) ont des probabilités de succès plus élevées que les algorithmes utilisant des techniques de QM non relativistes (produits tensoriels, formalisme de circuit quantique).

La première partie de ma question est, en supposant que cette preuve soit valable :

• Fait$MIP^\ast=RE$impliquer qu'il existe un ensemble de problèmes qui peuvent être résolus plus efficacement en employant le formalisme mathématique de QFT (opérateurs de commutation) plutôt que le formalisme QM non relativiste (circuits quantiques conventionnels) ?

Sauf erreur de ma part, cela semble découler directement des déclarations de Yuen. Si tel est le cas, est-il possible qu'il existe un ensemble de jeux non locaux pour lesquels$\omega^\ast(G) < 0.5$et$\omega^{co}(G) > 0.5$? Plus précisément, la deuxième partie de ma question est la suivante :

• Fait$MIP^\ast=RE$impliquent qu'il existe (ou pourrait exister) un ensemble de problèmes pouvant être résolus à l'aide d'opérateurs de commutation qui ne peuvent pas être résolus à l'aide de circuits quantiques, ou cette possibilité est-elle fermée par l'universalité du modèle de circuit quantique ?

EDIT : Henry Yuen a créé un wiki MIP* pour ceux qui souhaitent mieux comprendre cette classe de complexité ou la$MIP^\ast = RE$résultat.

Answer 1

Je ne sais pas si le résultat MIP* = RE, et en particulier l'affirmation qu'il existe un jeu non local$G$où$\omega^*(G) \neq \omega^{co}(G)$, a des implications algorithmiques pour les ordinateurs quantiques. Il y a quelques choses à dire ici.

Le résultat MIP* = RE concerne les problèmes de calcul qui peuvent être vérifiés à l' aide de jeux non locaux, par opposition à ce qui peut être résolu par des jeux non locaux (je ne suis pas sûr de ce que cela signifierait, de toute façon !). La distinction entre vérification et résolution est due à ce qui suit : dans un jeu non local, nous supposons qu'Alice et Bob connaissent magiquement la réponse au problème (nous supposons donc qu'ils peuvent résoudre instantanément n'importe quel problème de calcul). Leur défi n'est pas de le résoudre, mais de prouverà un vérificateur classique en temps polynomial, ils connaissent la réponse. Le simple fait de connaître la réponse à quelque chose ne signifie pas que vous êtes capable de convaincre quelqu'un d'autre de la réponse. Le fait qu'Alice et Bob puissent utiliser les corrélations du cadre du produit tensoriel ou du cadre de l'opérateur commutant affecte ce qu'ils sont capables de prouver au vérificateur. MIP* = RE montre qu'avec les corrélations des produits tensoriels, Alice et Bob peuvent prouver qu'ils savent qu'une machine de Turing finit par s'arrêter. C'est quelque chose qui ne peut pas être fait si Alice et Bob partagent des corrélations d'opérateurs de navettage ; par conséquent, le modèle de l'opérateur de navette diffère du modèle du produit tensoriel.

La deuxième chose que je voulais mentionner est, séparément, c'est une question intéressante de savoir si l'on peut définir un modèle de calcul quantique qui parle d'opérateurs commutants et de systèmes de dimension infinie. Il semble que Cleve et al aient essayé de proposer un modèle pour cela, quelque chose qu'ils appellent le modèle de circuit C* :https://arxiv.org/pdf/1811.12575.pdf. Vous pourriez trouver cela intéressant.