Búsqueda adaptativa de Grover para optimización binaria polinomial restringida

Sello de tiempo: 8 de abril de 2021 10:04 a. M.
Nodo de origen: 806213

Austin Gilliam1, Stefan Woerner2y Constantino Gonciulea1

1JPMorgan Chase
2IBM Quantum, IBM Research - Zúrich

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

Resumen

En este artículo discutimos Grover Adaptive Search (GAS) para problemas de optimización binaria polinomial restringida (CPBO) y, en particular, problemas de optimización binaria cuadrática no restringida (QUBO), como un caso especial. GAS puede proporcionar una aceleración cuadrática para problemas de optimización combinatoria en comparación con la búsqueda de fuerza bruta. Sin embargo, esto requiere el desarrollo de oráculos eficientes para representar problemas y estados de bandera que satisfagan ciertos criterios de búsqueda. En general, esto se puede lograr usando aritmética cuántica, sin embargo, esto es costoso en términos de puertas de Toffoli, así como de qubits de ancilla requeridos, que pueden ser prohibitivos a corto plazo. Dentro de este trabajo, desarrollamos una forma de construir oráculos eficientes para resolver problemas de CPBO utilizando algoritmos GAS. Demostramos este enfoque y la posible aceleración del problema de optimización de la cartera, es decir, un QUBO, utilizando simulación y resultados experimentales obtenidos en hardware cuántico real. Sin embargo, nuestro enfoque se aplica a funciones objetivo polinomiales de mayor grado, así como a problemas de optimización restringidos.

Imagen destacada: Las probabilidades de salida de GAS para dos iteraciones se ejecutan en hardware cuántico real, con los respectivos umbrales $ y $ y $ r $ aplicaciones del operador Grover. Los resultados de medición válidos se muestran en azul, mientras que los resultados de medición no válidos se muestran en gris.

Resumen popular

En este artículo discutimos Grover Adaptive Search (GAS) para problemas de optimización binaria polinomial restringida (CPBO) y, en particular, problemas de optimización binaria cuadrática no restringida (QUBO), como un caso especial. GAS puede proporcionar una aceleración cuadrática para problemas de optimización combinatoria en comparación con la búsqueda de fuerza bruta. Sin embargo, esto requiere el desarrollo de oráculos eficientes para representar problemas y estados de bandera que satisfagan ciertos criterios de búsqueda. En general, esto se puede lograr usando aritmética cuántica, sin embargo, esto es costoso en términos de puertas de Toffoli, así como de qubits de ancilla requeridos, que pueden ser prohibitivos a corto plazo. Dentro de este trabajo, desarrollamos una forma de construir oráculos eficientes para resolver problemas de CPBO utilizando algoritmos GAS. Demostramos este enfoque y la posible aceleración del problema de optimización de la cartera, es decir, un QUBO, utilizando simulación y resultados experimentales obtenidos en hardware cuántico real. Sin embargo, nuestro enfoque se aplica a funciones objetivo polinomiales de mayor grado, así como a problemas de optimización restringidos.

► datos BibTeX

► referencias

[ 1 ] Lov K. Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. En Actas del vigésimo octavo simposio anual de ACM sobre teoría de la computación, STOC '96, páginas 212–219, Nueva York, NY, EE. UU., 1996. ACM. ISBN 0-89791-785-5. 10.1145 / 237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866

[ 2 ] Peter W. Shor. Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica. SIAM Journal on Computing, 26 (5): 1484-1509, octubre de 1997. ISSN 1095-7111. 10.1137 / s0097539795293172.
https: / / doi.org/ 10.1137 / s0097539795293172

[ 3 ] BP Lanyon, JD Whitfield, GG Gillett, ME Goggin, MP Almeida, I. Kassal, JD Biamonte, M. Mohseni, BJ Powell, M. Barbieri y col. Hacia la química cuántica en una computadora cuántica. Nature Chemistry, 2 (2): 106-111, enero de 2010. ISSN 1755-4349. 10.1038 / nchem.483.
https: / / doi.org/ 10.1038 / nchem.483

[ 4 ] Aram W. Harrow, Avinatan Hassidim y Seth Lloyd. Algoritmo cuántico para sistemas lineales de ecuaciones. Physical Review Letters, 103 (15), octubre de 2009. ISSN 1079-7114. 10.1103 / physrevlett.103.150502.
https: / / doi.org/ 10.1103 / physrevlett.103.150502

