¿Hay alguna afirmación general sobre qué tipos de problemas se pueden aproximar de manera más eficiente utilizando una computadora cuántica?

Como su nombre ya sugiere, esta pregunta es un seguimiento de esta otra . Estaba encantado con la calidad de las respuestas, pero sentí que sería inmensamente interesante si se agregaran ideas sobre las técnicas de optimización y aproximación, pero podrían quedar fuera de tema, de ahí esta pregunta.

De la respuesta de Blue:

La regla general en la teoría de la complejidad es que si una computadora cuántica "puede ayudar" en términos de resolver en tiempo polinomial (con un error vinculado) si la clase de problema que puede resolver se encuentra en BQP pero no en P o BPP

¿Cómo se aplica esto a las clases de aproximación? ¿Existe alguna propiedad topológica, numérica, etc. específica de la computación cuántica que pueda aprovecharse?

Como ejemplo de lo que podría preguntar (¡pero definitivamente no se limita a eso!), Tome el algoritmo Christofides : explota propiedades geométricas específicas del gráfico que optimiza (simetría, desigualdad de triángulos): el vendedor viaja en un mundo factible . Pero los vendedores también tienen una gran masa, y podemos conocer su posición e impulso al mismo tiempo con gran precisión. ¿Quizás un modelo cuántico podría funcionar tan bien para otro tipo de métricas con restricciones más relajadas, como la divergencia KL ? En ese caso, la solución aún estaría completa NP, pero la optimización se aplicaría para una topología más amplia. Este ejemplo es quizás una posibilidad remota, pero espero que entiendas lo que quiero decir. Realmente no sé si tiene sentido, pero la respuesta también podría abordarlo en ese caso :)

RELACIONADO:

• Nivel de ventaja que proporciona el recocido para el vendedor ambulante

El algoritmo cuántico de optimización aproximada es un buen lugar para comenzar a analizar el rendimiento relativo de los algoritmos cuánticos en problemas de aproximación. Un resultado hasta ahora es que en p = 1 QAOA puede alcanzar teóricamente una relación de aproximación de 0.624 para MaxCut en gráficos de 3 regulares. Este resultado se obtuvo utilizando la enumeración de la fuerza bruta de los diferentes casos posibles. Esta no es una técnica fácilmente generalizable, por lo que se sabe relativamente poco sobre el rendimiento de QAOA en otros problemas.

Tal como está actualmente, QAOA utiliza muy poca estructura en el problema de optimización combinatoria y opera más en la línea de un método de búsqueda directa. Una posible consecuencia es que QAOA se utilizaría mejor para problemas donde hay una estructura mínima. En este caso, no hay nada que los algoritmos clásicos puedan usar para acelerar el proceso de búsqueda.