Temel kuantum alt rutinleri: birden çok işaretli öğeyi bulma ve sayıları toplama

Temel kuantum alt rutinleri: birden çok işaretli öğeyi bulma ve sayıları toplama

Zaman Damgası: 14 Mart 2024 9:40
Temel kuantum alt rutinleri: birden fazla işaretli öğeyi bulma ve sayıları toplama PlatoBlockchain Veri Zekası. Dikey Arama. Ai.

Joran van Apeldoorn1, Zımparalama2, ve Harold Nieuwboer3

1IViR ve QuSoft, Amsterdam Üniversitesi, Hollanda
2Ekonometri ve Yöneylem Araştırması Bölümü, Tilburg Üniversitesi, Tilburg, Hollanda
3Korteweg–de Vries Matematik Enstitüsü ve QuSoft, Amsterdam Üniversitesi, Hollanda ve Bilgisayar Bilimleri Fakültesi, Ruhr Üniversitesi Bochum, Almanya ve Matematik Bilimleri Bölümü, Kopenhag Üniversitesi, Danimarka

Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.

Özet

Kuantum sorgularının optimal sayısını $O(sqrt{N k})$ kullanarak ve kapı karmaşıklığında yalnızca polilogaritmik bir yükü kullanarak $N$ boyutundaki bir listedeki $k$ işaretli tüm öğelerin nasıl bulunacağını gösteriyoruz. kişinin küçük bir kuantum hafızası vardır. Önceki algoritmalar ya kapı karmaşıklığında bir $k$ ek yüküne maruz kalıyordu ya da sorgu karmaşıklığında fazladan bir $log(k)$ faktörüne sahipti.
Daha sonra, kuantum sorgu erişimi göz önüne alındığında, $s = toplam_{i=1}^N v_i$ burada $v=(v_i) in [0,1]^N$ çarpımsal $delta$-yaklaşımını bulma problemini ele alıyoruz. $v$'ın ikili açıklaması. $O(sqrt{N log(1/rho) / delta})$ kuantum sorgularını ($rho$ ile ilgili hafif varsayımlar altında) kullanarak, en az $1-rho$ olasılıkla bunu yapan bir algoritma veriyoruz. Bu, basit bir genlik tahmini uygulamasıyla karşılaştırıldığında $1/delta$ ve $log(1/rho)$ bağımlılığını ikinci dereceden artırır. Geliştirilmiş $log(1/rho)$ bağımlılığını elde etmek için ilk sonucu kullanırız.

► BibTeX verileri

► Referanslar