[ 5 ] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio y Patrick J. Coles. Solucionador lineal cuántico variacional, 2020. URL https: / / arxiv.org/ abs / 1909.05820.
arXiv: 1909.05820

[ 6 ] Patrick Rebentrost, Brajesh Gupt y Thomas R. Bromley. Finanzas computacionales cuánticas: fijación de precios Monte carlo de derivados financieros. Phys. Rev. A, 98: 022321, agosto de 2018. 10.1103 / PhysRevA.98.022321.
https: / / doi.org/ 10.1103 / PhysRevA.98.022321

[ 7 ] Stefan Woerner y Daniel J. Egger. Análisis de riesgo cuántico. npj Quantum Information, 5:15, 2019. 10.1038 / s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[ 8 ] DJ Egger, R. García Gutiérrez, J. Cahue Mestre y S. Woerner. Análisis de riesgo crediticio mediante computadoras cuánticas. Transacciones IEEE en computadoras, páginas 1–1, 2020. 10.1109 / TC.2020.3038063.
https: / / doi.org/ 10.1109 / TC.2020.3038063

[ 9 ] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen y Stefan Woerner. Fijación de precios de opciones utilizando computadoras cuánticas. Quantum, 4: 291, julio de 2020. ISSN 2521-327X. 10.22331 / q-2020-07-06-291.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

