Algoritmo cuántico de Goemans-Williamson con la prueba de Hadamard y restricciones de amplitud aproximada

Algoritmo cuántico de Goemans-Williamson con la prueba de Hadamard y restricciones de amplitud aproximada

Marca de tiempo: 12 de julio de 2023 8:29 a. M.

Taylor L. Patti1,2, Jean Kossaïfi2, Ánima Anandkumar3,2y Susanne F. Yelin1

1Departamento de Física, Universidad de Harvard, Cambridge, Massachusetts 02138, EE. UU.
2NVIDIA, Santa Clara, California 95051, EE. UU.
3Departamento de Computación + Ciencias Matemáticas (CMS), Instituto de Tecnología de California (Caltech), Pasadena, CA 91125 EE. UU.

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

Resumen

Los programas semidefinidos son métodos de optimización con una amplia gama de aplicaciones, como la aproximación a problemas combinatorios difíciles. Uno de estos programas semidefinidos es el algoritmo de Goemans-Williamson, una popular técnica de relajación de enteros. Presentamos un algoritmo cuántico variacional para el algoritmo de Goemans-Williamson que usa solo $n{+}1$ qubits, un número constante de preparaciones de circuitos y $text{poly}(n)$ valores esperados para resolver aproximadamente programas semidefinidos con hasta $N=2^n$ variables y $M sim O(N)$ restricciones. La optimización eficiente se logra mediante la codificación de la matriz objetivo como un unitario adecuadamente parametrizado condicionado en un qubit auxiliar, una técnica conocida como la Prueba de Hadamard. La prueba de Hadamard nos permite optimizar la función objetivo estimando solo un único valor esperado del ancilla qubit, en lugar de estimar por separado exponencialmente muchos valores esperados. De manera similar, ilustramos que las restricciones de programación semidefinida se pueden aplicar de manera efectiva implementando una segunda prueba de Hadamard, así como imponiendo un número polinomial de restricciones de amplitud de cadena de Pauli. Demostramos la efectividad de nuestro protocolo al diseñar una implementación cuántica eficiente del algoritmo Goemans-Williamson para varios problemas NP-difíciles, incluido MaxCut. Nuestro método supera el rendimiento de métodos clásicos análogos en un subconjunto diverso de problemas MaxCut bien estudiados de la biblioteca GSet.

Algoritmo cuántico de Goemans-Williamson con la prueba de Hadamard y restricciones de amplitud aproximada PlatoBlockchain Data Intelligence. Búsqueda vertical. Ai.

Imagen destacada: Diagrama de HTAAC-QSDP para el algoritmo Goemans-Williamson con $n=3$ qubits no auxiliares. a) Un problema clásico de $N$ variables (aquí un problema MaxCut de $N$-vértice donde $N=8$). La matriz de pesos $W$ se utiliza para generar el $U_W$ unitario. b) La prueba de Hadamard se utiliza para evaluar eficientemente la función objetivo y las restricciones de equilibrio de la población. El estado $n$-qubit $|psirangle = U_V|mathbf{0}rangle$ se prepara con un circuito cuántico variacional $U_V$. El qubit $n+1$ésimo (auxiliar) se inicializa como $(|0rangle -i |1rangle)/sqrt{2}$. Posteriormente, se realiza el Test de Hadamard: se implementa $U_W$ como condicionado unitario controlado sobre el qubit auxiliar, que luego se mide para calcular $langle sigma_{n+1} rangle_{W,t} = text{Im}[langle psi|U_W|psi rangle]$ o $langle sigma_{n+1} rangle_{P,t} = text{Im}[langle psi|U_P| rango psi]$. c) Las restricciones de amplitud $M=2^n$ SDP se imponen aproximadamente con solo restricciones de cadena $m sim text{poly}(n)$ Pauli. Estos se calculan recopilando medidas de $n$-qubit Pauli-$z$ y utilizando estadísticas marginales para estimar los valores esperados de $m$.

Resumen popular

