Mengukur Kecepatan Grover Di Luar Analisis Asimptotik

Diterbitkan Ulang Oleh Plato

Followers: 0

Chris Cade^1,2, Marten Folkertsma³, Ido Niesen^1,2, dan Jordi Weggemans³

¹QuSoft & Universitas Amsterdam (UvA), Amsterdam, Belanda
²Fermioniq, Amsterdam, Belanda
³QuSoft & CWI, Amsterdam, Belanda

Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.

Abstrak

Waktu proses algoritma kuantum sering kali dipelajari melalui analisis kasus terburuk yang asimtotik. Meskipun berguna, perbandingan seperti itu sering kali gagal: tidak jarang algoritma dengan run-time kasus terburuk yang besar pada akhirnya memberikan kinerja yang baik pada kasus-kasus yang memiliki kepentingan praktis. Untuk mengatasi hal ini, perlu dilakukan analisis run-time yang bersifat lebih empiris, yang untuk ukuran masukan yang cukup kecil dapat dilakukan pada perangkat kuantum atau simulasinya. Untuk ukuran masukan yang lebih besar, diperlukan pendekatan alternatif.
Dalam makalah ini kami mempertimbangkan pendekatan yang menggabungkan emulasi klasik dengan batasan kompleksitas terperinci yang mencakup semua konstanta. Kami mensimulasikan algoritma kuantum dengan menjalankan versi klasik dari sub-rutin, sekaligus mengumpulkan informasi tentang run-time dari rutinitas kuantum jika dijalankan. Untuk melakukan hal ini secara akurat dan efisien untuk ukuran masukan yang sangat besar, kami menjelaskan prosedur estimasi dan membuktikan bahwa prosedur tersebut memperoleh batas atas kompleksitas algoritma kuantum yang diharapkan.
Kami menerapkan metode kami pada beberapa percepatan kuantum sederhana dari algoritma heuristik klasik untuk memecahkan masalah optimasi MAX-$k$-SAT yang telah dipelajari dengan baik. Hal ini memerlukan batasan yang ketat (termasuk semua konstanta) pada kompleksitas yang diperkirakan dan dalam kasus terburuk dari dua sub-rutin kuantum penting: pencarian Grover dengan jumlah item yang ditandai yang tidak diketahui jumlahnya, dan penemuan maksimum kuantum. Hal ini meningkatkan hasil yang sudah ada dan mungkin dapat memberikan manfaat yang lebih luas.
Di antara hasil lainnya, kami menemukan bahwa algoritme heuristik klasik yang kami pelajari tidak menawarkan percepatan kuantum yang signifikan meskipun terdapat percepatan teoritis per langkah. Hal ini menunjukkan bahwa analisis empiris seperti yang kami terapkan dalam makalah ini sudah menghasilkan wawasan yang melampaui apa yang dapat dilihat hanya dengan analisis asimtotik saja.

Mengukur percepatan Grover di luar analisis asimtotik PlatoBlockchain Data Intelligence. Pencarian Vertikal. Ai.

Gambar unggulan: Hasil numerik untuk kueri dihitung pada instance max-k-sat yang dihasilkan secara acak, dengan n variabel dan klausa berbobot m = rn (acak seragam antara 0 dan 1), dari algoritme klasik dan kuantum yang diusulkan yang mengimplementasikan penelusuran pendaki bukit rutin.

[Embedded content]

Ringkasan populer

Waktu proses algoritma kuantum sering kali dipelajari melalui analisis kasus terburuk yang ketat. Meskipun berguna, perbandingan seperti itu sering kali gagal: tidak jarang algoritma dengan run-time kasus terburuk yang besar pada akhirnya memberikan kinerja yang baik pada kasus-kasus yang memiliki kepentingan praktis. Untuk ukuran masukan yang cukup kecil, simulasi (rangkaian) kuantum langsung dapat dilakukan pada perangkat kuantum atau simulasinya. Namun, untuk menyelidiki bagaimana kinerja algoritma tersebut untuk input kepentingan praktis yang lebih besar, diperlukan pendekatan alternatif.