[ 10 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. Un algoritmo de optimización aproximada cuántica, 2014. URL https: / / arxiv.org/ abs / 1411.4028.
arXiv: 1411.4028

[ 11 ] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man Hong Yung, Xiao Qi Zhou, Peter J. Love, Alán Aspuru-Guzik y Jeremy L. O'Brien. Un solucionador de valores propios variacionales en un procesador cuántico fotónico. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038 / ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213

[ 12 ] Giacomo Nannicini. Rendimiento de la heurística variacional cuántica clásica híbrida para la optimización combinatoria. Physical Review E, 99: 013304, enero de 2019. 10.1103 / PhysRevE.99.013304.
https: / / doi.org/ 10.1103 / PhysRevE.99.013304

[ 13 ] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli y Stefan Woerner. Mejora de la optimización cuántica variacional mediante cvar. Quantum, 4: 256, abril de 2020. ISSN 2521-327X. 10.22331 / q-2020-04-20-256.
https:/​/​doi.org/​10.22331/​q-2020-04-20-256

[ 14 ] L. Braine, DJ Egger, J. Glick y S. Woerner. Algoritmos cuánticos para optimización binaria mixta aplicados a la liquidación de transacciones. Transacciones IEEE sobre ingeniería cuántica, 2: 1–8, 2021. 10.1109 / TQE.2021.3063635.
https: / / doi.org/ 10.1109 / TQE.2021.3063635

[ 15 ] Andrew M. Childs, Edward Farhi y John Preskill. Robustez de la computación cuántica adiabática. Physical Review A, 65 (1): 012322, 2001. 10.1103 / PhysRevA.65.012322.
https: / / doi.org/ 10.1103 / PhysRevA.65.012322

[ 16 ] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Recocido cuántico con espines fabricados. Nature, 473 (7346): 194-198, 2011. 10.1038 / nature10012.
https: / / doi.org/ 10.1038 / nature10012

[ 17 ] Christoph Dürr y Peter Høyer. Un algoritmo cuántico para encontrar el mínimo, 1996. URL https: / / arxiv.org/ abs / quant-ph / 9607014.
arXiv: quant-ph / 9607014

[ 18 ] D. Bulger, WP Baritompa y GR Wood. Implementación de búsqueda adaptativa pura con el algoritmo cuántico de grover. Journal of Optimization Theory and Applications, 116 (3): 517–529, marzo de 2003. ISSN 1573-2878. 10.1023 / A: 1023061218864.
https: / / doi.org/ 10.1023 / A: 1023061218864

[ 19 ] WP Baritompa, DW Bulger y GR Wood. El algoritmo cuántico de Grover aplicado a la optimización global. SIAM J. on Optimization, 15 (4): 1170-1184, abril de 2005. ISSN 1052-6234. 10.1137 / 040605072.
https: / / doi.org/ 10.1137 / 040605072

[ 20 ] Austin Gilliam, Charlene Venci, Sreraman Muralidharan, Vitaliy Dorum, Eric May, Rajesh Narasimhan y Constantin Gonciulea. Patrones fundamentales para la computación cuántica eficiente, 2019. URL https: / / arxiv.org/ abs / 1907.11513.
arXiv: 1907.11513

[ 21 ] Thomas G. Draper. Adición en una computadora cuántica, 2000. URL https: / / arxiv.org/ abs / quant-ph / 0008033.
arXiv: quant-ph / 0008033

[ 22 ] Román Orús, Samuel Mugel y Enrique Lizaso. Computación cuántica para las finanzas: descripción general y perspectivas. Reviews in Physics, 4: 100028, noviembre de 2019. ISSN 2405-4283. 10.1016 / j.revip.2019.100028.
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[ 23 ] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner y Elena Yndurain. Computación cuántica para las finanzas: estado de la técnica y perspectivas de futuro. Transacciones IEEE sobre ingeniería cuántica, 1: 1–24, 2020a. ISSN 2689-1808. 10.1109 / tqe.2020.3030314.
https: / / doi.org/ 10.1109 / tqe.2020.3030314

[ 24 ] Patrick Rebentrost y Seth Lloyd. Finanzas computacionales cuánticas: algoritmo cuántico para la optimización de carteras, 2018. URL https: / / arxiv.org/ abs / 1811.03975.
arXiv: 1811.03975

[ 25 ] Davide Venturelli y Alexei Kondratyev. Enfoque de recocido cuántico inverso para problemas de optimización de carteras. Inteligencia de la máquina cuántica, 1, 2019. 10.1007 / s42484-019-00001-w.
https: / / doi.org/ 10.1007 / s42484-019-00001-w

[ 26 ] Daniel J. Egger, Jakub Marecek y Stefan Woerner. Optimización cuántica de arranque en caliente, 2020b. URL https: / / arxiv.org/ abs / 2009.10095.
arXiv: 2009.10095

[ 27 ] Héctor Abraham et. Alabama. Qiskit: un marco de código abierto para la computación cuántica. 2019. 10.5281 / zenodo.2562110.
https: / / doi.org/ 10.5281 / zenodo.2562110

[ 28 ] Michele Mosca. Búsqueda cuántica, recuento y amplificación de amplitud mediante análisis de vector propio. En Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, páginas 90–100, 1998. URL https: / / eccc.weizmann.ac.il/ / resources / pdf / moscafi.pdf.
https: / / eccc.weizmann.ac.il/ / resources / pdf / moscafi.pdf

[ 29 ] Gilles Brassard, Peter Hoyer, Michele Mosca y Alain Tapp. Amplificación y estimación de amplitud cuántica. Contemporary Mathematics, 305, 2002. 10.1090 / conm / 305.
https: / / doi.org/ 10.1090 / conm / 305

[ 30 ] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera y Naoki Yamamoto. Estimación de amplitud sin estimación de fase. Procesamiento de información cuántica, 19 (2), enero de 2020. ISSN 1573-1332. 10.1007 / s11128-019-2565-2.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

[ 31 ] Scott Aaronson y Patrick Rall. Conteo aproximado cuántico, simplificado. Simposio sobre simplicidad en algoritmos, páginas 24–32, enero de 2020. 10.1137 / 1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[ 32 ] Michel Boyer, Gilles Brassard, Peter Høyer y Alain Tapp. Límites estrictos en la búsqueda cuántica. Fortschritte der Physik, 46 (4-5): 493–505, junio de 1998. ISSN 1521-3978. 10.1002 / (SICI) 1521-3978 (199806) 46: 4/5 <493 :: AID-PROP493> 3.0.CO; 2-P.
[ 33 ] Benjamín Barán y Marcos Villagra. Optimización multiobjetivo Grover Adaptive Search, páginas 191–211. Springer International Publishing, Cham, 2019. ISBN 978-3-319-99648-6. 10.1007 / 978-3-319-99648-6_11.
https:/​/​doi.org/​10.1007/​978-3-319-99648-6_11

[ 34 ] Yunseong Nam, Yuan Su y Dmitri Maslov. Transformada cuántica de Fourier aproximada con puertas o (n log (n)) t. npj Quantum Information, 6 (1), marzo de 2020. ISSN 2056-6387. 10.1038 / s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[ 35 ] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin y David Petrie Moulton. Un nuevo circuito de adición de transporte de ondas cuánticas, 2004. URL https: / / arxiv.org/ abs / quant-ph / 0410184.
arXiv: quant-ph / 0410184

[ 36 ] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains y Krysta M. Svore. Un sumador de avance cuántico de profundidad logarítmica. Información cuántica. Comput., 6 (4): 351–369, julio de 2006. ISSN 1533-7146. 10.26421 / QIC6.4-5-4.
https: / / doi.org/ 10.26421 / QIC6.4-5-4

[ 37 ] Craig Gidney. Reducir a la mitad el costo de la adición cuántica. Quantum, 2:74, junio de 2018. ISSN 2521-327X. 10.22331 / q-2018-06-18-74.
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[ 38 ] Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation y Jay M. Gambetta. Validación de computadoras cuánticas utilizando circuitos modelo aleatorios. Physical Review A, 100 (3), septiembre de 2019. ISSN 2469-9934. 10.1103 / physreva.100.032328.
https: / / doi.org/ 10.1103 / physreva.100.032328

[ 39 ] A. Dewes, FR Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion y D. Esteve. Caracterización de un procesador de dos transmon con lectura individual de qubit de un solo disparo. Phys. Rev. Lett., 108: 057002, febrero de 2012. 10.1103 / PhysRevLett.108.057002.
https: / / doi.org/ 10.1103 / PhysRevLett.108.057002

[ 40 ] Svante Janson. Momentos de tipo gamma y el área del proceso superior browniano. Probab. Encuestas, 7: 1–52, 2010. 10.1214 / 10-PS160.
https: / / doi.org/ 10.1214 / 10-PS160

[ 41 ] Michael A. Nielsen e Isaac L. Chuang. Computación cuántica e información cuántica: Edición del décimo aniversario. Cambridge University Press, Nueva York, NY, EE. UU., Décima edición, 10. ISBN 10, 2011. 1107002176 / CBO9781107002173.
https: / / doi.org/ 10.1017 / CBO9780511976667

Citado por

[1] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner y Elena Yndurain, "Computación cuántica para las finanzas: estado del arte y perspectivas futuras", arXiv: 2006.14510.

[2] Claudio Gambella y Andrea Simonetto, "Heurística ADMM multibloque para la optimización binaria mixta en computadoras clásicas y cuánticas", arXiv: 2001.02069.

[3] Austin Gilliam, Marco Pistoia y Constantin Gonciulea, "Optimización de la búsqueda cuántica mediante una versión generalizada del algoritmo de Grover", arXiv: 2005.06468.

[4] Austin Gilliam, Marco Pistoia y Constantin Gonciulea, "Construcción canónica de oráculos cuánticos", arXiv: 2006.10656.

[5] Austin Gilliam, Marco Pistoia y Constantin Gonciulea, "Optimización de la búsqueda cuántica con una versión binomial del algoritmo de Grover", arXiv: 2007.10894.

[6] Julien Gacon, Christa Zoufal, Giuseppe Carleo y Stefan Woerner, "Aproximación estocástica de perturbación simultánea de la información de Quantum Fisher", arXiv: 2103.09232.

[7] Sayantan Pramanik, M Girish Chandra, Shampa Sarkar y Manoj Nambiar, "Búsqueda de fase aproximada y estimación propia mediante el algoritmo de Grover modificado", arXiv: 2012.11497.

[8] Su Yeon Chang, Steven Herbert, Sofia Vallecorsa, Elías F. Combarro y Ross Duncan, “Modelo GAN de circuito cuántico de doble parámetro en física de altas energías”, arXiv: 2103.15470.

[9] Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini y Göran Johansson, "Un método heurístico para resolver programas lineales enteros a gran escala mediante la combinación de rama y precio con un algoritmo cuántico", arXiv: 2103.15433.

[10] Yidong Liao, Min-Hsiu Hsieh y Chris Ferrie, "Optimización cuántica para entrenar redes neuronales cuánticas", arXiv: 2103.17047.

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2021-04-10 02:42:05). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.

On Servicio citado por Crossref no se encontraron datos sobre las obras citadas (último intento 2021-04-10 02:42:03).

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-2021-04-08-428/

Sello de tiempo:

Mas de Diario cuántico