Subrutinas cuánticas básicas: encontrar múltiples elementos marcados y sumar números

Reeditado por Platón

seguidores: 0

Subrutinas cuánticas básicas: encontrar múltiples elementos marcados y sumar números PlatoBlockchain Data Intelligence. Búsqueda vertical. Ai.

Joran van Apeldoorn¹, Sander Gribling²y Harold Nieuwboer³

¹IViR y QuSoft, Universidad de Amsterdam, Países Bajos
²Departamento de Econometría e Investigación de Operaciones, Universidad de Tilburg, Tilburg, Países Bajos
³Instituto Korteweg–de Vries de Matemáticas y QuSoft, Universidad de Amsterdam, Países Bajos y Facultad de Ciencias de la Computación, Universidad Ruhr de Bochum, Alemania y Departamento de Ciencias Matemáticas, Universidad de Copenhague, Dinamarca

¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.

Resumen

Mostramos cómo encontrar todos los $k$ elementos marcados en una lista de tamaño $N$ usando el número óptimo $O(sqrt{N k})$ de consultas cuánticas y solo una sobrecarga polilogarítmica en la complejidad de la puerta, en el entorno donde uno tiene una pequeña memoria cuántica. Los algoritmos anteriores incurrían en un factor $k$ de sobrecarga en la complejidad de la puerta o tenían un factor adicional $log(k)$ en la complejidad de la consulta.
Luego consideramos el problema de encontrar una aproximación $delta$ multiplicativa de $s = sum_{i=1}^N v_i$ donde $v=(v_i) en [0,1]^N$, dado el acceso a la consulta cuántica una descripción binaria de $v$. Proporcionamos un algoritmo que lo hace, con una probabilidad de al menos $1-rho$, utilizando consultas cuánticas $O(sqrt{N log(1/rho) / delta})$ (bajo suposiciones leves sobre $rho$). Esto mejora cuadráticamente la dependencia de $1/delta$ y $log(1/rho)$ en comparación con una aplicación sencilla de estimación de amplitud. Para obtener la dependencia $log(1/rho)$ mejorada utilizamos el primer resultado.

► datos BibTeX

