Algoritmos de aproximación cuántica

En general, se considera improbable que las computadoras cuánticas puedan resolver problemas NP-completos de manera eficiente. En el caso clásico, un enfoque para abordar tales problemas es utilizar algoritmos de aproximación. ¿Ha habido alguna investigación sobre algoritmos de aproximación que utilicen la computación cuántica en la que la cuantidad proporcione una aceleración significativa sobre los métodos de aproximación clásicos?

Por "significativo" quiero decir no necesariamente exponencial, sino mayor que para los algoritmos exactos correspondientes. En otras palabras, me interesa si relajar el requisito de que nuestro algoritmo produzca la solución exacta brinda una ventaja significativa a los algoritmos cuánticos.

Un comentario actualizado a respuesta parcial:

En estos días hay bastante trabajo en una versión cuántica conjeturada (o no) del teorema de PCP: vea, por ejemplo, esta publicación de blog de Scott Aaronson http://www.scottaaronson.com/blog/?p=139 o esta respuesta de Peter Shor en MathOverflow /mathpro/45106/quantum-pcp-theorem/45167#45167

Con respecto a los alpgoritmos de aproximación cuántica, puede consultar esta referencia "Algoritmos de aproximación para problemas de QMA-completa" http://arxiv.org/abs/1101.3884

Personalmente, no conozco ningún trabajo en la dirección de algoritmos de aproximación cuántica en el sentido de aproximaciones relativas (vs aproximaciones aditivas) (aunque eso no necesariamente significa que no existan).

Tenga en cuenta que si su intención es diseñar algs cuánticos de tiempo múltiple para, por ejemplo, problemas NP-duros, muchos problemas como MAX-CUT ya tienen unos algs clásicos ajustados (suponiendo la Conjetura de juegos únicos o por PCP). Por lo tanto, probablemente tenga sentido comenzar estudiando un problema que tenga una brecha en la relación de aproximación conocida versus los resultados de dureza.

La otra dirección es la dureza de la aproximación; véanse, por ejemplo, http://arxiv.org/abs/0811.3412 y http://arxiv.org/abs/1012.3319 para el progreso parcial positivo y negativo con respecto a un posible teorema de PCP cuántico.

Una especie de respuesta trivial, pero hay una estimación de la probabilidad de aceptación de un circuito cuántico, o de cualquiera de los problemas equivalentes, como la aproximación del polinomio de Jones, o la solución de un sistema lineal de ecuaciones, o la traza de una potencia de un Matriz dispersa grande.

Además, el conteo aproximado acelera muchos algoritmos de aproximación basados ​​en muestreo.

$i$