Subrutin kuantum dasar: menemukan beberapa elemen yang ditandai dan menjumlahkan angka

Subrutin kuantum dasar: menemukan beberapa elemen yang ditandai dan menjumlahkan angka

Stempel Waktu: 14 Maret 2024 9
Subrutin kuantum dasar: menemukan beberapa elemen yang ditandai dan menjumlahkan angka Intelijen Data PlatoBlockchain. Pencarian Vertikal. Ai.

Joran van Apeldoorn1, Sander Gribling2, dan Harold Nieuwboer3

1IViR dan QuSoft, Universitas Amsterdam, Belanda
2Departemen Ekonometrika dan Riset Operasi, Universitas Tilburg, Tilburg, Belanda
3Institut Matematika dan QuSoft Korteweg–de Vries, Universitas Amsterdam, Belanda dan Fakultas Ilmu Komputer, Universitas Ruhr Bochum, Jerman dan Departemen Ilmu Matematika, Universitas Kopenhagen, Denmark

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

Abstrak

Kami menunjukkan cara menemukan semua elemen yang ditandai $k$ dalam daftar ukuran $N$ menggunakan jumlah optimal $O(sqrt{N k})$ kueri kuantum dan hanya overhead polilogaritmik dalam kompleksitas gerbang, dalam pengaturan di mana seseorang memiliki memori kuantum kecil. Algoritme sebelumnya mengeluarkan faktor $k$ overhead dalam kompleksitas gerbang, atau memiliki faktor tambahan $log(k)$ dalam kompleksitas kueri.
Kami kemudian mempertimbangkan masalah menemukan perkiraan $delta$ perkalian dari $s = sum_{i=1}^N v_i$ di mana $v=(v_i) di [0,1]^N$, dengan memberikan akses kueri kuantum ke deskripsi biner $v$. Kami memberikan algoritme yang dapat melakukannya, dengan probabilitas setidaknya $1-rho$, menggunakan kueri kuantum $O(sqrt{N log(1/rho) / delta})$ (dengan asumsi ringan pada $rho$). Hal ini secara kuadrat meningkatkan ketergantungan pada $1/delta$ dan $log(1/rho)$ dibandingkan dengan penerapan estimasi amplitudo secara langsung. Untuk mendapatkan ketergantungan $log(1/rho)$ yang lebih baik, kami menggunakan hasil pertama.

► data BibTeX

► Referensi

