Sous-programmes quantiques de base : trouver plusieurs éléments marqués et additionner des nombres

Sous-programmes quantiques de base : trouver plusieurs éléments marqués et additionner des nombres

Horodatage: 14 mars 2024 9:40
Sous-programmes quantiques de base : trouver plusieurs éléments marqués et additionner les nombres PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

Joran van Apeldoorn1, Sander Gribling2et une Harold Nieuwboer3

1IViR et QuSoft, Université d'Amsterdam, Pays-Bas
2Département d'économétrie et de recherche opérationnelle, Université de Tilburg, Tilburg, Pays-Bas
3Institut Korteweg-de Vries de mathématiques et QuSoft, Université d'Amsterdam, Pays-Bas et Faculté d'informatique, Université de la Ruhr à Bochum, Allemagne et Département des sciences mathématiques, Université de Copenhague, Danemark

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Nous montrons comment trouver tous les éléments marqués $k$ dans une liste de taille $N$ en utilisant le nombre optimal $O(sqrt{N k})$ de requêtes quantiques et uniquement une surcharge polylogarithmique dans la complexité de la porte, dans le cadre où on a une petite mémoire quantique. Les algorithmes précédents entraînaient soit un facteur $k$ de surcharge dans la complexité de la porte, soit un facteur supplémentaire $log(k)$ dans la complexité de la requête.
Nous considérons ensuite le problème de trouver une approximation $delta$ multiplicative de $s = sum_{i=1}^N v_i$ où $v=(v_i) dans [0,1]^N$, étant donné l'accès aux requêtes quantiques à une description binaire de $v$. Nous donnons un algorithme qui le fait, avec une probabilité d'au moins $1-rho$, en utilisant des requêtes quantiques $O(sqrt{N log(1/rho) / delta})$ (sous des hypothèses douces sur $rho$). Cela améliore quadratiquement la dépendance à l'égard de $1/delta$ et $log(1/rho)$ par rapport à une application simple de l'estimation d'amplitude. Pour obtenir la dépendance $log(1/rho)$ améliorée, nous utilisons le premier résultat.

► Données BibTeX

► Références

Srinivasan Arunachalam et Ronald de Wolf. Optimiser le nombre de portes dans la recherche quantique. Informations quantiques. Calcul., 17(3-4):251-261, 2017. est ce que je:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

José A. Adell et P. Jodrá. Kolmogorov exact et distances de variation totales entre certaines distributions discrètes familières. Journal des inégalités et des applications, 2006(1):1–8, 2006. est ce que je:10.1155/​JIA/​2006/​64307.
https://​/​doi.org/​10.1155/​JIA/​2006/​64307

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter et Ronald de Wolf. Algorithmes quantiques pour la mise à l'échelle et l'équilibrage matriciels. Dans Actes du 48e Colloque international sur les automates, les langages et la programmation (ICALP'21), volume 198, pages 110 :1–110 :17, 2021. arXiv :2011.12823, est ce que je :10.4230/​LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

Scott Aaronson et Patrick Rall. Comptage quantique approximatif, simplifié. Dans Symposium sur la simplicité des algorithmes, pages 24 à 32, 2020. est ce que je:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

Michel Boyer, Gilles Brassard, Peter Høyer et Alain Tapp. Des limites strictes à la recherche quantique. Fortschritte der Physik, 46(4–5):493–505, 1998. Version antérieure dans Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: quant-ph / 9605034

Harry Buhrman, Richard Cleve, Ronald de Wolf et Christof Zalka. Limites des algorithmes quantiques à petites erreurs et à zéro erreur. Dans le 40e Symposium annuel sur les fondements de l'informatique (FOCS'99), pages 358-368. Société informatique IEEE, 1999.

Gilles Brassard, Peter Høyer, Michele Mosca et Alain Tapp. Amplification et estimation de l'amplitude quantique. Dans Calcul quantique et information quantique : un volume millénaire, volume 305 de Mathématiques contemporaines, pages 53-74. Société mathématique américaine, 2002. est ce que je: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

Richard Brent et Paul Zimmermann. Arithmétique informatique moderne, volume 18. Cambridge University Press, 2010.

