Un algoritmo de aproximación mejorado para Quantum Max-Cut en gráficos sin triángulos

Un algoritmo de aproximación mejorado para Quantum Max-Cut en gráficos sin triángulos

Marca de tiempo: 9 de noviembre de 2023 6:44 a. M.

robbie rey

Departamento de Computación y Ciencias Matemáticas, Caltech

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

Resumen

Damos un algoritmo de aproximación para Quantum Max-Cut que funciona redondeando una relajación SDP a un estado cuántico entrelazado. El SDP se utiliza para elegir los parámetros de un circuito cuántico variacional. El estado entrelazado se representa entonces como el circuito cuántico aplicado a un estado de producto. Logra una relación de aproximación de 0.582 en gráficos sin triángulos. Los mejores algoritmos anteriores de Anshu, Gosset, Morenz y Parekh, Thompson lograron relaciones de aproximación de 0.531 y 0.533 respectivamente. Además, estudiamos el hamiltoniano EPR, que, según creemos, es un problema intermedio natural que aísla algunas características cuánticas clave de los problemas hamiltonianos locales. Para el hamiltoniano EPR, damos un algoritmo de aproximación con una relación de aproximación $1 / sqrt{2}$ en todos los gráficos.

Un algoritmo de aproximación mejorado para Quantum Max-Cut en gráficos sin triángulos PlatoBlockchain Data Intelligence. Búsqueda vertical. Ai.

Imagen de portada: Vecindad local del borde en un gráfico sin triángulos.

[Contenido incrustado]

Resumen popular

¿Cómo podemos redondear una relajación SDP a un estado cuántico entrelazado? ¿Y cómo deberíamos optimizar un circuito variacional ansatz? En este trabajo resolvemos estos dos problemas combinándolos: Utilice la solución SDP para elegir los parámetros del circuito variacional.

► datos BibTeX

► referencias

[ 1 ] Anurag Anshu, David Gosset y Karen Morenz. Más allá de las aproximaciones del estado del producto para un análogo cuántico del corte máximo. En 15° Congreso sobre Teoría de la Computación, Comunicación y Criptografía Cuántica, 2020. https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.7.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.7

[ 2 ] Anurag Anshu, David Gosset, Karen Morenz y Mehdi Soleimanifar. Algoritmos de aproximación mejorados para hamiltonianos locales de grado acotado. Cartas de revisión física, 127(25):250502, 2021. https:/​/​doi.org/​10.1103/​PhysRevLett.127.250502.
https: / / doi.org/ 10.1103 / PhysRevLett.127.250502

[ 3 ] Jop Briët, Fernando Mário de Oliveira Filho y Frank Vallentin. Desigualdades de Grothendieck para programas semidefinidos con restricción de rango. Teoría de la informática, 10(4):77–105, 2014. https:/​/​doi.org/​10.4086/​toc.2014.v010a004.
https: / / doi.org/ 10.4086 / toc.2014.v010a004

[ 4 ] Sergey Bravyi, David Gosset, Robert König y Kristan Temme. Algoritmos de aproximación para problemas cuánticos de muchos cuerpos. Revista de Física Matemática, 60(3):032203, 2019. https:/​/​doi.org/​10.1063/​1.5085428.
https: / / doi.org/ 10.1063 / 1.5085428

[ 5 ] Fernando GSL Brandao y Aram W Harrow. Aproximaciones de estado-producto a estados cuánticos. Comunicaciones en Física Matemática, 342:47–80, 2016. https:/​/​doi.org/​10.1007/​s00220-016-2575-1.
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[ 6 ] Toby Cubitt y Ashley Montanaro. Clasificación de complejidad de problemas hamiltonianos locales. Revista SIAM de Computación, 45(2):268–316, 2016. https:/​/​doi.org/​10.1137/​140998287.
https: / / doi.org/ 10.1137 / 140998287

[ 7 ] Uriel Feige y Gideon Schechtman. Sobre la optimización de la técnica de redondeo aleatorio del hiperplano para un corte máximo. Algoritmos y estructuras aleatorias, 20(3):403–440, 2002. https:/​/​doi.org/​10.1002/​rsa.10036.
https: / / doi.org/ 10.1002 / rsa.10036

[ 8 ] Sevag Gharibian y Julia Kempe. Algoritmos de aproximación para problemas qma-completos. Revista SIAM de Computación, 41(4):1028–1050, 2012. https:/​/​doi.org/​10.1137/​110842272.
https: / / doi.org/ 10.1137 / 110842272

