Pemisahan orakular antara sirkuit kuantum kedalaman pol dan log

16

Masalah berikut muncul dalam daftar Aaronson, Sepuluh Tantangan Semi-Grand untuk Teori Komputasi Quantum .

ApakahBQP=BPPBQNC Dengan kata lain, dapatkah bagian "kuantum" dari algoritma kuantum apa pun dikompresi menjadi kedalaman, asalkan kita ' Apakah Anda bersedia melakukan postprocessing klasik polinomial-waktu? (Ini diketahui benar untuk algoritma Shor.) Jika demikian, membangun komputer kuantum untuk tujuan umum akan jauh lebih mudah daripada yang diyakini secara umum! Secara kebetulan, tidak sulit untuk memberikan pemisahan oracle antara dan , tetapi pertanyaannya adalah apakah ada fungsi konkret yang "membuat" oracle tersebut.polylog(n)BQPBPPBQNC

Telah diduga oleh Jozsa bahwa jawaban untuk pertanyaannya adalah ya dalam model perhitungan kuantum "berbasis pengukuran": di mana pengukuran lokal, gerbang lokal adaptif dan post-processing klasik yang efisien diperbolehkan. Lihat juga posting terkait ini .

Pertanyaan . Saya ingin tahu tentang pemisahan oracle yang saat ini dikenal di antara kelas-kelas ini (atau, setidaknya, pemisahan oracle yang dirujuk oleh Aaronson).

cc.complexity-theory quantum-computing circuit-complexity quantum-information circuit-depth Juan Bermejo Vega
sumber
5
Saya kira masalah pohon terpaku adalah kandidat yang baik untuk pemisahan. Intuisi adalah bahwa komputer klasik pada dasarnya tidak berguna untuk tugas ini, dan sirkuit kuantum kedalaman polylog hanya dapat mencapai polylog jauh ke dalam pohon terpaku, tetapi Anda harus mencapai titik keluar yang secara polinomi jauh dari titik entri.
Robin Kothari

Jawaban:

12

BQPBPPBQNC

Scott Aaronson
sumber
1
Begitu ya, terima kasih Scott. Baiklah, saya pribadi suka BQP ini = BPP ^ BQNC? pertanyaan, karena signifikansinya untuk membangun komputer kuantum. Saya pikir itu layak untuk memberikan satu atau dua pemikiran.
Juan Bermejo Vega
1
Pertanyaan ini tampaknya telah diselesaikan: lihat arXiv: 1909.10303 dan arXiv: 1909.10503 .
Sanketh Menda