Résumé - Pseudorandomité inconditionnelle contre des circuits quantiques superficiels

Pseudorandomité inconditionnelle contre des circuits quantiques superficiels

2025-07-24 20:33:26

{"Soumik Ghosh","Sathyawageeswar Subramanian","Wei Zhan"}

{quant-ph,cs.CC}

Ce papier établit les premières constructions pseudorandoms sécurisées et efficaces sans condition pour les classes de circuits quantiques à faible profondeur. Les auteurs montrent que : - Toute fonction 2-design quantique fournit une pseudorandomness inconditionnelle contre les circuits QNC0 avec un nombre arbitraire de qubits d'appoint et les circuits AC0 ◦ QNC0 avec des qubits d'appoint presque linéaires. - Les états de sous-espaces phasés aléatoires, où les phases sont choisies en utilisant une fonction à indépendance de 4, sont inconditionnellement pseudoentanglés contre les circuits mentionnés ci-dessus. - Toute fonction 2-design unitaire fournit des unitaires pseudorandoms inconditionnellement sécurisés pour les demandes parallèles contre des adversaires QNC0 géométriquement locaux, même avec une posttraitement AC0 limité. La clé de l'insight est que, en raison des contraintes de profondeur, chaque qubit de sortie des circuits quantiques à faible profondeur dépend localement seulement d'un sous-ensemble de qubits d'entrée, limitant ainsi fondamentalement leur capacité à distinguer certains objets quantiques structurés des objets Haar-aléatoires. Cette recherche montre que la pseudorandomness quantique computationnelle peut être réalisée inconditionnellement pour des classes naturelles d'adversaires restreints, ouvrant de nouvelles directions dans la théorie de la complexité quantique. ## Points Clés : - **Sécurité Inconditionnelle** : La pseudorandomness est obtenue sans s'appuyer sur des hypothèses théoriques de complexité ou des hypothèses cryptographiques. - **Circuits Quantiques à Faible Profondeur** : Les résultats s'appliquent aux circuits quantiques à faible profondeur, qui modélisent les appareils quantiques à court terme avec des temps de cohérence et des nombres de portes limités. - **2-designs** : La seule propriété nécessaire pour les constructions est d'être un (approximatif) 2-design. - **États et Unitaires Pseudorandoms** : Les constructions produisent des états et des unitaires pseudorandoms qui semblent Haar-aléatoires aux observateurs quantiques computationnellement bornés. - **Pseudoentanglement** : Les constructions atteignent également un pseudoentanglement inconditionnel contre les circuits quantiques à faible profondeur. - **Unitaires Pseudorandoms pour Demandes Parallèles** : Les constructions produisent des unitaires pseudorandoms inconditionnellement sécurisés pour les demandes parallèles contre des adversaires QNC0 géométriquement locaux. ## Implications : - **Théorie de la Complexité Quantique** : Les résultats fournissent de nouvelles perspectives sur la relation entre la difficulté et la pseudorandomness quantique. - **Informatique Quantique** : Les résultats ont des applications potentielles en cryptographie quantique, conception d'algorithmes quantiques et simulation quantique. - **Cryptographie** : Les résultats pourraient conduire à de nouveaux protocoles cryptographiques quantiques qui sont sécurisés contre les ordinateurs quantiques à court terme.