Worst-case depth hierarchy for shallow quantum circuits
Cet article établit un théorème de hiérarchie de profondeur inconditionnel pour les circuits quantiques peu profonds () en construisant une famille de problèmes interactifs qui séparent strictement les circuits de profondeur de ceux de profondeur et démontre un avantage quantique inconditionnel sur le classique, obtenu grâce à des techniques novatrices liant les systèmes de contraintes aux jeux non locaux pour prouver que l'augmentation de la profondeur est nécessaire pour réaliser des corrélations non locales spécifiques.