Mempercepat Algoritma Kuantum Dengan Prakomputasi

Diterbitkan Ulang Oleh Plato

Followers: 0

Mempercepat Algoritma Kuantum dengan Prakomputasi PlatoBlockchain Data Intelligence. Pencarian Vertikal. Ai.

William J. Huggins dan Jarrod R. McClean

Google Quantum AI, Venesia, CA, AS

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

Abstrak

Penerapan komputasi di dunia nyata bisa sangat sensitif terhadap waktu. Akan sangat bermanfaat jika kita dapat mempercepat tugas-tugas tersebut dengan melakukan beberapa pekerjaan lebih awal. Termotivasi oleh hal ini, kami mengusulkan model biaya untuk algoritma kuantum yang memungkinkan prakomputasi kuantum; yaitu, untuk sejumlah komputasi “bebas” dalam jumlah polinomial sebelum masukan ke suatu algoritma ditentukan sepenuhnya, dan metode untuk memanfaatkannya. Kami menganalisis dua kelompok kesatuan yang secara asimtotik lebih efisien untuk diterapkan dalam model biaya ini dibandingkan model biaya standar. Contoh pertama dari prakomputasi kuantum, berdasarkan eksponensial matriks kepadatan, dapat menawarkan keuntungan eksponensial dalam kondisi tertentu. Contoh kedua menggunakan varian teleportasi gerbang untuk mencapai keunggulan kuadrat jika dibandingkan dengan penerapan kesatuan secara langsung. Contoh-contoh ini mengisyaratkan bahwa prakomputasi kuantum mungkin menawarkan arena baru untuk mencari keuntungan kuantum.

► data BibTeX

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, title = {Mempercepat { Q}uantum {A}lgoritma dengan {P}recomputation}, penulis = {Huggins, William J. dan McClean, Jarrod R.}, jurnal = {{Quantum}}, issn = {2521-327X}, penerbit = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, halaman = {1264}, bulan = feb, tahun = {2024} }

► Referensi

[1] S Aaronson. Keterbatasan saran kuantum dan komunikasi satu arah. Dalam Prosiding. Konferensi Tahunan IEEE ke-19 tentang Kompleksitas Komputasi, 2004, halaman 320–332. IEEE, 2004. ISBN 9780769521206/ccc.10.1109.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson dan Andris Ambainis. hubungan. Dalam Prosiding simposium ACM tahunan ke empat puluh tujuh tentang Teori Komputasi, STOC '15, halaman 307–316, New York, NY, AS, 14 Juni 2015. ACM. ISBN 9781450335362/10.1145.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson dan Guy N Rothblum. Pengukuran halus status kuantum dan privasi diferensial. 18 April 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] 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. Kuantum PRX, 2 (1): 010103, 29 Maret 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein dan Tanja Lange. Retakan tidak seragam pada beton: Kekuatan perhitungan awal bebas. Dalam Kemajuan Kriptologi – ASIACRYPT 2013, Catatan kuliah ilmu komputer, halaman 321–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/978-3-642-42045-0_17.
https://doi.org/10.1007/978-3-642-42045-0_17

[6] Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean, dan Ryan Babbush. Qubitisasi kimia kuantum berbasis arbitrer memanfaatkan ketersebaran dan faktorisasi peringkat rendah. 6 Februari 2019. URL https:///doi.org/10.22331/q-2019-12-02-208.
https://doi.org/10.22331/q-2019-12-02-208

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, dan Seth Lloyd. Pembelajaran mesin kuantum. Alam, 549 (7671): 195–202, September 2017. ISSN 0028-0836,1476-4687. 10.1038/alam23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergey Bravyi dan Alexei Kitaev. Komputasi kuantum universal dengan gerbang clifford yang ideal dan ancillas yang berisik. Fis. Pdt. A, 71 (2): 022316, 22 Februari 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Sergey Bravyi dan Dmitri Maslov. Sirkuit bebas Hadamard memperlihatkan struktur grup clifford. IEEE Trans. Inf. Teori, 67 (7): 4546–4563, Juli 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell dan Joe O'Gorman. Pendekatan keadaan ajaib yang efisien untuk rotasi sudut kecil. 14 Maret 2016. URL https:///doi.org/10.1088/2058-9565/1/1/015007.
https://doi.org/10.1088/2058-9565/1/1/015007

[11] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, dan Jerry Li. Pemisahan eksponensial antara pembelajaran dengan dan tanpa memori kuantum. Pada Simposium Tahunan ke-2021 IEEE tentang Yayasan Ilmu Komputer (FOCS) tahun 62. IEEE, Februari 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari, dan Rolando D Somma. Algoritme kuantum untuk sistem persamaan linier dengan ketergantungan presisi yang ditingkatkan secara eksponensial. SIAM J. Comput., 46 (6): 1920–1950, 1 Januari 2017. ISSN 0097-5397. 10.1137/16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[13] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, dan Yoshihisa Yamamoto. Simulasi kimia kuantum yang lebih cepat pada komputer kuantum yang toleran terhadap kesalahan. J. Phys. Baru, 14 (11): 115023, 27 November 2012. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