Los programas semidefinidos nos permiten aproximarnos a una amplia gama de problemas difíciles, incluidos los problemas NP-difíciles. Uno de esos programas semidefinidos es el algoritmo Goemans-Williamson, que puede resolver problemas difíciles, como MaxCut. Presentamos un algoritmo cuántico variacional para el algoritmo de Goemans-Williamson que usa solo $n{+}1$ qubits, un número constante de preparaciones de circuitos y un número polinomial de valores esperados para resolver aproximadamente programas semidefinidos con un número exponencial de variables y restricciones. Codificamos el problema en un circuito cuántico (o unitario) y lo leemos en un solo qubit auxiliar, una técnica conocida como Prueba de Hadamard. De manera similar, ilustramos que las restricciones del problema se pueden aplicar mediante 1) una segunda prueba de Hadamard y 2) un número polinomial de restricciones de cadena de Pauli. Demostramos la efectividad de nuestro protocolo al diseñar una implementación cuántica eficiente del algoritmo Goemans-Williamson para varios problemas NP-difíciles, incluido MaxCut. Nuestro método supera el rendimiento de métodos clásicos análogos en un subconjunto diverso de problemas de MaxCut bien estudiados.

► datos BibTeX

► referencias

[ 1 ] Stephen P. Boyd y Lieven Vandenberghe. "Optimizacion convexa". Prensa de Cambridge. (2004).
https: / / doi.org/ 10.1017 / CBO9780511804441

[ 2 ] Michel X. Goemans. “Programación semidefinida en optimización combinatoria”. Programación matemática 79, 143–161 (1997).
https: / / doi.org/ 10.1007 / BF02614315

[ 3 ] Lieven Vandenberghe y Stephen Boyd. “Aplicaciones de la programación semidefinida”. Matemáticas numéricas aplicadas 29, 283–299 (1999).
https:/​/​doi.org/​10.1016/​S0168-9274(98)00098-1

[ 4 ] Wenjun Li, Yang Ding, Yongjie Yang, R. Simon Sherratt, Jong Hyuk Park y Jin Wang. “Algoritmos parametrizados de problemas fundamentales np-hard: una encuesta”. Ciencias de la información y computación centradas en el ser humano 10, 29 (2020).
https: / / doi.org/ 10.1186 / s13673-020-00226-w

[ 5 ] Cristóbal Helmberg. “Programación semidefinida para optimización combinatoria”. Konrad-Zuse-Zentrum fur Informationstechnik Berlín. (2000).
https: / / doi.org/ 10.1007 / BF02614315

[ 6 ] Michel X. Goemans y David P. Williamson. “Algoritmos de aproximación mejorados para problemas de máximo corte y satisfacibilidad usando programación semidefinida”. J. ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[ 7 ] Florian A. Potra y Stephen J. Wright. “Métodos del punto interior”. Revista de Matemática Computacional y Aplicada 124, 281–302 (2000).
https:/​/​doi.org/​10.1016/​S0377-0427(00)00433-7

[ 8 ] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan y Zhao Song. “Un método de punto interior más rápido para programación semidefinida”. En 2020, el 61.er simposio anual de IEEE sobre fundamentos de la informática (FOCS). Páginas 910–918. IEEE (2020).
https: / / doi.org/ 10.1109 / FOCS46700.2020.00089

[ 9 ] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao y Ruizhe Zhang. “Resolviendo sdp más rápido: un marco robusto de ipm e implementación eficiente”. En 2022, 63.º Simposio anual sobre fundamentos de la informática (FOCS) del IEEE. Páginas 233–244. IEEE (2022).
https: / / doi.org/ 10.1109 / FOCS54457.2022.00029

[ 10 ] David P. Williamson y David B. Shmoys. “El diseño de algoritmos de aproximación”. Prensa de la Universidad de Cambridge. (2011).
https: / / doi.org/ 10.1017 / CBO9780511921735

[ 11 ] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al. “Optimización cuántica utilizando algoritmos variacionales en dispositivos cuánticos a corto plazo”. Ciencia y tecnología cuántica 3, 030503 (2018).
https: / / doi.org/ 10.1088 / 2058-9565 / aab822

[ 12 ] Edward Farhi, Jeffrey Goldstone, Sam Gutmann y Michael Sipser. “Computación cuántica por evolución adiabática” (2000). arXiv:quant-ph/0001106.
arXiv: quant-ph / 0001106

[ 13 ] Tameem Albash y Daniel A. Lidar. “Computación cuántica adiabática”. Rev.Mod. física 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[ 14 ] Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, JG Liu, Rhine Samajdar, et al. “Optimización cuántica del conjunto máximo independiente utilizando arreglos atómicos de Rydberg”. Ciencia 376, 1209–1215 (2022).
https:/​/​doi.org/​10.1126/​science.abo6587

