Apakah ada yang setara dengan derandomisasi untuk algoritma kuantum?

Dengan beberapa algoritma acak Anda dapat derandomisasi algoritma, menghilangkan (dengan biaya yang mungkin dalam waktu berjalan) penggunaan bit acak dan memaksimalkan beberapa batas bawah pada tujuan (biasanya dihitung menggunakan fakta bahwa teorema adalah tentang kinerja yang diharapkan dari acak algoritma). Apakah ada persamaan untuk algoritma kuantum? Apakah ada hasil "dequantisasi" yang terkenal? Atau ruang keadaan yang mendasarinya terlalu besar untuk teknik semacam ini?

Ada posting blog oleh Fortnow tentang topik ini. Diyakini bahwa tidak ada harapan untuk program "dequantisasi", mirip dengan derandomisasi.

Di sisi lain, untuk beberapa hasil non-kuantum spesifik yang diperoleh dengan menggunakan metode kuantum, dimungkinkan untuk menghapus kuantum dalam bukti. Sebagai contoh, Kerenidis dan de Wolf (2002) membuktikan batas bawah eksponensial pertama untuk panjang kemungkinan kode 2-kueri yang dapat didekodekan secara lokal menggunakan argumen kuantum. Kemudian, Ben-Aroya, Regev dan de Wolf (2007) dapat menghapus kuantum bukti (meskipun garis argumen masih memodelkan kuantum). Situasi serupa juga muncul dalam membuktikan batas bawah untuk kekakuan matriks Hadamard, dan dalam menunjukkan bahwa PP ditutup di bawah persimpangan (meskipun dalam urutan kronologis terbalik :)). Lihat survei ini oleh Drucker dan de Wolf untuk referensi dan diskusi.

Ada kelas-kelas tertentu gerbang kuantum yang dapat disimulasikan secara efisien dengan komputer klasik. Jika tidak ada keterjeratan, perhitungan dengan keadaan murni (yaitu bukan keadaan acak) dapat disimulasikan secara efisien. Gerbang klasik Gerbang reversibel adalah bagian dari gerbang kuantum, dan karenanya dapat disimulasikan secara efisien. Dua contoh ini cukup sepele, namun ada beberapa set gerbang non-sepele yang dikenal.

1. Gerbang yang berani seperti yang disebutkan dalam jawaban Yosua
2. Gerbang grup Clifford (lihat arXiv: quant-ph / 0406196 )
3. Gerbang yang cocok (lihat arXiv: 0804.4050 )
4. Gerbang komuter, dll.

$SU(2^N)$$SU(2^N)$

Tampaknya sangat tidak mungkin bahwa mekanika kuantum dapat disimulasi secara efisien, sehingga program dequantisasi seperti itu pada umumnya tidak mungkin dilakukan. Namun ada rezim di mana ini bekerja, yaitu dengan bukti interaktif. Beberapa jenis sistem bukti interaktif dengan verifier kuantum telah terbukti memiliki kekuatan yang sama jika verifier kuantum diganti dengan verifier klasik murni. Untuk contohnya, lihat bukti Jain, Ji, Upadhyay dan Watrous bahwa QIP = PSPACE ( arXiv: 0907.4737 ).

Satu pengaturan yang menarik untuk mempelajari "dequantization" adalah kompleksitas komunikasi. Di sini, pertanyaan yang menarik adalah apakah batas atas dapat diberikan pada jumlah keterjeratan yang perlu dibagikan Alice dan Bob untuk mencapai protokol kuantum yang efisien untuk menyelesaikan beberapa masalah. Ini akan menjadi analog kuantum dari Teorema Newman dari kompleksitas komunikasi klasik. Gavinsky telah memberikan masalah relasional yang tidak dapat dilakukan, tetapi sejauh yang saya tahu ini masih terbuka untuk masalah fungsional (total).

Juga, sebuah tambahan pada komentar Joe tentang gerbang komuter: Bremner, Jozsa dan Shepherd baru-baru ini menunjukkan (arXiv: 1005.1407) bahwa gagasan tertentu tentang sirkuit komuter tidak mungkin dapat disimulasikan, karena ini akan membuat hierarki polinomial turun ke tingkat ketiga.

Meskipun secara umum "dequantization" tidak mungkin, saya percaya bahwa ide semacam ini membantu menginspirasi algoritma holografik Valiant. Atau, paling tidak, Anda dapat melihat karyanya sebagai beberapa hasil dequantisasi parsial pada kelas terbatas dari sirkuit kuantum. Lihat, misalnya: L. Valiant. Sirkuit Quantum Yang Dapat Disimulasikan Secara Klasik dalam Waktu Polinomial. SIAM J. Comput. 31 (4) 1229-1254 (2002).