Dalam makalah ini kami mempertimbangkan pendekatan yang menggabungkan emulasi klasik dengan batasan kompleksitas yang terperinci. Kami 'mensimulasikan' algoritma kuantum secara tidak langsung: dengan menjalankan versi klasik dari sub-rutin, sekaligus mengumpulkan informasi tentang run-time dari rutinitas kuantum jika dijalankan. Pendekatan ini memiliki keuntungan yaitu (1) tidak terbatas pada ukuran masalah yang kecil, dan (2) menyediakan sarana untuk memperkirakan waktu proses algoritma kuantum yang bergantung pada masukan (batas atas), sehingga memungkinkan dilakukannya perbandingan kinerja algoritma kuantum. dan algoritma klasik pada input tertentu yang diminati.

Kami menerapkan metode kami pada beberapa percepatan kuantum sederhana dari algoritma heuristik klasik untuk memecahkan masalah optimasi MAX-k-SAT yang telah dipelajari dengan baik. Di antara hasil lainnya, kami menemukan bahwa algoritme heuristik yang kami pelajari tidak menawarkan percepatan kuantum yang signifikan meskipun terdapat percepatan teoretis. Hal ini menunjukkan bahwa analisis empiris telah menghasilkan wawasan yang melampaui apa yang dapat dilihat melalui analisis kasus terburuk saja.

► data BibTeX