[ 15 ] Tadashi Kadowaki y Hidetoshi Nishimori. “Recocido cuántico en el modelo de ising transversal”. física Rev.E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[ 16 ] Elizabeth Gibney. "Actualización de onda D: cómo los científicos están utilizando la computadora cuántica más controvertida del mundo". Naturaleza 541 (2017).
https://​/​doi.org/​10.1038/​541447b

[ 17 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. “Un algoritmo de optimización cuántico aproximado”. arXiv (2014). arXiv:1411.4028.
https://​/​doi.org/​10.48550/​arXiv.1411.4028
arXiv: 1411.4028

[ 18 ] Juan M Arrazola, Ville Bergholm, Kamil Brádler, Thomas R Bromley, Matt J Collins, Ish Dhand, Alberto Fumagalli, Thomas Gerrits, Andrey Goussev, Lukas G Helt, et al. “Circuitos cuánticos con muchos fotones en un chip nanofotónico programable”. Naturaleza 591, 54–60 (2021).
https:/​/​doi.org/​10.1038/​s41586-021-03202-1

[ 19 ] 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". 46 ° Coloquio internacional sobre autómatas, lenguajes y programación (ICALP 2019) 132, 27: 1–27: 14 (2019).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27

[ 20 ] Joran Van Apeldoorn y András Gilyén. "Mejoras en la resolución cuántica de sdp con aplicaciones". En Actas del 46º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (2019).
https: / / doi.org/ 10.4230 / LIPICS.ICALP.2019.99

[ 21 ] Joran van Apeldoorn, Andràs Gilyèn, Sander Gribling y Ronald de Wolf. “Solvers de sdp cuánticos: mejores límites superior e inferior”. Cuántica 4, 230 (2020).
https:/​/​doi.org/​10.22331/​q-2020-02-14-230

[ 22 ] Fernando GSL Brandão y Krysta M. Svore. “Aceleradores cuánticos para la resolución de programas semidefinidos”. En 2017, 58.º Simposio anual sobre fundamentos de la informática (FOCS) del IEEE. Páginas 415–426. (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.45

[ 23 ] Fernando GS L. Brandão, Richard Kueng y Daniel Stilck França. “Aproximaciones SDP clásicas y cuánticas más rápidas para la optimización binaria cuadrática”. Cuántica 6, 625 (2022).
https:/​/​doi.org/​10.22331/​q-2022-01-20-625

[ 24 ] Dhrumil Patel, Patrick J. Coles y Mark M. Wilde. “Algoritmos cuánticos variacionales para programación semidefinida” (2021). arXiv:2112.08859.
arXiv: 2112.08859

[ 25 ] Anirban N. Chowdhury, Guang Hao Low y Nathan Wiebe. “Un algoritmo cuántico variacional para preparar estados cuánticos de gibbs” (2020). arXiv:2002.00055.
arXiv: 2002.00055

[ 26 ] Taylor L Patti, Omar Shehab, Khadijeh Najafi y Susanne F Yelin. "Algoritmos cuánticos variacionales mejorados Monte Carlo de la cadena de Markov". Ciencia y Tecnología Cuántica 8, 015019 (2022).
https:/​/​doi.org/​10.1088/​2058-9565/​aca821

[ 27 ] Youle Wang, Guangxi Li y Xin Wang. “Preparación del estado de Gibbs cuántico variacional con una serie de Taylor truncada”. Revisión Física Aplicada 16, 054035 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054035

[ 28 ] Sanjeev Arora, Elad Hazan y Satyen Kale. “El método de actualización de pesos multiplicativos: un meta-algoritmo y aplicaciones”. Teoría de la Computación 8, 121–164 (2012).
https: / / doi.org/ 10.4086 / toc.2012.v008a006

[ 29 ] Iordanis Kerenidis y Anupam Prakash. “Un método de punto interior cuántico para lps y sdps”. Transacciones de ACM en computación cuántica 1 (2020).
https: / / doi.org/ 10.1145 / 3406306

[ 30 ] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky y Luis F. Zuluaga. “Métodos cuánticos de puntos interiores para optimización semidefinida” (2022). arXiv:2112.06025.
arXiv: 2112.06025

[ 31 ] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio y Patrick J. Coles. “Algoritmos cuánticos variacionales”. Nature Reviews Physics 3, 625–644 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[ 32 ] Kishor Bharti, Tobias Haug, Vlatko Vedral y Leong-Chuan Kwek. “Algoritmo cuántico ruidoso de escala intermedia para programación semidefinida”. física Rev. A 105, 052445 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.052445

[ 33 ] Lennart Bittel y Martin Kliesch. "Entrenar algoritmos cuánticos variacionales es np-difícil". física Rev. Lett. 127, 120502 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.120502

[ 34 ] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush y Hartmut Neven. “Mesetas estériles en paisajes de entrenamiento de redes neuronales cuánticas”. Comunicaciones de la naturaleza 9, 4812 (2018).
https:/​/​doi.org/​10.1038/​s41467-018-07090-4

[ 35 ] Carlos Ortiz Marrero, Mária Kieferová y Nathan Wiebe. “Mesetas estériles inducidas por enredos”. PRX Quantum 2, 040316 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.040316

[ 36 ] Taylor L. Patti, Khadijeh Najafi, Xun Gao y Susanne F. Yelin. “Mitigación de meseta estéril ideada por enredos”. física Res. Rev. 3, 033090 (2021).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033090

[ 37 ] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger y Patrick J. Coles. “Ausencia de mesetas estériles en redes neuronales convolucionales cuánticas”. física Rev. X 11, 041011 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.041011

[ 38 ] Dorit Aharonov, Vaughan Jones y Zeph Landau. “Un algoritmo cuántico polinomial para aproximar el polinomio de Jones”. Algorítmica 55, 395–421 (2009).
https:/​/​doi.org/​10.1007/​s00453-008-9168-0

[ 39 ] Clayton W. Comandante. “Problema de corte máximo, max-cutproblema de corte máximo, max-cut”. Páginas 1991–1999. Springer Estados Unidos. Boston, MA (2009).
https:/​/​doi.org/​10.1007/​978-0-387-74759-0_358

[ 40 ] Steven J. Benson, Yinyu Yeb y Xiong Zhang. “Programación mixta lineal y semidefinida para optimización combinatoria y cuadrática”. Métodos de optimización y software 11, 515–544 (1999).
https: / / doi.org/ 10.1080 / 10556789908805761

[ 41 ] Changhui Choi y Yinyu Ye. “Resolver programas semidefinidos dispersos utilizando el algoritmo de escala dual con un solucionador iterativo”. Manuscrito, Departamento de Ciencias Administrativas, Universidad de Iowa, Iowa City, IA 52242 (2000). URL: web.stanford.edu/​yyye/​yyye/​cgsdp1.pdf.
https:/​/​web.stanford.edu/​~yyye/​yyye/​cgsdp1.pdf

[ 42 ] Angélica Wiegele. "Biblioteca Biq mac: una colección de instancias de programación cuadráticas 0-1 y de corte máximo de tamaño mediano". Alpen-Adria-Universität Klagenfurt (2007). URL: biqmac.aau.at/​biqmaclib.pdf.
https://​/​biqmac.aau.at/​biqmaclib.pdf

[ 43 ] Stefan H. Schmieta. “La biblioteca dimacs de programas mixtos semidefinidos-cuadráticos-lineales”. 7º Desafío de Implementación DIMACS (2007). URL: http:/​/​archive.dimacs.rutgers.edu.
http://archive.dimacs.rutgers.edu

[ 44 ] Yoshiki Matsuda. “Evaluación comparativa del problema de corte máximo en la máquina de bifurcación simulada”. Medio (2019). url: medium.com/​toshiba-sbm/​benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0.
https:/​/​medium.com/​toshiba-sbm/​evaluación comparativa del problema de corte máximo en la máquina de bifurcación simulada e26e1127c0b0

[ 45 ] RM Karpe. “Reducibilidad entre problemas combinatorios”. Springer Estados Unidos. Boston, MA (1972).

[ 46 ] Dimitri P Bertsekas. “Métodos de optimización restringida y multiplicador de lagrange”. Prensa académica. (mil novecientos ochenta y dos).
https:/​/​doi.org/​10.1016/​C2013-0-10366-2

[ 47 ] G Mauro D'Ariano, Matteo GA Paris y Massimiliano F Sacchi. “Tomografía cuántica”. Avances en imágenes y física de electrones 128, 206–309 (2003).
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0302028
arXiv: quant-ph / 0302028

[ 48 ] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini y Paolo Perinotti. “Tomografía cuántica óptima”. Revista IEEE de temas seleccionados en electrónica cuántica 15, 1646–1660 (2009).
https: / / doi.org/ 10.1109 / JSTQE.2009.2029243

[ 49 ] Max S. Kaznady y Daniel FV James. “Estrategias numéricas para tomografía cuántica: alternativas a la optimización total”. física Rev. A 79, 022109 (2009).
https: / / doi.org/ 10.1103 / PhysRevA.79.022109

[ 50 ] Javier Peña. “Convergencia de métodos de primer orden a través del conjugado convexo”. Cartas de investigación de operaciones 45, 561–564 (2017).
https: / / doi.org/ 10.1016 / j.orl.2017.08.013

[ 51 ] Alan Frieze y Mark Jerrum. “Algoritmos de aproximación mejorados para maxk-cut y max bisection”. Algorítmica 18, 67–81 (1997).
https: / / doi.org/ 10.1007 / BF02523688

[ 52 ] Clark David Thompson. “Una teoría de la complejidad para vlsi”. Tesis doctoral. Universidad de Carnegie mellon. (1980). URL: dl.acm.org/​doi/​10.5555/​909758.
https: / / dl.acm.org/ doi / 10.5555 / 909758

[ 53 ] Chu Min Li y Felip Manya. “Maxsat, restricciones duras y blandas”. En Manual de satisfacibilidad. Páginas 903–927. Prensa IOS (2021).
https:/​/​doi.org/​10.3233/​978-1-58603-929-5-613

[ 54 ] Nicolás J Higham. "Cálculo de la matriz de correlación más cercana: un problema de finanzas". Revista IMA de análisis numérico 22, 329–343 (2002).
https:/​/​doi.org/​10.1093/​imanum/​22.3.329

[ 55 ] Tadayoshi Fushiki. “Estimación de matrices de correlación semidefinidas positivas mediante programación semidefinida cuadrática convexa”. Computación neuronal 21, 2028–2048 (2009).
https://​/​doi.org/​10.1162/​neco.2009.04-08-765

[ 56 ] Todd MJ. "Un estudio de direcciones de búsqueda en métodos de punto interior primal-dual para programación semidefinida". Métodos de optimización y software 11, 1–46 (1999).
https: / / doi.org/ 10.1080 / 10556789908805745

[ 57 ] Roger Fletcher. “Funciones de penalización”. Programación matemática El estado del arte: Bonn 1982 Páginas 87–114 (1983).
https:/​/​doi.org/​10.1007/​978-3-642-68874-4_5

[ 58 ] Roberto M Freund. “Métodos de penalización y barrera para la optimización restringida”. Apuntes de conferencias, Instituto de Tecnología de Massachusetts (2004). URL: ocw.mit.edu/​courses/​15-084j-nonlinear-programming-spring-2004.
https:/​/​ocw.mit.edu/​courses/​15-084j-nonlinear-programming-spring-2004

[ 59 ] Eric Ricardo Anschuetz. “Puntos críticos en modelos generativos cuánticos”. En Congreso Internacional de Representaciones de Aprendizaje. (2022). URL: openreview.net/forum?id=2f1z55GVQN.
https://​/​openreview.net/​forum?id=2f1z55GVQN

[ 60 ] Amir Beck. “Métodos de primer orden en optimización”. SIAM. (2017).
https: / / doi.org/ 10.1137 / 1.9781611974997

[ 61 ] Sanjeev Arora y Satyen Kale. “Un enfoque combinatorio primal-dual de los programas semidefinidos”. J. ACM 63 (2016).
https: / / doi.org/ 10.1145 / 2837020

[ 62 ] Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin y Anima Anandkumar. “Tensorly-quantum: aprendizaje automático cuántico con métodos tensoriales” (2021). arXiv:2112.10239.
arXiv: 2112.10239

[ 63 ] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar y Maja Pantic. “Tensorly: aprendizaje de tensores en python”. Revista de investigación de aprendizaje automático 20, 1–6 (2019). URL: http:/​/​jmlr.org/​papers/​v20/​18-277.html.
http: / / jmlr.org/ papers / v20 ​​/ 18-277.html

[ 64 ] Equipo cuQuantum. “Nvidia/​cuquantum: cuquantum v22.11” (2022).

[ 65 ] Diederik P. Kingma y Jimmy Ba. “Adam: Un método para la optimización estocástica” (2017). arXiv:1412.6980.
arXiv: 1412.6980

[ 66 ] Brahim Chaourar. “Un algoritmo de tiempo lineal para una variante del problema de corte máximo en gráficos serie paralelos”. Avances en Investigación Operativa (2017).
https: / / doi.org/ 10.1155 / 2017/1267108

[ 67 ] Yuri Makarychev. "Una breve prueba del criterio de planaridad del gráfico de Kuratowski". Revista de teoría de grafos 25, 129–131 (1997).
<a href="https://doi.org/10.1002/(SICI)1097-0118(199706)25:23.0.CO;2-O”>https:/​/​doi.org/​10.1002/​(SICI)1097-0118(199706)25:2<129::AID-JGT4>3.0.CO;2-O

[ 68 ] Bela Bollobas. "La evolución de los gráficos aleatorios: el componente gigante". Página 130–159. Estudios de Cambridge en Matemáticas Avanzadas. Prensa de la Universidad de Cambridge. (2001). 2 edición.
https: / / doi.org/ 10.1017 / CBO9780511814068.008

[ 69 ] Sanjeev Arora, David Karger y Marek Karpinski. "Esquemas de aproximación de tiempo polinomial para instancias densas de problemas np-hard". Revista de ciencias informáticas y de sistemas 58, 193–210 (1999).
https: / / doi.org/ 10.1006 / jcss.1998.1605

[ 70 ] Rick Durret. "Gráficos aleatorios de Erdös-rényi". Página 27–69. Serie de Cambridge en Matemáticas Estadísticas y Probabilísticas. Prensa de la Universidad de Cambridge. (2006).
https: / / doi.org/ 10.1017 / CBO9780511546594.003

[ 71 ] Gary Chartrand y Ping Zhang. “Teoría de grafos cromáticos”. Taylor y Francisco. (2008).
https: / / doi.org/ 10.1201 / 9781584888017

[ 72 ] John van de Wetering. “Cálculo Zx para el científico informático cuántico en activo” (2020). arXiv:2012.13966.
arXiv: 2012.13966

[ 73 ] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons y Seyon Sivarajah. “Síntesis de dispositivos de fase para circuitos poco profundos”. Procedimientos electrónicos en informática teórica 318, 213–228 (2020).
https: / / doi.org/ 10.4204 / eptcs.318.13

[ 74 ] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe y Shuchen Zhu. “Teoría del error del trotón con escalado del conmutador”. física Rev. X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[ 75 ] Joseph W Britton, Brian C Sawyer, Adam C Keith, CC Joseph Wang, James K Freericks, Hermann Uys, Michael J Biercuk y John J Bollinger. "Interacciones de ising bidimensionales diseñadas en un simulador cuántico de iones atrapados con cientos de espines". Naturaleza 484, 489–492 (2012).
https: / / doi.org/ 10.1038 / nature10981

[ 76 ] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner, et al. “Probando la dinámica de muchos cuerpos en un simulador cuántico de 51 átomos”. Naturaleza 551, 579–584 (2017).
https: / / doi.org/ 10.1038 / nature24622

[ 77 ] Gheorghe-Sorin Paraoanu. “Progresos recientes en la simulación cuántica utilizando circuitos superconductores”. Revista de Física de Baja Temperatura 175, 633–654 (2014).
https:/​/​doi.org/​10.1007/​s10909-014-1175-8

[ 78 ] Katsuki Fujisawa, Hitoshi Sato, Satoshi Matsuoka, Toshio Endo, Makoto Yamashita y Maho Nakata. “Solucionador general de alto rendimiento para problemas de programación semidefinidos de escala extremadamente grande”. En SC '12: Actas de la Conferencia internacional sobre informática, redes, almacenamiento y análisis de alto rendimiento. Páginas 1–11. (2012).
https: / / doi.org/ 10.1109 / SC.2012.67

[ 79 ] Adrian S. Lewis y Michael L. Overton. “Optimización de valores propios”. Acta Numerica 5, 149–190 (1996).
https: / / doi.org/ 10.1017 / S0962492900002646

[ 80 ] Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin y Xiao Yuan. “Algoritmos variacionales para álgebra lineal”. Boletín científico 66, 2181–2188 (2021).
https: / / doi.org/ 10.1016 / j.scib.2021.06.023

Citado por

No se pudo recuperar Crossref citado por datos durante el último intento 2023-07-12 14:07:40: No se pudieron obtener los datos citados por 10.22331 / q-2023-07-12-1057 de Crossref. Esto es normal si el DOI se registró recientemente. En ANUNCIOS SAO / NASA no se encontraron datos sobre las obras citadas (último intento 2023-07-12 14:07:40).

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.

Sello de tiempo:

Mas de Diario cuántico