Ran Canetti, Guy Even et Oded Goldreich. Limites inférieures des algorithmes d'échantillonnage pour estimer la moyenne. Lettres de traitement de l'information, 53(1):17-25, janvier 1995. est ce que je:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini et Leonard Wossnig. Apprentissage automatique quantique : une perspective classique. Actes de la Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, janvier 2018. est ce que je:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein. Introduction aux algorithmes. MIT Press, 4e édition, 2022.

P. Diaconis et D. Freedman. Séquences finies échangeables. Les Annales des probabilités, 8(4):745-764, 1980. URL : https:/​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ stable / 2242823

Christoph Dürr et Peter Høyer. Un algorithme quantique pour trouver le minimum, 1996. est ce que je:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 9607014

Christoph Dürr, Mark Heiligman, Peter Høyer et Mehdi Mhalla. Complexité des requêtes quantiques de certains problèmes de graphiques. SIAM Journal on Computing, 35(6):1310-1328, janvier 2006. est ce que je:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

Paul Dagum, Richard Karp, Michael Luby et Sheldon Ross. Un algorithme optimal pour l'estimation de Monte Carlo. SIAM Journal on Computing, 29(5):1484-1496, janvier 2000. est ce que je:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

Vittorio Giovannetti, Seth Lloyd et Lorenzo Maccone. Mémoire vive quantique. Physical Review Letters, 100(16), avril 2008. est ce que je:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

Sander Gribling et Harold Nieuwboer. Amélioration des limites quantiques inférieures et supérieures pour la mise à l'échelle de la matrice. Dans Actes du 39e Symposium international sur les aspects théoriques de l'informatique (STACS'22), volume 219, pages 35 :1–35 :23, 2022. arXiv :2109.15282, est ce que je :10.4230/​LIPIcs.STACS.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

Mart de Graaf et Ronald de Wolf. Sur les versions quantiques du principe de Yao. Dans le 19e Symposium sur les aspects théoriques de l'informatique (STACS'02), volume 2285 de Lecture Notes in Computer Science, pages 347-358, Berlin, Heidelberg, 2002. Springer. est ce que je:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

Amour K. Grover. Un algorithme de mécanique quantique rapide pour la recherche dans des bases de données. Dans Actes du 38e Symposium annuel de l'ACM sur la théorie de l'informatique (STOC'96), pages 212-219, 1996. arXiv:quant-ph/​9605043, est ce que je:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

Amour K. Grover. Téléinformatique quantique, 1997. Mémorandum technique des Bell Labs ITD97-31630F. est ce que je:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 9704012

Amour K. Grover. Un cadre pour des algorithmes de mécanique quantique rapides. Dans Actes du trentième symposium annuel de l'ACM sur la théorie de l'informatique (STOC'98), pages 53-62, 1998. arXiv:quant-ph/​9711043, est ce que je:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

Yassine Hamoudi. Estimateur de moyenne sous-gaussienne quantique. Dans le 29e Symposium européen annuel sur les algorithmes (ESA 2021), volume 204 de Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:17, 2021. est ce que je:10.4230/​LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

Svante Janson. Limites de queue pour les sommes de variables géométriques et exponentielles. Lettres de statistiques et de probabilités, 135 : 1–6, 2018. est ce que je :10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

Donald Ervin Knuth. L'art de la programmation informatique, volume III. Addison-Wesley, 2e édition, 1998. URL : https:/​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

Robin Kothari et Ryan O'Donnell. Estimation moyenne lorsque vous disposez du code source ; ou, les méthodes quantiques de Monte Carlo. Dans Actes du Symposium annuel ACM-SIAM 2023 sur les algorithmes discrets (SODA'23), pages 1186-1215, 2023. est ce que je:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

Michael A. Nielsen et Isaac L. Chuang. Calcul quantique et information quantique. Cambridge University Press, 2002.

Ashwin Nayak et Félix Wu. La complexité des requêtes quantiques pour approximer les statistiques médianes et associées. Dans Actes du 31e Symposium annuel ACM SIGACT sur la théorie de l'informatique (STOC'99), pages 384-393, 1999. arXiv:quant-ph/​9804066, est ce que je:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

B.Roos. Approximation binomiale de la distribution binomiale de Poisson : l'expansion de Krawtchouk. Théorie des probabilités et ses applications, 45(2):258-272, 2001. est ce que je:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

Robert M. Young. 75.9 Constante d'Euler. The Mathematical Gazette, 75(472):187-190, 1991. est ce que je:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

Cité par

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique