Informatique quantique, post-sélection et temps polynomial probabiliste

J'étudie la classe de problèmes résolubles efficacement par un ordinateur quantique, étant donné la capacité de « post-sélectionner » les résultats des mesures. Je prouve que cette classe coïncide avec une classe de complexité classique appelée PP, ou temps polynomial probabiliste. En utilisant ce résultat, je montre que plusieurs changements simples aux axiomes de la mécanique quantique nous permettraient de résoudre efficacement des problèmes complets en PP. Le résultat implique également, comme un corollaire facile, un théorème célèbre de Beigel, Reingold et Spielman selon lequel PP est fermé sous l'intersection, ainsi qu'une généralisation de ce théorème due à Fortnow et Reingold. Cela illustre que l'informatique quantique peut fournir de nouvelles preuves plus simples de résultats majeurs sur le calcul classique.