[14] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, dan Dominic W Berry. Pemecah sistem linier kuantum penskalaan optimal melalui teorema adiabatik diskrit. Kuantum PRX, 3 (4): 040303, 7 Oktober 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang, dan Jarrod R McClean. Meninjau kembali dekuantisasi dan keunggulan kuantum dalam tugas pembelajaran. 1 Desember 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman, dan Anirudh Krishna. Gerbang diagonal dalam hierarki clifford. Fis. Pdt A, 95 (1), 26 Januari 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone, dan Sam Gutmann. Algoritma optimasi perkiraan kuantum. 14 November 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Komputasi kuantum dengan waktu optimal. 17 Oktober 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian dan François Le Gall. Dekuantisasi transformasi nilai singular kuantum: kekerasan dan penerapan pada kimia kuantum dan dugaan PCP kuantum. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-54 tentang Teori Komputasi, STOC 2022, halaman 19–32, New York, NY, AS, 9 Juni 2022. ACM. ISBN 9781450392648/10.1145.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney dan Martin Ekerå. Cara memfaktorkan bilangan bulat RSA 2048 bit dalam 8 jam menggunakan 20 juta qubit berisik. Kuantum, 5 (433): 433, 15 April 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney dan Austin G Fowler. Tata letak komputasi kode permukaan yang fleksibel menggunakan status AutoCCZ. 21 Mei 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] András Gilyén dan Alexander Poremba. Peningkatan algoritma kuantum untuk estimasi fidelitas. 29 Maret 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman dan Isaac L Chuang. Teleportasi kuantum adalah komputasi primitif universal. 2 Agustus 1999. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady dan Ali Kemal Sinop. Perkiraan segmentasi random walker yang cepat menggunakan prakomputasi vektor eigen. Pada Konferensi IEEE 2008 tentang Visi Komputer dan Pengenalan Pola, halaman 1–8. IEEE, Juni 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Cinta K Grover. Algoritma mekanika kuantum cepat untuk pencarian basis data. Dalam Prosiding simposium ACM tahunan ke dua puluh delapan tentang Teori komputasi – STOC '96, STOC '96, halaman 212–219, New York, New York, AS, 1996. ACM Press. ISBN 9780897917858/10.1145.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Aram W Harrow, Avinatan Hassidim, dan Seth Lloyd. Algoritma kuantum untuk sistem persamaan linier. Fis. Pendeta Lett., 103 (15): 150502, 9 Oktober 2009. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, dan Jarrod R McClean. Keuntungan kuantum dalam belajar dari eksperimen. Sains, 376 (6598): 1182–1186, 10 Juni 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Protokol distilasi untuk keadaan fourier dalam komputasi kuantum. 12 Maret 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Keuntungan kuantum untuk masalah streaming alami. Pada Simposium Tahunan ke-2021 IEEE tentang Yayasan Ilmu Komputer (FOCS) tahun 62, halaman 897–908. IEEE, Februari 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp dan Richard J Lipton. Beberapa hubungan antara kelas kompleksitas yang tidak seragam dan seragam. Dalam Prosiding simposium ACM tahunan kedua belas tentang Teori komputasi – STOC '80, STOC '80, halaman 302–309, New York, New York, AS, 28 April 1980. ACM Press. ISBN 9780897910170/10.1145.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, dan Theodore J Yoder. Simulasi Hamiltonian dengan kompleksitas sampel optimal. Npj Quantum Inf., 3 (1): 1–7, 30 Maret 2017. ISSN 2056-6387,2056-6387. 10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7

[32] Francois Le Gall. Pemisahan eksponensial kompleksitas ruang online kuantum dan klasik. Dalam Prosiding simposium ACM tahunan kedelapan belas tentang Paralelisme dalam algoritma dan arsitektur, SPAA '06, halaman 67–73, New York, NY, AS, 30 Juli 2006. ACM. ISBN 9781595934529/10.1145.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin dan Yu Tong. Pemfilteran keadaan eigen kuantum berbasis polinomial yang optimal dengan aplikasi untuk menyelesaikan sistem linier kuantum. Kuantum, 4 (361): 361, 11 November 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Daniel Litinsky. Distilasi keadaan ajaib: Tidak semahal yang Anda kira. Quantum, 3 (205): 205, 2 Desember 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinsky. Permainan kode permukaan: Komputasi kuantum skala besar dengan operasi kisi. Quantum, 3 (128): 128, 5 Maret 2019b. ISSN 2521-327X. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128

[36] Seth Lloyd, Masoud Mohseni, dan Patrick Rebentrost. Analisis komponen utama kuantum. Nat. Fis., 10 (9): 631–633, 27 September 2014. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https:///doi.org/10.1038/nphys3029

