1QuSoft, Amsterdam, Países Bajos.
2Universidad de Amsterdam, Holanda.
3Universidad de Amsterdam, Holanda.
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Brandão y Svore [14] recientemente dio algoritmos cuánticos para resolver aproximadamente programas semidefinidos, que en algunos regímenes son más rápidos que los mejores algoritmos clásicos posibles en términos de la dimensión $ n $ del problema y el número $ m $ de restricciones, pero peor en términos de varios Otros parámetros. En este artículo mejoramos sus algoritmos de varias maneras, mejorando la dependencia de esos otros parámetros. Con este fin, desarrollamos nuevas técnicas para algoritmos cuánticos, por ejemplo, una forma general de implementar eficientemente funciones suaves de Hamiltonianos dispersos, y un procedimiento generalizado de búsqueda mínima.
También mostramos límites en este enfoque para los solucionadores cuánticos de SDP, por ejemplo, para problemas de optimización combinatoria que tienen mucha simetría. Finalmente, demostramos algunos límites inferiores generales que muestran que, en el peor de los casos, la complejidad de cada solucionador de LP cuántico (y, por lo tanto, también el solucionador de SDP) tiene que escalar linealmente con $ mn $ cuando $ mapprox n $, que es lo mismo que clásico.
Resumen popular
► datos BibTeX
► referencias
[ 1 ] Sanjeev Arora, Elad Hazan y Satyen Kale. El método de actualización de pesos multiplicativos: un meta-algoritmo y aplicaciones. toc, 8 (6): 121-164, 2012.
https: / / doi.org/ 10.4086 / toc.2012.v008a006
[ 2 ] Sanjeev Arora y Satyen Kale. Un enfoque combinatorio, primal-dual para programas semidefinidos. jacm, 63 (2): 12: 1–12: 35, 2016. Versión anterior en STOC'07.
https: / / doi.org/ 10.1145 / 2837020
[ 3 ] Andris Ambainis. Algoritmo de caminata cuántica para la distinción de elementos. siamjc, 37 (1): 210–239, 2007. Versión anterior en FOCS'04. arXiv: quant-ph / 0311001 ?.
https: / / doi.org/ 10.1137 / S0097539705447311
arXiv: quant-ph / 0311001
[ 4 ] Joran van Apeldoorn y András Gilyén. Mejoras en la resolución cuántica de SDP con aplicaciones. En icalp46th, páginas 99: 1–99: 15, 2019. arXiv: 1804.05058 ?.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
arXiv: 1804.05058
[ 5 ] Joran van Apeldoorn y András Gilyén. Algoritmos cuánticos para juegos de suma cero. arXiv: 1904.03180 ?, 2019.
arXiv: 1904.03180
[ 6 ] Joran van Apeldoorn, András Gilyén, Sander Gribling y Ronald de Wolf. Solucionadores Quantum SDP: mejores límites superior e inferior. En focs58th, páginas 403–414, 2017. arXiv: 1705.01843 ?.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arXiv: 1705.01843
[ 7 ] Joran van Apeldoorn, András Gilyén, Sander Gribling y Ronald de Wolf. Optimización convexa utilizando oráculos cuánticos. cuántica, 4: 220, 2020. arXiv: 1809.00643 ?.
https://doi.org/10.22331/q-2020-01-13-220
arXiv: 1809.00643
[ 8 ] Noga Alon y Joel H. Spencer. El método probabilístico. Wiley-Interscience, tercera edición, 2008.
https: / / doi.org/ 10.1002 / 0471722154
[ 9 ] Michel Boyer, Gilles Brassard, Peter Høyer y Alain Tapp. Límites estrechos en la búsqueda cuántica. Fortschritte der Physik, 46 (4–5): 493–505, 1998. arXiv: quant-ph / 9605034 ?.
arXiv: quant-ph / 9605034
[ 10 ] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari y Rolando D. Somma. Simulando la dinámica hamiltoniana con una serie de Taylor truncada. prl, 114 (9): 090502, 2015. arXiv: 1412.4687 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv: 1412.4687
[ 11 ] Dominic W. Berry, Andrew M. Childs y Robin Kothari. Simulación hamiltoniana con dependencia casi óptima de todos los parámetros. En focs56th, páginas 792–809, 2015. arXiv: 1501.01715 ?.
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
[ 12 ] Gilles Brassard, Peter Høyer, Michele Mosca y Alain Tapp. Amplificación cuántica amplificación y estimación. En Computación cuántica e información cuántica: A Millennium Volume, volumen 305 de Contemporary Mathematics Series, páginas 53–74. AMS, 2002. arXiv: quant-ph / 0005055 ?.
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[ 13 ] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore y Xiaodi Wu. Solucionadores Quantum SDP: grandes aceleraciones, optimización y aplicaciones para el aprendizaje cuántico. En icalp46th, páginas 27: 1–27: 14, 2019. arXiv: 1710.02581 ?.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
arXiv: 1710.02581
[ 14 ] Fernando GSL Brandão y Krysta M. Svore. Aceleraciones cuánticas para resolver programas semidefinidos. En focs58th, páginas 415–426, 2017. arXiv: 1609.05537 ?.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arXiv: 1609.05537
[ 15 ] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li y Xiaodi Wu. Algoritmos cuánticos y límites inferiores para la optimización convexa. cuántica, 4: 221, 2020. arXiv: 1809.01731 ?.
https://doi.org/10.22331/q-2020-01-13-221
arXiv: 1809.01731
[ 16 ] Richard Cleve, Artur Ekert, Chiara Macchiavello y Michele Mosca. Algoritmos cuánticos revisitados. rspa, 454 (1969): 339–354, 1998. arXiv: quant-ph / 9708016 ?.
https: / / doi.org/ 10.1098 / rspa.1998.0164
arXiv: quant-ph / 9708016
[ 17 ] Andrew M. Childs, Robin Kothari y Rolando D. Somma. Algoritmo cuántico para sistemas de ecuaciones lineales con dependencia exponencialmente mejorada de la precisión. siamjc, 46 (6): 1920–1950, 2017. arXiv: 1511.02306 ?.
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306
[ 18 ] Anirban Narayan Chowdhury y Rolando D. Somma. Algoritmos cuánticos para muestreo de Gibbs y estimación del tiempo de respuesta. qic, 17 (1 y 2): 41–64, 2017. arXiv: 1603.02940 ?.
https: / / doi.org/ 10.26421 / QIC17.1-2
arXiv: 1603.02940
[ 19 ] Andrew M. Childs y Nathan Wiebe. Simulación hamiltoniana mediante combinaciones lineales de operaciones unitarias. qic, 12 (11 y 12): 901–924, 2012. arXiv: 1202.5822 ?.
https: / / doi.org/ 10.26421 / QIC12.11-12
arXiv: 1202.5822
[ 20 ] George B. Dantzig. Maximización de una función lineal de variables sujetas a desigualdades lineales. En Análisis de actividad de producción y asignación, Monografía de la Comisión Cowles No. 13, páginas 339
–347. John Wiley & Sons Inc., Nueva York, NY, 1951.
[ 21 ] Christoph Dürr y Peter Høyer. Un algoritmo cuántico para encontrar el mínimo. arXiv: quant-ph / 9607014 ?, 1996.
arXiv: quant-ph / 9607014
[ 22 ] Christoph Dürr, Mark Heiligman, Peter Høyer y Mehdi Mhalla. Complejidad de consulta cuántica de algunos problemas gráficos. siamjc, 35 (6): 1310–1328, 2006. Versión anterior en ICALP'04. arXiv: quant-ph / 0401091 ?.
https: / / doi.org/ 10.1137 / 050644719
arXiv: quant-ph / 0401091
[ 23 ] Martin Grötschel, László Lovász y Alexander Schrijver. El método elipsoide y sus consecuencias en la optimización combinatoria. peine, 1 (2): 169-197, 1981.
https: / / doi.org/ 10.1007 / BF02579273
[ 24 ] Martin Grötschel, László Lovász y Alexander Schrijver. Algoritmos Geométricos y Optimización Combinatoria. Springer, 1988.
[ 25 ] Lov Grover y Terry Rudolph. Creación de superposiciones que corresponden a distribuciones de probabilidad integrables de manera eficiente. arXiv: quant-ph / 0208112 ?, 2002.
arXiv: quant-ph / 0208112
[ 26 ] Lov K. Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. En stoc28th, páginas 212–219, 1996. arXiv: quant-ph / 9605043 ?.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043
[ 27 ] András Gilyén, Yuan Su, Guang Hao Low y Nathan Wiebe. Transformación cuántica de valores singulares y más allá: mejoras exponenciales para la aritmética de matriz cuántica. En stoc51st, páginas 193–204, 2019. arXiv: 1806.01838 ?.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[ 28 ] Michel X. Goemans y David P. Williamson. Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacción utilizando programación semidefinida. jacm, 42 (6): 1115–1145, 1995. Versión anterior en STOC'94.
https: / / doi.org/ 10.1145 / 227683.227684
[ 29 ] Aram W. Harrow, Avinatan Hassidim y Seth Lloyd. Algoritmo cuántico para sistemas lineales de ecuaciones. prl, 103 (15): 150502, 2009. arXiv: 0811.3171 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[ 30 ] Shelby Kimmel. Límite adversario cuántico (superior). cjtcs, 2013: 4: 1–14, 2013. Versión anterior en ICALP'12. arXiv: 1101.0797 ?.
https: / / doi.org/ 10.4086 / cjtcs.2013.004
arXiv: 1101.0797
[ 31 ] Subhash Khot, Guy Kindler, Elchanan Mossel y Ryan O'Donnell. ¿Resultados óptimos de inaproximabilidad para MAX-CUT y otros CSP de 2 variables? siamjc, 37 (1): 319–357, 2007. Versión anterior en FOCS'04.
https: / / doi.org/ 10.1137 / S0097539705447372
[ 32 ] Iordanis Kerenidis y Anupam Prakash. Un método de punto interior cuántico para LP y SDP. arXiv: 1808.09266 ?, 2018.
arXiv: 1808.09266
[ 33 ] Guang Hao Low e Isaac L. Chuang. Simulación hamiltoniana óptima mediante procesamiento de señal cuántica. prl, 118 (1): 010501, 2017. arXiv: 1606.02685 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685
[ 34 ] Guang Hao Low e Isaac L. Chuang. Simulación hamiltoniana por qubitización. cuántica, 3: 163, 2019. arXiv: 1610.06546 ?.
https://doi.org/10.22331/q-2019-07-12-163
arXiv: 1610.06546
[ 35 ] Yin Tat Lee, Aaron Sidford y Sam Chiu-wai Wong. Un método de plano de corte más rápido y sus implicaciones para la optimización combinatoria y convexa. En focs56th, páginas 1049–1065, 2015. arXiv: 1508.04874 ?.
https: / / doi.org/ 10.1109 / FOCS.2015.68
arXiv: 1508.04874
[ 36 ] Michael A. Nielsen e Isaac L. Chuang. Cálculo cuántico e información cuántica. Cambridge University Press, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[ 37 ] Y. Nesterov y A. Nemirovski. Algoritmos polinómicos de punto interior en programación convexa, volumen 13 de Estudios SIAM en Matemática Aplicada. Sociedad de Matemáticas Industriales y Aplicadas (SIAM), 1994.
https: / / doi.org/ 10.1137 / 1.9781611970791
[ 38 ] David Poulin y Pawel Wocjan. Preparación de estados fundamentales de sistemas cuánticos de muchos cuerpos en una computadora cuántica. prl, 102 (13): 130503, 2009. arXiv: 0809.2705 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.102.130503
arXiv: 0809.2705
[ 39 ] David Poulin y Pawel Wocjan. Muestreo del estado de Gibbs cuántico térmico y evaluación de las funciones de partición con una computadora cuántica. prl, 103 (22): 220502, 2009. arXiv: 0905.2199 ?.
https: / / doi.org/ 10.1103 / PhysRevLett.103.220502
arXiv: 0905.2199
[ 40 ] James Renegar Métodos de gradiente "eficientes" para la optimización convexa general. siamjc, 26 (4): 2649–2676, 2016. arXiv: 1605.08712 ?.
https: / / doi.org/ 10.1137 / 15M1027371
arXiv: 1605.08712
[ 41 ] James Renegar Métodos acelerados de primer orden para la programación hiperbólica. Programación matemática, 173 (1): 1–35, 2019. arXiv: 1512.07569 ?.
https: / / doi.org/ 10.1007 / s10107-017-1203-y
arXiv: 1512.07569
[ 42 ] Alexander Schrijver. Teoría de la programación lineal y entera. John Wiley & Sons, Inc., Nueva York, NY, EE. UU., 1986.
[ 43 ] Peter W. Shor. Algoritmos de tiempo polinómico para factorización prima y logaritmos discretos en una computadora cuántica. siamjc, 26 (5): 1484–1509, 1997. Versión anterior en FOCS'94. arXiv: quant-ph / 9508027 ?.
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027
[ 44 ] Koji Tsuda, Gunnar Rätsch y Manfred K. Warmuth. Actualizaciones de gradiente exponenciadas de matriz para aprendizaje en línea y proyección de Bregman. Journal of Machine Learning Research, 6: 995–1018, 2005. Versión anterior en NIPS'04.
http: / / jmlr.csail.mit.edu/ papers / volume6 / tsuda05a / tsuda05a.pdf
[ 45 ] Manfred K. Warmuth y Dima Kuzmin. Minimización de varianza en línea. Machine Learning, 87 (1): 1–32, 2012. Versión anterior en COLT'06.
https://doi.org/10.1007/s10994-011-5269-0
Citado por
[1] András Gilyén, Yuan Su, Guang Hao Low y Nathan Wiebe, "Transformación cuántica del valor singular y más allá: mejoras exponenciales para la aritmética de matriz cuántica", arXiv: 1806.01838.
[2] 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 of London Serie A 474 2209, 20170551 (2018).
[3] Patrick Rebentrost y Seth Lloyd, "Finanzas computacionales cuánticas: algoritmo cuántico para la optimización de la cartera", arXiv: 1811.03975.
[4] Joran van Apeldoorn y András Gilyén, "Algoritmos cuánticos para juegos de suma cero", arXiv: 1904.03180.
[5] András Gilyén, Srinivasan Arunachalam y Nathan Wiebe, "Optimización de algoritmos de optimización cuántica a través de un cálculo de gradiente cuántico más rápido", arXiv: 1711.00465.
[6] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione y Seth Lloyd, "Descenso de gradiente cuántico y método de Newton para la optimización polinómica restringida", arXiv: 1612.01789.
[7] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore y Xiaodi Wu, "Solucionadores Quantum SDP: grandes velocidades, optimización y aplicaciones para el aprendizaje cuántico", arXiv: 1710.02581.
[8] Joran van Apeldoorn y András Gilyén, "Mejoras en la solución cuántica de SDP con aplicaciones", arXiv: 1804.05058.
[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin y Chunhao Wang, "Algoritmo clásico de tiempo sublineal inspirado en Quantum para resolver la programación semidefinida de bajo rango mediante enfoques de muestreo", arXiv: 1901.03254.
[10] Simon Apers, "Muestreo de caminata cuántica por conjuntos de semillas en crecimiento", arXiv: 1904.11446.
[11] Joran van Apeldoorn, András Gilyén, Sander Gribling y Ronald de Wolf, "Optimización convexa utilizando oráculos cuánticos", arXiv: 1809.00643.
[12] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li y Xiaodi Wu, "Algoritmos cuánticos y límites inferiores para la optimización convexa", arXiv: 1809.01731.
[13] Yimin Ge, Jordi Tura y J. Ignacio Cirac, "Preparación más rápida del estado del terreno y estimación de la energía del suelo de alta precisión con menos qubits", arXiv: 1712.03193.
[14] Ivan Bardet y Cambyse Rouzé, "Hipercontractividad y desigualdad logarítmica de Sobolev para semigrupos cuánticos de Markov no primitivos y estimación de tasas de decoherencia", arXiv: 1803.05379.
[15] Ashley Montanaro, "Aceleración cuántica de algoritmos de ramificación y unión", arXiv: 1906.10375.
[16] Johannes Bausch, Subramanian Sathyawageeswar, y Stephen Piddock, "Un decodificador de búsqueda cuántica para el procesamiento del lenguaje natural", arXiv: 1909.05023.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2020-02-14 09:28:14). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
No se pudo recuperar Crossref citado por datos durante el último intento 2020-02-14 09:28:13: No se pudieron obtener los datos citados por 10.22331 / q-2020-02-14-230 de Crossref. Esto es normal si el DOI se registró recientemente.
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.
Fuente: https://quantum-journal.org/papers/q-2020-02-14-230/