[1] Srinivasan Arunachalam ve Ronald de Wolf. Kuantum aramada kapı sayısını optimize etmek. Kuantum Bilgisi. Comp., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell ve P. Jodrá. Kesin Kolmogorov ve bazı tanıdık ayrık dağılımlar arasındaki toplam değişim mesafeleri. Eşitsizlikler ve Uygulamalar Dergisi, 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 ve Ronald de Wolf. Matris ölçeklendirme ve matris dengeleme için kuantum algoritmaları. 48. Uluslararası Otomata, Diller ve Programlama Toplantısı Bildirileri (ICALP'21), cilt 198, sayfalar 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 ve Patrick Rall. Kuantum yaklaşık sayımı, basitleştirilmiş. Algoritmalarda Basitlik Sempozyumu, sayfa 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 ve Alain Tapp. Kuantum arayışında sıkı sınırlar Fortschritte der Physik, 46(4–5):493–505, 1998. Physcomp'96'nın önceki versiyonu. arXiv:quant-ph/​9605034.
arXiv: kuant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf ve Christof Zalka. Küçük hata ve sıfır hata kuantum algoritmalarının sınırları. 40. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu (FOCS'99), sayfa 358-368. IEEE Bilgisayar Topluluğu, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca ve Alain Tapp. Kuantum genlik amplifikasyonu ve tahmini. Kuantum Hesaplama ve Kuantum Bilgisi: Bir Milenyum Cilt, Çağdaş Matematik'in 305. cildi, sayfa 53-74'te. Amerikan Matematik Derneği, 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 ve Paul Zimmermann. Modern Bilgisayar Aritmetiği, cilt 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even ve Oded Goldreich. Ortalamayı tahmin etmeye yönelik örnekleme algoritmalarının alt sınırları. Bilgi İşleme Mektupları, 53(1):17–25, Ocak 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 ve Leonard Wossnig. Kuantum makine öğrenimi: Klasik bir bakış açısı. Royal Society A: Matematik, Fiziksel ve Mühendislik Bilimleri Bildirileri, 474(2209):20170551, Ocak 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 ve Clifford Stein. Algoritmalara Giriş. MIT Press, 4. baskı, 2022.

[12] P. Diaconis ve D. Freedman. Sonlu Değiştirilebilir Diziler. Olasılık Yıllıkları, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ kararlı / 2242823

[13] Christoph Dürr ve Peter Høyer. Minimumu bulmak için bir kuantum algoritması, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: kuant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer ve Mehdi Mhalla. Bazı Grafik Problemlerinin Kuantum Sorgulama Karmaşıklığı. SIAM Journal on Computing, 35(6):1310–1328, Ocak 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby ve Sheldon Ross. Monte Carlo Tahmini için Optimal Bir Algoritma. SIAM Journal on Computing, 29(5):1484–1496, Ocak 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd ve Lorenzo Maccone. Kuantum rastgele erişim belleği. Physical Review Letters, 100(16), Nisan 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling ve Harold Nieuwboer. Matris ölçeklendirme için iyileştirilmiş kuantum alt ve üst sınırları. 39. Uluslararası Bilgisayar Biliminin Teorik Yönleri Sempozyumu Bildirileri (STACS'22), cilt 219, sayfalar 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 ve Ronald de Wolf. Yao Prensibinin Kuantum Versiyonları Üzerine. 19. Bilgisayar Biliminin Teorik Yönleri Sempozyumu (STACS'02), Bilgisayar Bilimi Ders Notları cilt 2285, sayfa 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. Kıvırcık. Veritabanı araması için hızlı bir kuantum mekaniksel algoritma. Bilgisayar Teorisi Üzerine 38. Yıllık ACM Sempozyumu Bildirileri (STOC'96), sayfa 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: kuant-ph / 9605043

[20] Lov K. Kıvırcık. Kuantum telekomütasyon, 1997. Bell Labs Teknik Bildirisi ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: kuant-ph / 9704012

[21] Lov K. Kıvırcık. Hızlı kuantum mekaniksel algoritmalar için bir çerçeve. Bilgisayar Teorisi Üzerine Otuzuncu Yıllık ACM Sempozyumu Bildirileri (STOC'98), sayfa 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: kuant-ph / 9711043

[22] Yassine Hamoudi. Kuantum Alt Gauss Ortalama Tahmincisi. 29. Yıllık Avrupa Algoritma Sempozyumu (ESA 2021), Leibniz Uluslararası Bildiriler Kitabı (LIPIcs), cilt 204, sayfa 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] Svante Janson. Geometrik ve üstel değişkenlerin toplamları için kuyruk sınırları. İstatistik ve Olasılık Mektupları, 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. Bilgisayar Programlama Sanatı, cilt III. Addison-Wesley, 2. baskı, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari ve Ryan O'Donnell. Kaynak koduna sahip olduğunuzda ortalama tahmin; veya kuantum Monte Carlo yöntemleri. 2023 Yıllık ACM-SIAM Ayrık Algoritmalar Sempozyumu Bildirileri (SODA'23), sayfa 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen ve Isaac L. Chuang. Kuantum hesaplama ve kuantum bilgisi. Cambridge University Press, 2002.

[27] Ashwin Nayak ve Felix Wu. Medyan ve ilgili istatistiklere yaklaşmanın kuantum sorgu karmaşıklığı. 31. Yıllık ACM SIGACT Hesaplama Teorisi Sempozyumu Bildirileri (STOC'99), sayfa 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: kuant-ph / 9804066

[28] B. Roos. Poisson Binom Dağılımına Binom Yaklaşımı: Krawtchouk Genişlemesi. Olasılık Teorisi ve Uygulamaları, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

[29] Robert M. Young. 75.9 Euler Sabiti. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

Alıntılama

Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.

Zaman Damgası:

Den fazla Kuantum Günlüğü