@artículo{vanApeldoorn2024basicquantum, doi = {10.22331/q-2024-03-14-1284}, URL = {https://doi.org/10.22331/q-2024-03-14-1284}, título = {Subrutinas cuánticas básicas: encontrar múltiples elementos marcados y sumar números}, autor = {van Apeldoorn, Joran y Gribling, Sander y Nieuwboer, Harold}, diario = {{Quantum}}, issn = {2521-327X}, editor = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volumen = {8}, páginas = {1284}, mes = marzo, año = {2024} }

► referencias

[ 1 ] Srinivasan Arunachalam y Ronald de Wolf. Optimización del número de puertas en la búsqueda cuántica. Información cuántica. Comput., 17(3-4):251–261, 2017. doi:10.26421/qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[ 2 ] José A. Adell y P. Jodrá. Distancias exactas de Kolmogorov y variación total entre algunas distribuciones discretas familiares. Revista de desigualdades y aplicaciones, 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 y Ronald de Wolf. Algoritmos cuánticos para escalado y equilibrio matricial. En Actas del 48.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP'21), volumen 198, páginas 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 y Patrick Rall. Conteo cuántico aproximado, simplificado. En Simposio sobre simplicidad en algoritmos, páginas 24 a 32, 2020. doi:10.1137/1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[ 5 ] Michel Boyer, Gilles Brassard, Peter Høyer y Alain Tapp. Límites estrictos para la búsqueda cuántica. Fortschritte der Physik, 46(4–5):493–505, 1998. Versión anterior en Physcomp'96. arXiv:quant-ph/9605034.
arXiv: quant-ph / 9605034

[ 6 ] Harry Buhrman, Richard Cleve, Ronald de Wolf y Christof Zalka. Límites para algoritmos cuánticos de error pequeño y error cero. En el 40º Simposio anual sobre fundamentos de la informática (FOCS'99), páginas 358–368. Sociedad de Computación IEEE, 1999.

[ 7 ] Gilles Brassard, Peter Høyer, Michele Mosca y Alain Tapp. Amplificación y estimación de amplitud cuántica. En Computación cuántica e información cuántica: un volumen milenario, volumen 305 de Matemáticas contemporáneas, páginas 53–74. Sociedad Americana de Matemáticas, 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 y Paul Zimmermann. Aritmética informática moderna, volumen 18. Cambridge University Press, 2010.

[ 9 ] Ran Canetti, Guy Even y Oded Goldreich. Límites inferiores de algoritmos de muestreo para estimar el promedio. Cartas de procesamiento de información, 53(1):17–25, enero de 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 y Leonard Wossnig. Aprendizaje automático cuántico: una perspectiva clásica. Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería, 474(2209):20170551, enero de 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 y Clifford Stein. Introducción a los algoritmos. MIT Press, 4.a edición, 2022.

[ 12 ] P. Diaconis y D. Freedman. Secuencias finitas intercambiables. The Annals of Probability, 8(4):745–764, 1980. URL: https://www.jstor.org/stable/2242823.
https: / / www.jstor.org/ stable / 2242823

[ 13 ] Christoph Dürr y Peter Høyer. Un algoritmo cuántico para encontrar el mínimo, 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 y Mehdi Mhalla. Complejidad de las consultas cuánticas de algunos problemas de gráficos. Revista SIAM de Computación, 35(6):1310–1328, enero de 2006. doi:10.1137/050644719.
https: / / doi.org/ 10.1137 / 050644719

[ 15 ] Paul Dagum, Richard Karp, Michael Luby y Sheldon Ross. Un algoritmo óptimo para la estimación de Monte Carlo. Revista SIAM de Computación, 29(5):1484–1496, enero de 2000. doi:10.1137/S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[ 16 ] Vittorio Giovannetti, Seth Lloyd y Lorenzo Maccone. Memoria cuántica de acceso aleatorio. Physical Review Letters, 100(16), abril de 2008. doi:10.1103/physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[ 17 ] Sander Gribling y Harold Nieuwboer. Límites superiores e inferiores cuánticos mejorados para el escalado matricial. En Actas del 39.º Simposio internacional sobre aspectos teóricos de la informática (STACS'22), volumen 219, páginas 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 y Ronald de Wolf. Sobre las versiones cuánticas del principio de Yao. En el XIX Simposio sobre aspectos teóricos de la informática (STACS'19), volumen 02 de Lecture Notes in Computer Science, páginas 2285–347, Berlín, Heidelberg, 358. Springer. doi:2002/10.1007-3-540-45841_7.
https://doi.org/10.1007/3-540-45841-7_28

[ 19 ] Lov K. Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. En Actas del 38º Simposio Anual ACM sobre Teoría de la Computación (STOC'96), páginas 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. Telecomputación cuántica, 1997. Memorando técnico de 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. Un marco para algoritmos mecánicos cuánticos rápidos. En Actas del trigésimo simposio anual ACM sobre teoría de la computación (STOC'98), páginas 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. Estimador cuántico de media subgaussiana. En 29.º Simposio europeo anual sobre algoritmos (ESA 2021), volumen 204 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 50:1–50:17, 2021. doi:10.4230/LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[ 23 ] Svante Janson. Límites de cola para sumas de variables geométricas y exponenciales. Cartas de estadística y probabilidad, 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. El arte de la programación informática, volumen III. Addison-Wesley, 2.ª edición, 1998. URL: https://www.worldcat.org/oclc/312994415.
https:///www.worldcat.org/oclc/312994415

[ 25 ] Robin Kothari y Ryan O'Donnell. Estimación media cuando tienes el código fuente; o métodos cuánticos de Monte Carlo. En Actas del Simposio anual ACM-SIAM de 2023 sobre algoritmos discretos (SODA'23), páginas 1186–1215, 2023. doi:10.1137/1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[ 26 ] Michael A. Nielsen e Isaac L. Chuang. Cálculo cuántico e información cuántica. Cambridge University Press, 2002.

[ 27 ] Ashwin Nayak y Félix Wu. La complejidad de la consulta cuántica para aproximar la mediana y las estadísticas relacionadas. En Actas del 31º Simposio Anual ACM SIGACT sobre Teoría de la Computación (STOC'99), páginas 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. Roos. Aproximación binomial a la distribución binomial de Poisson: la expansión de Krawtchouk. Teoría de la probabilidad y sus aplicaciones, 45(2):258–272, 2001. doi:10.1137/S0040585X9797821X.
https:///doi.org/10.1137/S0040585X9797821X

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

Citado por

Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.