Bukti kuantum dari teorema klasik

Saya tertarik pada contoh masalah di mana teorema yang tampaknya tidak ada hubungannya dengan mekanika kuantum / informasi (misalnya menyatakan sesuatu tentang benda-benda klasik murni) tetap dapat dibuktikan menggunakan alat kuantum. Sebuah survei Bukti Kuantum untuk Teorema Klasik (A. Drucker, R. Wolf) memberikan daftar masalah yang bagus, tetapi tentu saja ada banyak lagi.

Sangat menarik akan menjadi contoh di mana bukti kuantum tidak hanya mungkin, tetapi juga "lebih mencerahkan", dalam analogi dengan analisis nyata dan kompleks, di mana menempatkan masalah nyata dalam pengaturan kompleks sering membuatnya lebih alami (misalnya geometri lebih sederhana karena ditutup secara aljabar, dll.); dengan kata lain, masalah klasik yang dunia kuantum adalah "habitat alami" mereka.$\mathbb{C}$

(Saya tidak mendefinisikan "kuantum" di sini dalam arti yang tepat dan orang dapat berargumen bahwa semua argumen tersebut akhirnya bermuara pada aljabar linier; well, kita juga dapat menerjemahkan argumen apa pun menggunakan bilangan kompleks untuk menggunakan hanya pasangan real - tetapi jadi apa ?)

Ada makalah baru-baru ini dari Scott Aaronson yang memberikan bukti baru bahwa permanen adalah # P-hard. Bukti ini didasarkan pada model komputasi kuantum linier-optik dan lebih intuitif daripada Leslie Valiant.

Menurut pendapat saya, saya suka makalah berikut:

Katalin Friedl, Gabor Ivanyos, Miklos Santha. Pengujian kelompok yang efisien. Dalam STOC'05.

Di sini mereka mendefinisikan penguji "klasik" untuk kelompok abelian. Namun, pertama-tama mereka mulai dengan memberikan tester kuantum, dan kemudian melanjutkan dengan menghilangkan semua bagian kuantum.

Apa yang saya suka dari makalah ini adalah bahwa mereka menggunakan penguji kuantum untuk mendapatkan intuisi dan menggunakannya untuk mendekati masalah. Mungkin terdengar pendekatan yang lebih sulit (mulai dari kuantum dan klasik go), tetapi penulis adalah peneliti terkenal dalam komputasi kuantum. Jadi mungkin bagi mereka lebih mudah untuk memulai dengan itu.

Saya akan mengatakan bahwa kontribusi teknis utama mereka adalah penguji homomorfisme, yang mereka gunakan untuk menghilangkan bagian-bagian kuantum.

Dua hasil yang sangat baru dan menarik:

• Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, dan Ronald de Wolf membuktikan bahwa "tidak ada program linier ukuran polinomial (LP) yang terkait proyek-proyek polytope dengan polytope salesman keliling, bahkan jika LP tidak diharuskan simetris "(dikutip dari abstrak).
  Mereka menggunakan kompleksitas komunikasi kuantum sebagai alat. Lihat makalah mereka dan posting blog Gil Kalai . Perhatikan juga komentar Dave di bawah posting Gil Kalai. Saya belum membaca koran, jadi saya tidak bisa berkomentar sendiri tentang di mana dan bagaimana hal-hal kuantum digunakan.

• Andrew M. Childs, Shelby Kimmel, dan Robin Kothari menggunakan kompleksitas kueri kuantum untuk membuktikan batas bawah untuk ukuran yang sangat klasik, yang merupakan penghitungan fungsi gerbang formula seperti PARITY. Lihat kertas mereka .

Sebagai permanen memberikan probabilitas amplitudo hasil pengukuran boson setelah mereka mengganggu dalam interferometer linier, Scheel memperoleh bukti "kuantum" sederhana bahwa nilai absolut permanen dari setiap matriks kesatuan adalah 1 ( http://arxiv.org/abs / quant-ph / 0406127 ).

• lihat juga komputasi klasik mencakup gagasan - gagasan kuantum semacam ikhtisar / survei semi-pop-sains dari fenomena dikotomi klasik / kuantum ini oleh Wolchover yang menulis untuk lembaga Simons dengan beberapa contoh & lead / ref.

Dalam beberapa tahun terakhir, ide-ide kuantum telah membantu para peneliti membuktikan keamanan skema enkripsi data yang menjanjikan yang disebut cryptosystems berbasis kisi, beberapa aplikasi yang dapat menutupi informasi sensitif pengguna, seperti DNA, bahkan dari perusahaan yang memprosesnya. Bukti komputasi kuantum juga menghasilkan formula untuk panjang minimum kode koreksi kesalahan, yang merupakan perlindungan terhadap korupsi data.

Ide-ide kuantum juga mengilhami sejumlah hasil teoretis yang penting, seperti penolakan terhadap algoritme lama dan keliru yang diklaim dapat secara efisien menyelesaikan masalah penjual keliling yang terkenal sulit bepergian, yang menanyakan cara menemukan rute tercepat melalui beberapa kota.

• contoh lain baru-baru ini yang mirip dengan arah penelitian dari Bukti Alam Razborov / Rudich (yang terkait pemisahan kelas kompleksitas dengan melanggar generator nomor acak)

Batas bawah kuantum untuk membedakan fungsi acak dari permutasi acak Henry Yuen

Masalah membedakan antara fungsi acak dan permutasi acak pada domain ukuran N penting dalam kriptografi teoretis, di mana keamanan banyak primitif bergantung pada kekerasan masalah. Kami mempelajari kompleksitas kueri kuantum dari masalah ini ...