El Algoritmo Cuántico de Optimización Aproximada a Alta Profundidad para MaxCut en Grafos Regulares de Gran Girth y el Modelo de Sherrington-Kirkpatrick

El Algoritmo Cuántico de Optimización Aproximada (QAOA) encuentra soluciones aproximadas a problemas de optimización combinatoria. Su rendimiento mejora monótonamente con su profundidad p. Aplicamos el QAOA a MaxCut en grafos D-regulares de gran girth. Damos una fórmula iterativa para evaluar el rendimiento para cualquier D en cualquier profundidad p. Al observar grafos D-regulares aleatorios, en parámetros óptimos y a medida que D tiende a infinito, encontramos que el QAOA para p=11 supera todos los algoritmos clásicos (conocidos por los autores) que están libres de conjeturas no probadas. Mientras que la fórmula iterativa para estos grafos D-regulares se deriva al observar un solo subgrafo de árbol, demostramos que también proporciona el rendimiento promedio del QAOA en el modelo de Sherrington-Kirkpatrick (SK) definido en el grafo completo. También generalizamos nuestra fórmula a Max-q-XORSAT en hipergrafos regulares de gran girth. Nuestra iteración es un procedimiento compacto, pero su complejidad computacional crece como O (p² 4ᵖ). Esta iteración es más eficiente que el procedimiento anterior para analizar el rendimiento del QAOA en el modelo SK, y somos capaces de ir numéricamente hasta p=20. Alentados por nuestros hallazgos, hacemos la conjetura optimista de que el QAOA, a medida que p tiende a infinito, alcanzará el valor de Parisi. Analizamos el rendimiento del algoritmo cuántico, pero es necesario ejecutarlo en una computadora cuántica para producir una cadena con el rendimiento garantizado.