[1] Srinivasan Arunachalam dan Ronald de Wolf. Mengoptimalkan jumlah gerbang dalam pencarian kuantum. Info Kuantum. Komput., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell dan P. Jodrá. Kolmogorov yang tepat dan jarak variasi total antara beberapa distribusi diskrit yang sudah dikenal. Jurnal Ketimpangan dan Penerapan, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https:/​/​doi.org/​10.1155/​JIA/​2006/​64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, dan Ronald de Wolf. Algoritma kuantum untuk penskalaan matriks dan penyeimbangan matriks. Dalam Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), volume 198, halaman 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] Scott Aaronson dan Patrick Rall. Penghitungan perkiraan kuantum, disederhanakan. Dalam Simposium Kesederhanaan dalam Algoritma, halaman 24–32, 2020. doi:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer, dan Alain Tapp. Batasan ketat pada pencarian kuantum. Fortschritte der Physik, 46(4–5):493–505, 1998. Versi sebelumnya di Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf, dan Christof Zalka. Batasan untuk algoritma kuantum kesalahan kecil dan kesalahan nol. Dalam Simposium Tahunan ke-40 tentang Landasan Ilmu Komputer (FOCS'99), halaman 358–368. Masyarakat Komputer IEEE, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca, dan Alain Tapp. Amplifikasi dan estimasi amplitudo kuantum. Dalam Komputasi Kuantum dan Informasi Kuantum: Volume Milenium, volume 305 Matematika Kontemporer, halaman 53–74. Persatuan Matematika Amerika, 2002. doi: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] Richard Brent dan Paul Zimmermann. Aritmatika Komputer Modern, volume 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even, dan Oded Goldreich. Batas bawah algoritma pengambilan sampel untuk memperkirakan rata-rata. Surat Pemrosesan Informasi, 53(1):17–25, Januari 1995. doi:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, dan Leonard Wossnig. Pembelajaran mesin kuantum: perspektif klasik. Prosiding Royal Society A: Ilmu Matematika, Fisika dan Teknik, 474(2209):20170551, jan 2018. doi:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, dan Clifford Stein. Pengantar Algoritma. MIT Press, edisi ke-4, 2022.

[12] P. Diaconis dan D. Freedman. Urutan Terbatas yang Dapat Ditukar. Sejarah Probabilitas, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ stable / 2242823

[13] Christoph Dürr dan Peter Høyer. Algoritme kuantum untuk mencari nilai minimum, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer, dan Mehdi Mhalla. Kompleksitas Kueri Kuantum dari Beberapa Masalah Grafik. Jurnal SIAM tentang Komputasi, 35(6):1310–1328, Januari 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby, dan Sheldon Ross. Algoritma Optimal untuk Estimasi Monte Carlo. Jurnal SIAM tentang Komputasi, 29(5):1484–1496, Januari 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd, dan Lorenzo Maccone. Memori akses acak kuantum. Surat Tinjauan Fisik, 100(16), apr 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling dan Harold Nieuwboer. Peningkatan batas bawah dan atas kuantum untuk penskalaan matriks. Dalam Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), volume 219, halaman 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/​LIPIcs.STACS.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] Mart de Graaf dan Ronald de Wolf. Tentang Prinsip Yao Versi Kuantum. Dalam Simposium ke-19 tentang Aspek Teoritis Ilmu Komputer (STACS'02), volume 2285 dari Catatan Kuliah Ilmu Komputer, halaman 347–358, Berlin, Heidelberg, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] Lov K. Grover. Algoritma mekanika kuantum cepat untuk pencarian basis data. Dalam Prosiding Simposium ACM Tahunan ke-38 tentang Teori Komputasi (STOC'96), halaman 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[20] Lov K. Grover. Telekomputasi kuantum, 1997. Memorandum Teknis Bell Labs ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 9704012

[21] Lov K. Grover. Kerangka kerja untuk algoritma mekanika kuantum cepat. Dalam Prosiding Simposium ACM Tahunan Ketiga Puluh tentang Teori Komputasi (STOC'98), halaman 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

[22] Yassine Hamoudi. Penaksir Rata-rata Sub-Gaussian Kuantum. Dalam Simposium Eropa Tahunan ke-29 tentang Algoritma (ESA 2021), volume 204 dari Leibniz International Proceedings in Informatics (LIPIcs), halaman 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] Svante Janson. Batas ekor jumlah variabel geometri dan eksponensial. Surat Statistik & Probabilitas, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] Donald Ervin Knuth. Seni Pemrograman Komputer, volume III. Addison-Wesley, edisi ke-2, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https:/​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari dan Ryan O'Donnell. Estimasi rata-rata bila Anda memiliki kode sumber; atau, metode kuantum Monte Carlo. Dalam Prosiding Simposium ACM-SIAM Tahunan 2023 tentang Algoritma Diskrit (SODA'23), halaman 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen dan Isaac L. Chuang. Komputasi kuantum dan informasi kuantum. Cambridge University Press, 2002.

[27] Ashwin Nayak dan Felix Wu. Kompleksitas kueri kuantum dalam memperkirakan median dan statistik terkait. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-31 tentang Teori Komputasi (STOC'99), halaman 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

[28] B.Ayam. Pendekatan Binomial terhadap Distribusi Binomial Poisson: Ekspansi Krawtchouk. Teori Probabilitas & Penerapannya, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

[29] Robert M.Muda. 75.9 Konstanta Euler. Lembaran Matematika, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

Dikutip oleh

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.

Stempel Waktu:

Lebih dari Jurnal Kuantum