Membaca di

Apa yang harus saya baca untuk memahami masalah ini?

Kekuatan sirkuit kuantum kecil-kedalaman. Apakah ? Dengan kata lain, dapatkah bagian "kuantum" dari algoritma kuantum apa pun dikompres ke kedalaman polylog (n), asalkan kami bersedia melakukan postprocessing klasik waktu polinomial? (Ini diketahui benar untuk algoritma Shor.) Jika demikian, membangun komputer kuantum untuk keperluan umum akan jauh lebih mudah daripada yang diyakini secara umum! Kebetulan, itu tidak sulit untuk memberikan pemisahan oracle antara B Q P dan B P P B Q N $BQP = BPP^{BQNC}$$BQP$$BPP^{BQNC}$, tetapi pertanyaannya adalah apakah ada fungsi konkret "instantiating" oracle tersebut. --Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html

Ini dugaan oleh R. Jozsa di Bagian 8 dari arXiv: quant-ph / 0508124 . Jika Anda sudah terbiasa dengan komputasi kuantum dan teori kompleksitas kuantum, Anda bisa mulai dengan membaca bagian itu.

Bacaan penting adalah arXiv: quant-ph / 0006004 , di mana Cleve dan Watrous menunjukkan bahwa algoritma Shor ada di kelas itu.