[ 9 ] Sevag Gharibian y Ojas Parekh. Algoritmos de aproximación clásica casi óptimos para una generalización cuántica de max-cut. En aproximación, aleatorización y optimización combinatoria. Algoritmos y Técnicas (APROX/​RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. https:/​/​doi.org/​10.4230/​LIPIcs.APPROX-RANDOM.2019.31.
https: / / doi.org/ 10.4230 / LIPIcs.APPROX-RANDOM.2019.31

[ 10 ] Michel Goemans y David Williamson. Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando programación semidefinida. Revista de la ACM (JACM), 42(6):1115–1145, 1995. https:/​/​doi.org/​10.1145/​227683.227684.
https: / / doi.org/ 10.1145 / 227683.227684

[ 11 ] Johan Hastad. Algunos resultados óptimos de inaproximabilidad. Revista de la ACM (JACM), 48(4):798–859, 2001. https:/​/​doi.org/​10.1145/​502090.502098.
https: / / doi.org/ 10.1145 / 502090.502098

[ 12 ] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson y John Wright. Dureza de juegos única del corte máximo cuántico y una desigualdad de Borrell con valor vectorial conjeturada. En Actas del Simposio anual ACM-SIAM de 2023 sobre algoritmos discretos (SODA), páginas 1319–1384. SIAM, 2023. https:/​/​doi.org/​10.1137/​1.9781611977554.ch48.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch48

[ 13 ] Subhash Khot, Guy Kindler, Elchanan Mossel y Ryan O'Donnell. ¿Resultados óptimos de inaproximabilidad para max-cut y otros csps de 2 variables? Revista SIAM de Computación, 37(1):319–357, 2007. https:/​/​doi.org/​10.1137/​S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372

[ 14 ] Euno Lee. Optimización de los parámetros del circuito cuántico mediante sdp. En 33º Simposio Internacional sobre Algoritmos y Computación (ISAAC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. https:/​/​doi.org/​10.4230/​LIPIcs.ISAAC.2022.48.
https: / / doi.org/ 10.4230 / LIPIcs.ISAAC.2022.48

[ 15 ] Stephen Piddock y Ashley Montanaro. La complejidad de las interacciones antiferromagnéticas y las redes 2D. Información y computación cuánticas, 17(7-8):636–672, 2017. https:/​/​dl.acm.org/​doi/​abs/​10.5555/​3179553.3179559.
https: / / dl.acm.org/ doi / abs / 10.5555 / 3179553.3179559

[ 16 ] Ojas Parekh y Kevin Thompson. Aplicación de la jerarquía cuántica de Lasserre de nivel 2 en algoritmos de aproximación cuántica. En el 48º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2021.102.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.102

[ 17 ] Ojas Parekh y Kevin Thompson. Superar la asignación aleatoria para aproximar problemas hamiltonianos cuánticos 2 locales. En el 29º Simposio Europeo Anual sobre Algoritmos (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. https:/​/​doi.org/​10.4230/​LIPIcs.ESA.2021.74.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.74

[ 18 ] Ojas Parekh y Kevin Thompson. Una aproximación óptima del estado del producto para hamiltonianos cuánticos bilocales con términos positivos. Preimpresión de arXiv arXiv:2, 2206.08342. https:/​/​doi.org/​2022/​arXiv.10.48550.
https://​/​doi.org/​10.48550/​arXiv.2206.08342
arXiv: 2206.08342

Citado por

[1] Nicolas PD Sawaya, Daniel Marti-Dafcik, Yang Ho, Daniel P Tabor, David Bernal, Alicia B Magann, Shavindra Premaratne, Pradeep Dubey, Anne Matsuura, Nathan Bishop, Wibe A de Jong, Simon Benjamin, Ojas D Parekh, Norm Tubman, Katherine Klymko y Daan Camps, "HamLib: una biblioteca de hamiltonianos para evaluar hardware y algoritmos cuánticos", arXiv: 2306.13126, (2023).

[2] Dmitry Grinko y Maris Ozols, “Programación lineal con restricciones unitarias equivalentes”, arXiv: 2207.05713, (2022).

[3] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy y Stuart Wayland, “Algoritmos de aproximación para Quantum Max-$d$-Cut”, arXiv: 2309.10957, (2023).

[4] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton e Igor Klep, "Relajaciones y soluciones exactas para Quantum Max Cut a través de la estructura algebraica de los operadores de intercambio", arXiv: 2307.15661, (2023).

[5] Andrew Zhao y Nicholas C. Rubin, "Ampliando el alcance de la optimización cuántica con incrustaciones fermiónicas", arXiv: 2301.01778, (2023).

[6] Steven Heilman, “Estabilidad del ruido valorada por esfera y dureza Quantum MAX-CUT”, arXiv: 2306.03912, (2023).

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2023-11-09 11:49:09). 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 2023-11-09 11:49:08: No se pudieron obtener los datos citados por 10.22331 / q-2023-11-09-1180 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.

Sello de tiempo:

Mas de Diario cuántico