Untuk pertanyaan tentang analisis kompleksitas algoritma kuantum dan perbandingan dengan kompleksitas algoritma klasik.
Komputer kuantum diketahui mampu memecahkan dalam waktu polinomial berbagai algoritma kriptografi yang sebelumnya dianggap hanya dapat dipecahkan oleh sumber daya yang meningkat secara eksponensial dengan ukuran bit kunci. Contoh untuk itu adalah algoritma Shor . Tapi, sejauh yang saya tahu, tidak...
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...
Algoritma pencarian Grover menyediakan kecepatan kuadratik yang dapat dibuktikan untuk pencarian basis data yang tidak disortir. Algoritma biasanya diekspresikan oleh rangkaian kuantum berikut: Dalam sebagian besar representasi, bagian penting dari protokol adalah "gerbang oracle" UωUωU_\omega ,...
Posting blog ini oleh Scott Aaronson adalah penjelasan yang sangat berguna dan sederhana tentang algoritma Shor . Saya ingin tahu apakah ada penjelasan seperti itu untuk algoritma kuantum kedua yang paling terkenal: Algoritma Grover untuk mencari basis data ukuran tidak berurutan dalam waktu .O (...
Akun populer-berita standar komputasi kuantum adalah bahwa komputer kuantum (QC) akan bekerja dengan memecah secara eksponensial banyak salinan paralel yang tidak berinteraksi dengan dirinya sendiri di alam semesta yang berbeda dan memiliki masing-masing upaya untuk memverifikasi sertifikat yang...
Apakah ada pernyataan umum tentang jenis masalah apa yang dapat diselesaikan secara lebih efisien menggunakan komputer kuantum (hanya model gerbang kuantum)? Apakah masalah yang diketahui algoritma saat ini memiliki properti yang sama? Sejauh yang saya mengerti komputasi kuantum membantu masalah...
Banyak makalah menyatakan bahwa simulasi Hamiltonian adalah BQP-lengkap (misalnya, simulasi Hamiltonian dengan ketergantungan hampir optimal pada semua parameter dan Simulasi Hamiltonian oleh Qubitisasi ). Sangat mudah untuk melihat bahwa simulasi Hamiltonian adalah BQP-keras karena setiap...
Di permukaan, algoritma kuantum tidak ada hubungannya dengan komputasi klasik dan P vs NP khususnya: Memecahkan masalah dari NP dengan komputer kuantum tidak memberi tahu kita apa-apa tentang hubungan kelas kompleksitas klasik 1 ini . Di sisi lain, 'deskripsi alternatif' dari kelas kompleksitas...
Komputer kuantum dapat secara efisien menyelesaikan masalah yang ada di BQP kelas kompleksitas . Saya telah melihat klaim yang dapat (berpotensi, karena kita tidak tahu apakah BQP adalah himpunan bagian yang tepat atau sama dengan PP) meningkatkan efisiensi komputer kuantum dengan menerapkan pasca...
Sebagai hasil dari jawaban yang bagus untuk pertanyaan saya tentang bogosort kuantum , saya bertanya-tanya bagaimana keadaan terkini dalam algoritma kuantum untuk pengurutan. Lebih tepatnya, penyortiran di sini didefinisikan sebagai masalah berikut: Diberikan array SEBUAHSEBUAHA dari bilangan...
Saya bingung tentang algoritma Grover dan hubungannya dengan kelas kompleksitas. Algoritma Grover menemukan dan elemen dalam database N = 2 n (sedemikian sehingga f ( k ) = 1 ) elemen dengan ∼ √kkkN=2nN=2nN=2^nf(k)=1f(k)=1f(k)=1 panggilan ke oracle.∼N−−√=2n/2∼N=2n/2\sim \sqrt{N}=2^{n/2} Jadi...
Seperti namanya, pertanyaan ini merupakan tindak lanjut dari pertanyaan ini . Saya senang dengan kualitas jawaban, tetapi saya merasa akan sangat menarik jika wawasan tentang teknik optimasi dan perkiraan ditambahkan, tetapi mungkin jatuh di luar topik, maka pertanyaan ini. Dari jawaban Blue:...
Saya ingin tahu kompleksitas waktu apa yang dianggap efisien / tidak efisien untuk komputer kuantum. Untuk ini, saya perlu tahu berapa banyak operasi yang dapat dilakukan komputer kuantum per detik. Adakah yang bisa memberi tahu saya cara menghitungnya dan faktor apa yang bergantung padanya (detail...
Apakah ada suite enkripsi yang dapat diretas oleh komputer biasa atau komputer super, tetapi tidak komputer kuantum? Jika itu mungkin, asumsi apa yang akan bergantung padanya? (Memfaktorkan angka besar, Sebuahb( modd)ab(modd)a^b\pmod d Sebuahc( modd)Sebuahc(modd)a^c\pmod d Sebuahb c(...
Saya ingin belajar lebih banyak tentang kelas kompleksitas komputasi dalam konteks komputasi kuantum. Media tidak begitu penting; bisa berupa buku, catatan kuliah online atau sejenisnya. Yang paling penting adalah isinya. Materi tersebut harus mencakup dasar-dasar kelas kompleksitas komputasi...
Saya melihat catatan kuliah ini di mana penulis memberikan pemisahan oracle antara dan . Dia mengisyaratkan bagaimana "teknik diagonalisasi standar dapat digunakan untuk membuat ini ketat".BQPBQP\mathsf{BQP}NPNP\mathsf{NP} Bisakah seseorang merinci teknik diagonalisasi yang seharusnya digunakan?...
Kelas kompleksitas BQP (waktu polinomial kuantum kesalahan-terbatas) tampaknya hanya ditentukan dengan mempertimbangkan faktor waktu. Apakah ini selalu berarti? Apakah ada algoritma di mana waktu komputasi menskala secara polinomi dengan ukuran input tetapi sumber daya lain seperti skala memori...
Baru-baru ini, saya telah membaca tentang 'bogosort kuantum' di beberapa wiki. Ide dasarnya adalah, bahwa seperti bogosort, kami hanya mengocok array kami dan berharap itu diurutkan 'secara tidak sengaja' dan coba lagi pada kegagalan. Perbedaannya adalah bahwa sekarang, kita memiliki ' quantum...
Nomor Allah adalah kasus terburuk dari algoritma Allah yang gagasan yang berasal dari diskusi tentang cara-cara untuk memecahkan teka-teki Rubik's Cube, tetapi yang juga dapat diterapkan pada teka-teki kombinasi dan permainan matematika lainnya. Ini merujuk pada algoritma apa pun yang...
Saya memiliki beberapa kebingungan mengenai konsep estimasi fase: menurut definisi, diberikan operator kesatuan dan vektor eigen dengan nilai eigen terkait , estimasi fase memungkinkan untuk menemukan nilai . Ini berarti bahwa saya akan dapat menentukan nilai eigen dari matriks tertentu mengingat...