Lecture sur

Que dois-je lire pour comprendre ce problème?

La puissance des circuits quantiques de faible profondeur. Est-ce que ? En d'autres termes, la partie "quantique" de tout algorithme quantique peut-elle être compressée à la profondeur du polylogue (n), à condition que nous soyons prêts à effectuer un post-traitement classique en temps polynomial? (Cela est connu pour l'algorithme de Shor.) Si c'est le cas, la construction d'un ordinateur quantique à usage général serait beaucoup plus facile qu'on ne le pense généralement! Soit dit en passant, il n'est pas difficile de séparer l'oracle entre B Q P et B P P B Q N $BQP = BPP^{BQNC}$$BQP$$BPP^{BQNC}$, mais la question est de savoir s'il existe une fonction concrète "instanciant" un tel oracle. --Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html

Cela a été conjecturé par R. Jozsa dans la section 8 de arXiv: quant-ph / 0508124 . Si vous êtes déjà familier avec l'informatique quantique et la théorie de la complexité quantique, vous pouvez commencer par lire cette section.

Une lecture importante est arXiv: quant-ph / 0006004 , où Cleve et Watrous montrent que l'algorithme de Shor est dans cette classe.