@article{Cade2023quantifyinggrover, doi = {10.22331/q-2023-10-10-1133}, url = {https://doi.org/10.22331/q-2023-10-10-1133}, title = {Mengukur { Kecepatan G}rover melampaui analisis asimtotik}, penulis = {Cade, Chris and Folkertsma, Marten dan Niesen, Ido dan Weggemans, Jordi}, journal = {{Quantum}}, issn = {2521-327X}, penerbit = { {Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, halaman = {1133}, bulan = oktober, tahun = {2023} }

► Referensi

[1] Ashish Ahuja dan Sanjiv Kapoor. Algoritma kuantum untuk menemukan nilai maksimum. arXiv:quant-ph/9911082, 1999. https://doi.org/10.48550/arXiv.quant-ph/9911082.
https:///doi.org/10.48550/arXiv.quant-ph/9911082
arXiv: quant-ph / 9911082

[2] Haifa Hamad Alkasem dan Mohamed El Bachir Menai. Pencarian lokal stokastik untuk MAX-SAT parsial: evaluasi eksperimental. Tinjauan Kecerdasan Buatan, 54:2525–2566, 2021. https://doi.org/10.1007/s10462-020-09908-4.
https://doi.org/10.1007/s10462-020-09908-4

[3] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, dan Hartmut Neven. Fokus melampaui percepatan kuadratik untuk mendapatkan keuntungan kuantum yang terkoreksi kesalahan. PRX Quantum, 2(1):010103, 2021. https://doi.org/10.1103/PRXQuantum.2.010103.
https: / / doi.org/ 10.1103 / PRXQuantum.2.010103

[4] Shai Ben-David, Benny Chor, Oded Goldreich, dan Michel Luby. Tentang teori kompleksitas kasus rata-rata. Jurnal Ilmu Komputer dan Sistem, 44(2):193–219, 1992. https://doi.org/10.1016/0022-0000(92)90019-F.
https://doi.org/10.1016/0022-0000(92)90019-F

[5] Benjamin Bichsel, Maximilian Baader, Timon Gehr, dan Martin Vechev. Silq: Bahasa kuantum tingkat tinggi dengan komputasi yang aman dan semantik intuitif. Dalam Konferensi ACM SIGPLAN tentang Desain dan Implementasi Bahasa Pemrograman, halaman 286–300, 2020. https://doi.org/10.5281/zenodo.3764961.
https: / / doi.org/ 10.5281 / zenodo.3764961

[6] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, dan Etienne Lefebvre. Perkembangan komunitas yang cepat dalam jaringan besar. Jurnal Mekanika Statistik: Teori dan Eksperimen, 2008:P10008, Oktober 2008. https://doi.org/10.1088/1742-5468/2008/10/P10008.
https://doi.org/10.1088/1742-5468/2008/10/P10008

[7] Michel Boyer, Gilles Brassard, Peter Høyer, dan Alain Tapp. Batasan ketat pada pencarian kuantum. Fortschritte der Physik: Kemajuan Fisika, 46(4-5):493–505, 1998. https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5 <493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P

[8] Chris Cade, Marten Folkertsma, Ido Niesen, dan Jordi Weggemans. Algoritme kuantum untuk deteksi komunitas dan waktu proses empirisnya. arXiv:2203.06208, 2022. https:///doi.org/10.48550/arXiv.2203.06208.
https:///doi.org/10.48550/arXiv.2203.06208
arXiv: 2203.06208

[9] Chris Cade, Lana Mineh, Ashley Montanaro, dan Stasja Stanisic. Strategi untuk memecahkan model Fermi-Hubbard pada komputer kuantum jangka pendek. Tinjauan Fisik B, 102(23):235122, 2020. https://doi.org/10.1103/PhysRevB.102.235122.
https:///doi.org/10.1103/PhysRevB.102.235122

[10] Shaowei Cai, Chuan Luo, dan Haochen Zhang. Dari penipisan hingga pencarian lokal dan sebaliknya: Pendekatan baru untuk MAX-SAT. Dalam IJCAI, halaman 571–577, 2017. https://doi.org/10.24963/ijcai.2017/80.
https:///doi.org/10.24963/ijcai.2017/80

[11] Earl Campbell, Ankur Khurana, dan Ashley Montanaro. Menerapkan algoritma kuantum untuk membatasi masalah kepuasan. Quantum, 3:167, 2019. https:///doi.org/10.22331/q-2019-07-18-167.
https://doi.org/10.22331/q-2019-07-18-167

[12] Pierre-Luc Dallaire-Demers, Jonathan Romero, Libor Veis, Sukin Sim, dan Alán Aspuru-Guzik. Ansatz sirkuit kedalaman rendah untuk mempersiapkan keadaan fermionik berkorelasi pada komputer kuantum. Sains dan Teknologi Quantum, 4(4):045005, 2019. https://doi.org/10.1088/2058-9565/ab3951.
https: / / doi.org/ 10.1088 / 2058-9565 / ab3951

[13] Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, dan Alessandro Provetti. Metode louvain yang digeneralisasi untuk deteksi komunitas di jaringan besar. Pada konferensi internasional ke-2011 tahun 11 tentang desain dan aplikasi sistem cerdas, halaman 88–93. IEEE, 2011.https:///doi.org/10.1109/ISDA.2011.6121636.
https:///doi.org/10.1109/ISDA.2011.6121636

[14] Christoph Durr dan Peter Hoyer. Algoritma kuantum untuk mencari nilai minimum. arXiv:quant-ph/9607014, 1996. https://doi.org/10.48550/arXiv.quant-ph/9607014.
https:///doi.org/10.48550/arXiv.quant-ph/9607014
arXiv: quant-ph / 9607014

[15] Andrew Hancock, Austin Garcia, Jacob Shedenhelm, Jordan Cowen, dan Calista Carey. Cirq: Kerangka kerja python untuk membuat, mengedit, dan menjalankan sirkuit kuantum. URL https:///github.com/quantumlib/Cirq, 2019.
https: / / github.com/ quantumlib / Cirq

[16] Peter Hoyer. Fase sewenang-wenang dalam amplifikasi amplitudo kuantum. Tinjauan Fisik A, 62(5):052304, 2000. https://doi.org/10.1103/PhysRevA.62.052304.
https: / / doi.org/ 10.1103 / PhysRevA.62.052304

[17] Richard M Karp dan J Michael Steele. Analisis probabilistik heuristik. Masalah penjual keliling, halaman 181–205, 1985.

[18] Joonho Lee, Dominic W Berry, Craig Gidney, William J Huggins, Jarrod R McClean, Nathan Wiebe, dan Ryan Babbush. Perhitungan kimia kuantum yang lebih efisien melalui hiperkontraksi tensor. PRX Quantum, 2(3):030305, 2021. https://doi.org/10.1103/PRXQuantum.2.030305.
https: / / doi.org/ 10.1103 / PRXQuantum.2.030305

[19] Ashley Montanaro. Percepatan berjalan kuantum dari algoritma penelusuran mundur. Teori Komputasi, 14(15):1–24, 2018. http://dx.doi.org/10.4086/toc.2018.v014a015.
https: / / doi.org/ 10.4086 / toc.2018.v014a015

[20] Xinyu Que, Fabio Checconi, Fabrizio Petrini, dan John A Gunnels. Deteksi komunitas yang skalabel dengan algoritma louvain. Pada Simposium Pemrosesan Paralel dan Terdistribusi Internasional IEEE 2015, halaman 28–37. IEEE, 2015.https:///doi.org/10.1109/IPDPS.2015.59.
https:///doi.org/10.1109/IPDPS.2015.59

[21] Maria Schuld dan Nathan Killoran. Apakah keunggulan kuantum merupakan tujuan yang tepat untuk pembelajaran mesin kuantum? Prx Quantum, 3(3):030101, 2022. https://doi.org/10.1103/PRXQuantum.3.030101.
https: / / doi.org/ 10.1103 / PRXQuantum.3.030101

[22] Daniel A Spielman dan Shang-Hua Teng. Analisis yang diperhalus: upaya untuk menjelaskan perilaku algoritma dalam praktiknya. Komunikasi ACM, 52(10):76–84, 2009. https://doi.org/10.1145/1562764.1562785.
https: / / doi.org/ 10.1145 / 1562764.1562785

[23] Damian S Steiger, Thomas Häner, dan Matthias Troyer. ProjectQ: kerangka perangkat lunak sumber terbuka untuk komputasi kuantum. Quantum, 2:49, 2018. https:///doi.org/10.22331/q-2018-01-31-49.
https://doi.org/10.22331/q-2018-01-31-49

[24] EM Stoudenmire dan Xavier Waintal. Algoritme Grover tidak menawarkan keunggulan kuantum. arXiv:2303.11317, 2023. https:///doi.org/10.48550/arXiv.2303.11317.
https:///doi.org/10.48550/arXiv.2303.11317
arXiv: 2303.11317

[25] Thomas Stützle, Holger H. Hoos, dan Andrea Roli. Tinjauan literatur tentang algoritma pencarian lokal untuk MAX-SAT. 2001.

[26] Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, dan Martin Roetteler. Q# memungkinkan komputasi dan pengembangan kuantum yang skalabel dengan DSL tingkat tinggi. Dalam Prosiding Lokakarya Bahasa Tertentu Domain Dunia Nyata 2018, halaman 1–10, 2018. https://doi.org/10.1145/3183895.3183901.
https: / / doi.org/ 10.1145 / 3183895.3183901

[27] VA Traag, L. Waltman, dan NJ van Eck. Dari Louvain hingga Leiden: menjamin komunitas yang terhubung dengan baik. Laporan Ilmiah, 9:5233, Maret 2019. https:///doi.org/10.1038/s41598-019-41695-z.
https: / / doi.org/ 10.1038 / s41598-019-41695-z

[28] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S Steiger, Markus Reiher, Martin Roetteler, dan Matthias Troyer. Komputasi kuantum meningkatkan katalisis komputasi. Penelitian Tinjauan Fisik, 3(3):033055, 2021. https://doi.org/10.1103/PhysRevResearch.3.033055.
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033055

[29] Dave Wecker, Matthew B Hastings, dan Matthias Troyer. Kemajuan menuju algoritma variasi kuantum praktis. Tinjauan Fisik A, 92(4):042303, 2015. https://doi.org/10.1103/PhysRevA.92.042303.
https: / / doi.org/ 10.1103 / PhysRevA.92.042303

[30] Jordi R Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, dan Florian Speelman. Memecahkan pengelompokan korelasi dengan QAOA dan sistem qudit Rydberg: pendekatan full-stack. Quantum, 6:687, 2022. https://doi.org/10.22331/q-2022-04-13-687.
https://doi.org/10.22331/q-2022-04-13-687

[31] James D Whitfield, Jacob Biamonte, dan Alán Aspuru-Guzik. Estimasi sumber daya komputasi kuantum dari simulasi energi molekul. Sains, 309:1704, 2005.

[32] Robert Wille, Rod Van Meter, dan Yehuda Naveh. Rantai alat Qiskit IBM: Bekerja dengan dan mengembangkan komputer kuantum nyata. Pada Konferensi & Pameran Desain, Otomasi & Pengujian di Eropa 2019, halaman 1234–1240. IEEE, 2019.https:///doi.org/10.23919/DATE.2019.8715261.
https: / / doi.org/ 10.23919 / DATE.2019.8715261

[33] Margaret Wright. Revolusi titik dalam dalam optimalisasi: sejarah, perkembangan terkini, dan konsekuensi jangka panjang. Buletin masyarakat matematika Amerika, 42(1):39–56, 2005. https://doi.org/10.1090/S0273-0979-04-01040-7.
https://doi.org/10.1090/S0273-0979-04-01040-7

[34] Christof Zalka. Pencarian kuantum berbasis Grover dengan urutan optimal untuk elemen bertanda yang jumlahnya tidak diketahui. arXiv:quant-ph/9902049, 1999. https://doi.org/10.48550/arXiv.quant-ph/9902049.
https:///doi.org/10.48550/arXiv.quant-ph/9902049
arXiv: quant-ph / 9902049

[35] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, dan Mikhail D Lukin. Algoritme pengoptimalan perkiraan kuantum: Performa, mekanisme, dan implementasi pada perangkat jangka pendek. Tinjauan Fisik X, 10(2):021067, 2020. https://doi.org/10.1103/PhysRevX.10.021067.
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

Dikutip oleh

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, dan Fernando GSL Brandão, “Algoritme kuantum: Survei aplikasi dan kompleksitas ujung ke ujung”, arXiv: 2310.03011, (2023).

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2023-10-11 04:09:45). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.

On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2023-10-11 04:09:44).

Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.

