Les scientifiques de NTT disent qu'ils ont une nouvelle façon de vérifier l'avantage quantique

Sunnyvale, Californie - 26 octobre 2022 - NTT Research a annoncé qu'un scientifique de son Laboratoire de cryptographie et de sécurité de l'information (CIS) et un collègue du Laboratoires d'informatique sociale NTT (SIL) ont rédigé un article novateur sur l'avantage quantique. L'article a été sélectionné pour être présenté au Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), qui se déroule du 31 octobre au 3 novembre. XNUMX à Denver.

Les co-auteurs de l'article, intitulé "Avantage quantique vérifiable sans structure», sont le Dr Takashi Yamakawa, chercheur distingué au NTT SIL et le Dr Mark Zhandry, chercheur principal au Recherche NTT Laboratoire CEI. Le travail a été effectué en partie à l'Université de Princeton, où le Dr Yamakawa était chercheur invité et le Dr Zhandry est également professeur adjoint d'informatique. 

Le sujet de l'avantage quantique (ou accélération quantique) concerne les types de problèmes que les ordinateurs quantiques peuvent résoudre plus rapidement que les ordinateurs classiques, ou non quantiques, et à quel point ils sont plus rapides. Les problèmes en question sont communément décrits comme une classe de temps polynomial (NP) non déterministe. Combien d'avantage pourrait varier dans une large mesure. Un ordinateur quantique peut être capable de résoudre un problème particulier en une minute ou une seconde qui prend une semaine à un ordinateur classique, ou peut-être un temps exponentiel insondable. Dans cet article, les auteurs relèvent le défi de vérifier cette supériorité, et de le faire efficacement. À ce jour, les démonstrations de l'avantage quantique ont impliqué une «structure» importante ou une communication aller-retour entre deux ou plusieurs parties. La percée de l'article de Yamakawa et Zhandry est de démontrer un problème NP difficile où la vérification est possible sans structure.

"C'est la première fois que nous constatons une accélération quantique exponentielle pour un problème de recherche NP, qui ne nécessite qu'un oracle aléatoire", a déclaré le Dr Scott Aaronson, professeur d'informatique à l'Université du Texas à Austin, qui a commenté une première version. de l'article lors d'un atelier le 13 juin 2022 au Simons Institute for the Theory of Computing. En n'exigeant qu'un oracle aléatoire, c'est-à-dire une boîte noire théorique qui génère des réponses aléatoires à chaque requête, Yamakawa et Zhandry ont construit leur problème sur des hypothèses de calcul non structurées. En tant que tel, leur problème s'aligne plus étroitement sur les fonctions à sens unique que sur les fonctions structurées, telles que celles trouvées dans la cryptographie à clé publique. Cet alignement unidirectionnel facilite une vérification efficace.

"C'est excitant de voir des cryptographes affiliés à NTT collaborer à des recherches qui méritent une fois de plus le label de "percée", en particulier dans un article qui enrichit notre compréhension de l'informatique quantique, un autre domaine d'intérêt pour nous chez NTT Research", a déclaré Kazuhiro Gomi. , président et chef de la direction de NTT Research. "Félicitations et meilleurs vœux à tous les participants à cette prestigieuse conférence IEEE." 

Le problème de recherche NP conçu par Yamakawa et Zhandry était un problème deux en un qui consiste à trouver 1) une chaîne de n symboles qui est un mot de code d'un code de correction d'erreur donné, et 2) une chaîne de n symboles où chaque le symbole est mappé à zéro sous l'oracle aléatoire. Chaque problème séparément est facile. Mais trouver une seule chaîne de symboles qui est à la fois un mot de code et correspond à zéro est beaucoup plus difficile, du moins de manière classique. "Si vous êtes quantique, vous pouvez résoudre cela en temps polynomial", a déclaré le Dr Zhandry, "mais si vous êtes classique, au moins si vous êtes dans ce modèle de boîte noire, vous avez besoin d'un temps exponentiel." En revanche, étant donnée une solution potentielle, il est simple de la vérifier en vérifiant qu'elle résout séparément chacun des deux problèmes. Notez que, comme il sied à un article pour FOCS, ce travail est basique ou fondamental. Comme souligné dans l'exposé du Dr Aaronson au Simons Institute (discuté dans ce NTT Research article de blog), l'argument Yamakawa-Zhandry tombe dans une classe d'accélérations qui peuvent être facilement vérifiées mathématiquement, mais pas démontrées pratiquement par un véritable ordinateur quantique de si tôt. Au-delà de son schéma de vérification révolutionnaire, cependant, le document souligne également quelque chose de nouveau concernant l'étendue de l'accélération quantique.

«Avant nos travaux, nous avions des exemples d'avantage quantique pour les problèmes NP, comme la factorisation ou, dans le cadre de la boîte noire, la recherche de période. Mais il s'avère que l'algorithme quantique sous-jacent à tous ces exemples était essentiellement une recherche de période - bien que montrer comment appliquer la recherche de période à ces exemples n'était souvent pas trivial », a déclaré le Dr Zhandry. « Notre article montre qu'il y a au moins un deuxième cas. Vous pourriez interpréter cela avec optimisme comme disant qu'il y a de l'espoir que l'avantage quantique est plus répandu que nous ne le pensions peut-être auparavant.

Parrainé par le comité technique de l'IEEE Computer Society sur les fondements mathématiques de l'informatique (TCMF), FOCS est une conférence de premier plan dans le domaine de l'informatique théorique. L'appel à contributions pour FOCS 2022, le 63e rassemblement annuel de ce type, a répertorié l'informatique quantique comme l'un des 17 domaines d'intérêt généraux. L'article Yamakawa-Zhandry devrait être présenté le 31 octobre 2022 à 10h15 MT. Pour en savoir plus et vous inscrire à cet événement, rendez-vous sur FOCUS 2022 en ligne.