[37] John M Martyn, Zane M Rossi, Andrew K Tan, dan Isaac L Chuang. Penyatuan besar algoritma kuantum. Kuantum PRX, 2 (4): 040203, 3 Desember 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian dan Seth Lloyd. Emulator kuantum universal. 8 Juni 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher, dan FK Wilhelm. Komposisi waktu linier dan logaritmik dari operator banyak benda kuantum. Fis. Pdt Lett., 119 (16): 160503, 20 Oktober 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Komputasi kuantum optik menggunakan status cluster. Fis. Pdt Lett., 93 (4): 040503, 23 Juli 2004. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.93.040503.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

[41] Bryan O'Gorman, William J Huggins, Eleanor G Rieffel, dan K Birgitta Whaley. Jaringan pertukaran umum untuk komputasi kuantum jangka pendek. 13 Mei 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham dan Krysta M Svore. Arsitektur kuantum tetangga terdekat 2D untuk memperhitungkan kedalaman polilogaritmik. 27 Juli 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf dan HJ Briegel. Komputer kuantum satu arah. Fis. Pendeta Lett., 86 (22): 5188–5191, 28 Mei 2001. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[44] Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, dan Ryan Babbush. Kompilasi heuristik kuantum toleran kesalahan untuk optimasi kombinatorial. Kuantum PRX, 1 (2): 020312, 9 November 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd dan Michael J Bremner. Komputasi kuantum yang tidak terstruktur secara sementara. Proses. Matematika. Fis. bahasa Inggris Sains, 465 (2105): 1413–1439, 8 Mei 2009. ISSN 1364-5021,1471-2946. 10.1098/rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz, dan John Snyder. Transfer pancaran yang telah dihitung sebelumnya untuk rendering waktu nyata dalam lingkungan pencahayaan frekuensi rendah yang dinamis. Dalam Prosiding konferensi tahunan ke-29 tentang Grafik komputer dan teknik interaktif, SIGGRAPH '02, halaman 527–536, New York, NY, AS, 1 Juli 2002. ACM. ISBN 9781581135213/10.1145.
https: / / doi.org/ 10.1145 / 566570.566612

[47] James E Smith. Sebuah studi tentang strategi prediksi cabang. Dalam 25 tahun simposium internasional arsitektur Komputer (makalah terpilih), ISCA '98, halaman 202–215, New York, NY, AS, 1 Agustus 1998. ACM. ISBN 9781581130584/10.1145.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma dan Yiğit Subaşı. Kompleksitas verifikasi keadaan kuantum dalam masalah sistem linier kuantum. Kuantum PRX, 2 (1): 010315, 27 Januari 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Koreksi kesalahan kuantum untuk memori kuantum. Pendeta Mod. Fis., 87 (2): 307–346, 7 April 2015. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Xinlan Zhou, Debbie W Leung, dan Isaac L Chuang. Metodologi konstruksi gerbang logika kuantum. Fis. Pdt. A, 62 (5), 18 Oktober 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Dikutip oleh

[1] Dar Gilboa dan Jarrod R. McClean, “Keunggulan Komunikasi Kuantum Eksponensial dalam Pembelajaran Terdistribusi”, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost, dan Mikel Sanz, “Perkiraan eksponen matriks kepadatan berbantuan kloning kuantum”, arXiv: 2311.11751, (2023).

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2024-02-22 13:13:08). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.

Tidak dapat mengambil Crossref dikutip oleh data selama upaya terakhir 2024-02-22 13:13:06: Tidak dapat mengambil data yang dikutip oleh untuk 10.22331 / q-2024-02-22-1264 dari Crossref. Ini normal jika DOI terdaftar baru-baru ini.

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-2024-02-22-1264/

Stempel Waktu: Februari 22, 2024

Stempel Waktu: Juni 1, 2023

Mempercepat Algoritma Kuantum dengan Prakomputasi

Diterbitkan Ulang Oleh Plato

Abstrak

► data BibTeX

► Referensi

Dikutip oleh

Lebih dari Jurnal Kuantum

Perceval: Platform Perangkat Lunak untuk Komputasi Kuantum Fotonik Variabel Diskrit

Sirkuit kuantum universal untuk kimia kuantum

Teori efektif versus Floquet untuk osilator parametrik Kerr

Sirkuit saluran kuantum ruang dan waktu

Teorema kekekalan energi dan fluktuasi tidak sesuai untuk kerja kuantum

Pengkodean osilator yang optimal menjadi lebih banyak osilator

Diskriminasi dan sertifikasi pengukuran kuantum yang tidak diketahui

Pengambilan sampel penting untuk simulasi kuantum stokastik

Algoritme pengiriman pesan kuantum untuk decoding yang optimal dan efisien

Tomografi Bayangan Klasik yang Dapat Diskalakan dan Fleksibel dengan Tensor Networks

Tentang Kami

Pencarian Vertikal & Ai

Platform

Tetap Berhubung

Akun