Konten Bertenaga SEO & Distribusi PR. Dapatkan Amplifikasi Hari Ini.
PlatoData.Jaringan Vertikal Generatif Ai. Berdayakan Diri Anda. Akses Di Sini.
PlatoAiStream. Intelijen Web3. Pengetahuan Diperkuat. Akses Di Sini.
PlatoESG. Karbon, teknologi bersih, energi, Lingkungan Hidup, Tenaga surya, Penanganan limbah. Akses Di Sini.
PlatoHealth. Kecerdasan Uji Coba Biotek dan Klinis. Akses Di Sini.
Sumber: https://quantum-journal.org/papers/q-2023-10-10-1133/

Stempel Waktu: Oktober 10, 2023

Stempel Waktu: Jan 3, 2023

Mengukur percepatan Grover di luar analisis asimtotik

Diterbitkan Ulang Oleh Plato

Abstrak

Ringkasan populer

► data BibTeX

► Referensi

Dikutip oleh

Lebih dari Jurnal Kuantum

Persiapan Keadaan Termal melalui Janji Pembulatan

Pengkodean informasi optimal kuantum menggunakan optik linier pasif yang berisik

Arsitektur modular untuk secara deterministik menghasilkan status grafik

Mengukur EPR: teori sumber daya nonklasikalitas kumpulan penyebab umum

Meningkatkan kriptografi yang tidak bergantung pada perangkat dengan nonlokalitas tripartit

Batas Kecepatan Kuantum Operator Geometrik, Aliran Hamiltonian Wegner, dan Pertumbuhan Operator

Teori sumber daya ketajaman pengukuran yang lengkap dan operasional

Arsitektur toleransi kerugian untuk komputasi kuantum dengan pemancar kuantum

Berat minimum yang dikorelasikan dengan pipa sangat cocok dengan kode permukaan

Keterikatan fotonik dengan cahaya yang dipercepat

Batas Bawah Kompleksitas Sampel yang Disempurnakan untuk (Fidelity) Quantum State Tomography

Tentang Kami

Pencarian Vertikal & Ai

Platform

Tetap Berhubung

Akun