Saya akan menjawab pertanyaan pertama Anda:
Adakah contoh keluarga fungsi alami yang dapat dipelajari komputer kuantum lebih cepat daripada komputer klasik yang diberi asumsi kriptografi?
Yah, itu tergantung pada model yang tepat dan sumber daya yang diminimalkan. Salah satu pilihan adalah membandingkan kompleksitas sampel (untuk pembelajaran PAC distribusi-independen) dari model klasik standar dengan model kuantum yang diberikan sampel kuantum (yaitu, alih-alih diberi input acak dan nilai fungsi yang sesuai, algoritma disediakan dengan superposisi kuantum atas input dan nilai fungsinya). Dalam pengaturan ini, pembelajaran PAC kuantum dan pembelajaran PAC klasik pada dasarnya setara. Batas atas klasik pada kompleksitas sampel dan batas bawah kuantum pada kompleksitas sampel hampir sama, seperti yang ditunjukkan oleh urutan makalah berikut:
[1] R. Servedio dan S. Gortler, "Kesetaraan dan pemisahan antara pembelajaran kuantum dan klasik," SIAM Journal on Computing, vol. 02138, hlm. 1–26, 2004.
[2] A. Atici dan R. Servedio, “Peningkatan batasan pada algoritma pembelajaran kuantum,” Quantum Information Processing, hlm. 1–18, 2005.
[3] C. Zhang, "Batas bawah yang ditingkatkan pada kompleksitas kueri untuk pembelajaran PAC kuantum," Information Processing Letters, vol. 111, tidak. 1, hlm. 40–45, Desember 2010.
Pindah ke kompleksitas waktu, menggunakan model PAC kuantum yang sama, Bshouty dan Jackson menunjukkan bahwa DNF dapat menjadi PAC kuantum yang dipelajari dalam waktu polinomial atas distribusi seragam [4], lebih ditingkatkan lagi dalam [5]. Algoritma klasik paling dikenal untuk ini berjalan diO ( ncatatann)waktu. Atici dan Servedio [6] juga menunjukkan hasil yang meningkat untuk pembelajaran dan pengujian juntas.
[4] N. Bshouty dan J. Jackson, "Mempelajari DNF atas distribusi seragam menggunakan oracle contoh quantum," SIAM Journal on Computing, vol. 28, tidak. 3, hlm. 1136–1153, 1998.
[5] J. Jackson, C. Tamon, dan T. Yamakami, “Quantum DNF learningability revisited,” Computing and Combinatorics, hlm. 595–604, 2002.
[6] A. Atıcı dan R. Servedio, "Algoritma Quantum untuk Belajar dan Menguji Juntas," Pemrosesan Informasi Quantum, vol. 6, tidak. 5, hlm. 323–348, Sep 2007.
Di sisi lain, jika Anda hanya tertarik pada model PAC klasik standar, menggunakan komputasi kuantum sebagai alat pasca-pemrosesan (yaitu, tidak ada sampel kuantum), maka Servedio dan Gortler [1] mengamati bahwa ada kelas konsep karena untuk Kearns dan Valiant yang tidak bisa dipelajari PAC secara klasik dengan asumsi kekerasan anjak Blum integer, tetapi dapat secara kuantitatif PAC dipelajari menggunakan algoritma Shor.
Situasi untuk model pembelajaran pasti Angluin melalui pertanyaan keanggotaan agak mirip. Quantum queries hanya dapat memberikan percepatan polinomial dalam hal kompleksitas kueri. Namun, ada percepatan eksponensial dalam kompleksitas waktu dengan asumsi adanya fungsi satu arah [1].
Saya tidak tahu tentang pertanyaan kedua. Saya akan senang mendengar lebih banyak tentang itu juga.