¿Hay ejemplos de casos en los que la simulación clásica de un algoritmo cuántico para un problema supera al algoritmo clásico mejor conocido anteriormente para este problema? "Superar" no tiene que significar una clase de complejidad diferente, simplemente podría ser una mejor escala.
Esta pregunta se inspiró en el caso de la simulación clásica eficiente de un algoritmo de recomendación cuántica .
Respuestas:
Su pregunta se inspiró en el reciente avance clásico de inspiración cuántica en el algoritmo de recomendación. Tenga en cuenta que no es el primer momento en que sucede tal cosa. En 2015, ocurrieron desarrollos similares con MAX3LIN aproximado : un algoritmo quanutm que supera a todos los algoritmos clásicos conocidos anteriores motivó una búsqueda exitosa de un algoritmo clásico mejor. Sin embargo, hasta donde yo sé, en ambos casos, los algoritmos clásicos no se parecen a la simulación clásica de una evolución cuántica.
Sé de un artículo que describe una simulación clásica de un sistema cuántico que permite superar los algoritmos previamente conocidos (Divulgación completa: los autores son amigos míos) :
Esto se basa en la conexión entre la óptica permanente y la óptica cuántica, que se muestra mediante el muestreo de bosones . En oposición al enfoque habitual, observan estados que son bien conocidos por ser fáciles de simular (estados térmicos), y utilizan esta simulación para realizar un cálculo de Monte-Carlo del permanente de matrices semidefinidas positivas de Hermit. Para algunas clases de matrices, este algoritmo ofrece una mejor aproximación que el mejor algoritmo conocido previamente (algoritmo de Gurvits).
fuente