Apa tingkat "kepercayaan" dari hasil dari komputer kuantum yang mungkin?

Pada tingkat yang sangat dasar, membaca atau mengukur qubit memaksanya berada dalam satu keadaan atau yang lain, sehingga pengoperasian komputer kuantum untuk mendapatkan hasil membuat keadaan runtuh menjadi satu dari banyak kemungkinan.

Tetapi karena keadaan masing-masing qubit adalah probabilistik, pasti ini berarti hasilnya sebenarnya bisa berupa salah satu dari kemungkinan itu, dengan berbagai kemungkinan. Jika saya menjalankan kembali program - haruskah saya berharap melihat hasil yang berbeda?

Bagaimana saya bisa yakin bahwa saya memiliki hasil "terbaik"? Apa yang memberikan kepercayaan diri itu? Saya menganggap itu tidak bisa pengukuran sementara seperti yang dijelaskan dalam pertanyaan ini karena mereka tidak menciutkan output.

Mayoritas algoritma ¹ berguna / relatif efisien untuk komputer kuantum termasuk dalam kelas kompleksitas 'bounded-error quantum polynomial time' (BQP) . Dengan definisi ini, Anda ingin 'tingkat kegagalan' dari setiap algoritma kuantum menjadi , atauP(sukses)≥$\leq\frac{1}{3}$ , meskipun hasilnya mungkin masih dalam beberapa kesalahan kecil. Algoritma non-probabilistik (yang dapat berjalan dalam waktu polinomial) masih akan berada di kelas kompleksitas ini, dengan satu-satunya perbedaan adalah bahwa iaselalumengembalikan hasil yang benar².$\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$

Namun, karena Anda dapat menjalankan algoritme beberapa kali secara sewenang-wenang, ini setara dengan memiliki probabilitas keberhasilan minimal untuk input panjangndan konstanta positifc.$\frac{1}{2} + n^{-c}$$n$$c$

Jadi, hasil 'benar' adalah yang muncul setidaknya dua pertiga dari waktu, kecuali jika Anda ingin perhitungan 'satu-tembakan' seperti jika Anda ingin menghasilkan angka acak, atau jika Anda ingin melakukan sesuatu seperti benchmark chip kuantum, di mana statistik penting dan merupakan bagian dari 'hasil'.

Selain dari ini (atau algoritma lain yang tidak memiliki 'hasil yang benar' tunggal), jika Anda menemukan algoritma dengan tingkat keberhasilan di bawah setengah, itu tidak lagi 'kesalahan terikat' dan itu tidak mungkin bagi pengguna untuk mengetahui hasil yang benar - mungkin hanya ada jawaban yang salah dengan kemungkinan lebih tinggi terjadi daripada yang benar.

Ya, Anda dapat melihat hasil yang berbeda setiap kali Anda menjalankan perhitungan. Kepercayaan pada hasil disediakan oleh:

1. Algoritma kuantum itu sendiri memastikan bahwa hasil yang benar terjadi dengan probabilitas tinggi dan;
2. Mengulangi algoritma beberapa kali untuk menemukan hasil yang paling mungkin.

^{1 Di sini, algoritma yang dapat dihitung dalam waktu polinomial untuk memberikan solusi dengan 'probabilitas tinggi', meskipun untuk keperluan jawaban ini, kompleksitas waktu kurang penting}

^{2 Yah, setidaknya secara idealis}

Menguraikan sedikit tentang Mithrandir24601respons -

Fitur yang Anda khawatirkan, bahwa komputer kuantum dapat menghasilkan jawaban berbeda pada proses komputasi berikutnya, juga merupakan fitur komputasi acak. Dalam beberapa hal baik untuk dapat memperoleh satu jawaban berulang, tetapi pada akhirnya cukup untuk mendapatkan jawaban yang benar dengan kepercayaan yang cukup tinggi. Seperti halnya algoritma acak, yang penting adalah Anda bisa yakin akan peluang mendapatkan jawaban yang benar dalam setiap perhitungan yang dijalankan.

Misalnya, komputer kuantum Anda mungkin memberi Anda jawaban yang benar untuk pertanyaan YA / TIDAK dua kali dari setiap tiga. Ini mungkin terlihat seperti kinerja yang buruk, tetapi apa artinya ini adalah jika Anda menjalankannya berkali-kali, Anda dapat mengambil jawaban mayoritas dan sangat yakin bahwa aturan mayoritas memberi Anda jawaban yang benar. (Hal yang sama berlaku untuk perhitungan acak secara normal juga.) Cara kepercayaan meningkat dengan jumlah rune, berarti selama salah satu run memberikan jawaban yang secara signifikan lebih dari sekadar peluang 50% untuk menjadi benar, Anda dapat membuat kepercayaan diri Anda setinggi yang Anda suka hanya dengan melakukan sejumlah kecil proses berulang (meskipun diperlukan lebih banyak proses, semakin dekat peluang jawaban yang benar dalam satu kali proses mencapai 50%).

$\mathrm{poly}(n)$$n$

Untuk masalah yang memiliki jawaban yang lebih rumit daripada pertanyaan YA / TIDAK, kami tidak dapat berasumsi bahwa jawaban yang sama akan dihasilkan lebih dari satu kali sehingga kami dapat mengambil suara mayoritas. (Jika Anda menggunakan komputer kuantum untuk mengambil sampel dari sejumlah hasil eksponensial, ada kemungkinan bahwa ada beberapa jumlah jawaban yang lebih kecil tetapi masih secara eksponensial benar dan berguna!) Misalkan Anda mencoba menyelesaikan masalah pengoptimalan: mungkin tidak mudah untuk memverifikasi bahwa Anda telah menemukan solusi optimal, atau solusi yang hampir optimal - atau bahwa jawaban yang Anda dapatkan adalah yang terbaik yang dapat dilakukan komputer kuantum (bagaimana jika proses selanjutnya memberi Anda jawaban yang lebih baik secara kebetulan?). Dalam hal ini, yang penting adalah menentukan apa yang Anda ketahui tentang masalahnya,NP , artinya pada prinsipnya Anda dapat memeriksa jawaban yang Anda berikan secara efisien?), Dan kualitas solusi apa yang Anda sukai.

Sekali lagi, ini semua benar untuk algoritma acak juga - perbedaannya adalah kita berharap komputer kuantum dapat menyelesaikan masalah yang tidak dapat diselesaikan dengan mudah oleh komputer acak.

$15$$3\times5$

Ini adalah baris yang bagus terutama dengan ketukan yang tepat waktu dari Aaronson, dan para penonton sepertinya selalu terkekeh setidaknya sedikit, tetapi tentu saja kita semua tahu bahwa itu adalah penyederhanaan kecil dari sifat probabilistik dari algoritma Shor.

$15$$3$$15$$5$$15=3\times 5$

$\mathsf{FACTORING}$$\mathrm{BQP}\cap\mathrm{NP}$$\mathrm{BQP}$

$\mathrm{BQP}$$\mathrm{NP}$

(Saya tahu bahwa sudah ada dua jawaban hebat; namun, pertanyaannya memungkinkan eksposisi / klarifikasi atas kutipan / anectdote Aaronson.)