Apakah ada masalah di mana komputer kuantum diketahui memberikan keunggulan eksponensial?

Secara umum diyakini dan diklaim bahwa komputer kuantum dapat mengungguli perangkat klasik dalam setidaknya beberapa tugas.

Salah satu contoh yang paling sering dikutip dari masalah di mana komputer kuantum akan mengungguli perangkat klasik adalah , tapi sekali lagi, juga tidak diketahui apakah Anjak juga dapat dipecahkan secara efisien dengan komputer klasik (yaitu, apakah Anjak ∈ P ).$\text{Factoring}$$\text{Factoring}$$\text{Factoring}\in \text{P}$

Untuk masalah lain yang sering dikutip di mana komputer kuantum diketahui memberikan keuntungan, seperti pencarian basis data, percepatan hanya polinomial.

Adakah contoh masalah yang diketahui yang dapat ditunjukkan (baik dibuktikan atau dibuktikan dengan asumsi kompleksitas komputasi yang kuat) bahwa komputer kuantum akan memberikan keuntungan eksponensial?

$f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$$s \in \{0,1\}^n$$f(x) = f(y)$$x + y = s$$s = 0$$f$$s$$f(x) = f(x + s)$$x$$2 = 0$$f$

Berapa biaya untuk setiap probabilitas keberhasilan yang ditentukan, pada komputer klasik atau kuantum, untuk membedakan fungsi acak 1-ke-1 yang seragam dari fungsi acak 2-ke-1 yang memuaskan properti ini, jika setiap opsi (1-ke -1 atau 2-ke-1) memiliki probabilitas yang sama?

$f$$f$$p$

Ini adalah skenario dari algoritma Simon . Ini memiliki aplikasi esoterik dalam kriptanalisis nonsensik , ^* dan itu adalah instrumen awal dalam mempelajari kelas kompleksitas BQP dan BPP dan inspirasi awal untuk algoritma Shor.

$O(n + |f|)$$O(n \cdot T_f(n) + G(n))$$T_f(n)$$f$$n$$G(n)$$n \times n$$\mathbb F_2$

$f$$2^{n/4}$$2^{-n/2}$

$f$

The algoritma Deutsch-Jozsa berfungsi sebagai ilustrasi yang sama untuk masalah buatan yang sedikit berbeda untuk belajar kelas kompleksitas yang berbeda, P dan EQP, mencari tahu rincian yang tersisa sebagai latihan bagi pembaca.

_{^* Simon tidak masuk akal untuk kriptanalisis karena hanya orang idiot yang tidak dapat dibayangkan yang akan memasukkan kunci rahasia mereka ke sirkuit kuantum musuh untuk digunakan pada superposisi input yang kuantum, tetapi untuk beberapa alasan itu membuat percikan setiap kali seseorang menerbitkan tulisan baru tentang penggunaan algoritma Simon untuk memecahkan kunci idiot dengan perangkat keras imajiner, yang merupakan cara semua serangan ini bekerja. Pengecualian: Mungkin saja hal ini dapat merusak kriptografi kotak putih , tetapi kisah keamanan untuk kriptografi kotak putih bahkan terhadap musuh klasik tidak menjanjikan.}

Tidak yakin apakah ini benar-benar yang Anda cari; dan saya tidak tahu bahwa saya akan memenuhi syarat ini sebagai "eksponensial" (Saya juga bukan ilmuwan komputer sehingga kemampuan saya untuk melakukan analisis algoritma kurang lebih tidak ada ...), tetapi hasil terbaru oleh Bravyi et. al mempresentasikan kelas '2D Hidden Linear Function Function' yang terbukti menggunakan lebih sedikit sumber daya pada perangkat paralel kuantum.

$N\times N$$A$$b$$q$

$\log{N}$$>7/8$

Buktinya jumlah pada keadaan grafik tertentu menjadi sulit untuk disimulasikan oleh sirkuit klasik, sub-hasil ini terbukti sedikit lebih awal . Kemudian sisa kertas menunjukkan bahwa kelas masalah yang lebih besar mengandung masalah yang sulit ini.

$\neq$

$\textbf{BPP}^O \neq \textbf{BQP}^O$ $\neq$

Sementara saya tidak dapat memberikan bukti formal, simulasi (evolusi temporal) dari sistem kuantum diyakini sebagai kasus seperti itu: Tidak ada cara yang lebih baik untuk melakukan ini pada komputer klasik daripada dalam waktu eksponensial tetapi komputer kuantum dapat sepele melakukannya dalam waktu polinomial.

Gagasan seperti simulator kuantum (lihat juga artikel wikipedia ) sebenarnya adalah bagaimana komputer kuantum pertama kali diusulkan.