Apakah ada bukti bahwa komputer kuantum lebih efisien daripada komputer klasik?

Algoritma Shor sering digunakan sebagai argumen. Ini dapat memecahkan masalah faktorisasi lebih cepat daripada algoritma yang dikenal untuk komputer klasik. Namun, kami tidak memiliki bukti bahwa komputer klasik juga tidak dapat faktor integer secara efisien.

Apakah ada komputer kuantum bukti aktual yang dapat memecahkan beberapa masalah lebih cepat daripada komputer klasik?

algorithms efficiency quantum-computing Viktor Maia
sumber

beberapa di antaranya ditangkap secara formal dalam pemisahan kelas kompleksitas terbuka seperti BPP =? BQP (klasik 1, berorientasi QM ke-2). ada juga masalah implementasi yang tidak diketahui (berbeda dengan mesin klasik) jika QM benar-benar layak secara fisik. dll ... mungkin memasak beberapa ini menjadi jawaban.

vzn

Terkait erat: Mengapa dan bagaimana komputer kuantum lebih cepat dari komputer biasa?

Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

Ya, algoritme Grover menunjukkan Anda dapat menggunakan algoritme kuantum untuk menemukan elemen dalam basis data tak berurutan dengan ukuran dengan probabilitas tinggi dengan menanyakan hanya pada basis data $N$ kali. Setiap solusi klasik yang berhasil dengan probabilitas tinggi memerlukanquery ke database. $O(\sqrt{N})$ $\Omega (N)$

Ran G.
sumber

Algoritma Deutsch – Jozsa juga layak disebut. Diberikan akses ke oracle dari fungsi boolean

, yang dikenal seragam atau konstan (dengan seragam yang kami maksudkan adalah

untuk tepat setengah dari input yang mungkin). Jelas setiap algoritma klasik akan membutuhkan setidaknya

query (dalam pengaturan deterministik). Komputer kuantum dapat memutuskan ini menggunakan satu permintaan.

f : {0, 1}^{n} \to {0, 1}

$f: \{0,1\}^n\rightarrow \left\{0,1\right\}$

0

$0$

2^{n - 1} + 1

$2^{n-1}+1$

Ariel

"menggali basis data" - Saya pikir Anda mungkin mengambil ungkapan "penggalian data" sedikit terlalu harfiah. :-)

David Richerby

@DavidRicherby sialan benar? (;

Ran G.

@ariel Saya pikir ini pantas mendapat jawaban tambahan! kenapa kamu tidak menambahkannya? (Anda juga dapat menyebutkan bahwa ini memberikan ide-ide untuk algoritma Simon yang pada gilirannya berkaitan dengan algoritma Shor)

Ran G.

"Setiap solusi klasik yang berhasil dengan probabilitas tinggi memerlukan Ω (N) query ke database" - Apakah ini benar untuk model non-kotak hitam juga? Apakah ini terbukti?

user976850

Itu tergantung apa yang Anda anggap sebagai bukti aktual, dan apa yang Anda maksud dengan "lebih cepat". Dari perspektif teori kompleksitas, jawabannya adalah tidak - kami tidak memiliki bukti seperti itu. BQP (kelas masalah yang dapat diselesaikan secara efisien oleh komputer kuantum) terkandung dalam PSPACE. Mampu membuktikan pemisahan antara BQP dan PSPACE juga akan menyiratkan pemisahan antara P dan PSPACE, yang tidak diketahui.

Perhatikan bahwa algoritma Grover hanya memberikan peningkatan kecepatan akar kuadrat, sehingga tidak ada kontradiksi.

Norbert Schuch
sumber

Selamat datang! Sayangnya, jawaban Anda tampaknya bertentangan sendiri. Anda mengatakan bahwa, "dari sudut pandang teori kompleksitas, jawabannya adalah tidak" tetapi kemudian Anda memberikan satu argumen teoretis kompleksitas bahwa jawabannya adalah "kita tidak tahu" dan yang lain mengatakan bahwa jawabannya adalah "ya". Jadi bagaimana jawabannya tidak?

David Richerby

\neq

$\ne$

Pertanyaannya menanyakan apakah ada "komputer kuantum bukti aktual dapat menyelesaikan beberapa masalah lebih cepat dari komputer klasik". Algoritma Grover terbukti lebih cepat daripada algoritma klasik mana pun, jadi jawabannya jelas "ya."

David Richerby

Algoritma @DavidRicherby Grover didasarkan pada oracle (ini adalah, kotak hitam), yang tidak Anda temui dalam masalah nyata . Setelah Anda mempertimbangkan struktur masalah dalam oracle (misalnya memverifikasi solusi untuk masalah NP-complete), itu (afaik) tidak jelas apakah percepatan berlanjut.

Norbert Schuch

Jawaban ini agak membingungkan untuk dibaca. Saya pikir ini akan membantu untuk mengedit jawaban untuk mengklarifikasi poin-poin ini dan memikirkan dengan tepat klaim apa yang Anda coba buat dan alasan apa yang dapat Anda tawarkan untuk mendukung klaim tersebut. Ada dua poin yang saya pikir akan membantu untuk memperjelas: (a) perbedaan antara speedup waktu polinomial vs speedup yang lebih besar, (b) perbedaan antara algoritma dengan oracle vs algoritma biasa. Kemudian, gunakan itu untuk menjelaskan mengapa algoritma Grover memiliki percepatan tetapi itu tidak bertentangan dengan pernyataan Anda yang lain.

-1

Anda bertanya tentang "bukti" yang mungkin terbatas pada tingkat matematika, tetapi pertanyaan dasarnya jauh lebih dalam dari itu. ahli teori akan mengakui pada dasarnya masih merupakan pertanyaan terbuka secara umum tentang kinerja relatif dari algoritma kuantum vs klasik dan mungkin tidak ada jawaban sederhana / umum, tetapi dengan beberapa konsensus ahli bahwa algoritma Shors tampaknya "luar biasa cepat dibandingkan dengan kecepatan klasik terbaik yang diharapkan . " anjak cepat di komputer klasik akan mematahkan asumsi keamanan kriptografi yang banyak dipegang seperti sistem RSA .

beberapa di antaranya ditangkap secara formal dalam pertanyaan kelas kompleksitas terbuka BPP =? Pertanyaan BQP . ini adalah kelas analog dan klasik yang analog dan pemisahannya tidak diketahui dan merupakan area penelitian yang aktif.
pertanyaan yang berkaitan erat adalah apakah komputer QM secara fisik dapat dibangun yang sesuai dengan spesifikasi teoretis dan beberapa / minoritas ilmuwan (alias "skeptis") berargumen bahwa mungkin ada suara atau hukum penskalaan yang mencegah penskalaan QM seperti yang dibayangkan dalam teori. dalam arti tertentu "bukti" kecepatan komputer QM harus berupa implementasi fisik. (Ini mirip dengan cara tesis Church-Turing teoretis tetapi tampaknya pada akhirnya mengikat ke dalam penegasan tentang implementasi fisik.) beberapa peneliti berbicara tentang analog Church-Turing dalam komputasi QM. lihat misalnya tesis Church Turing dalam dunia kuantum oleh Montanaro.
yang relevan dengan / menimpa pertanyaan / debat ini adalah upaya substansial / "panas" (ilmiah) untuk membandingkan komputer kuantum "terbesar" dunia saat ini oleh DWave. ini adalah topik besar dengan banyak materi terkait, tetapi untuk tinjauan yang relatif baru coba studi benchmark S-D-Wave yang menunjukkan komputer kuantum lamban / Register

vzn
sumber