Lista de algoritmos de inspiración cuántica

Los avances en la computación cuántica han llevado al desarrollo de nuevos algoritmos clásicos. Ejemplos recientes notables son los algoritmos de inspiración cuántica para el álgebra lineal:

• Un algoritmo clásico de inspiración cuántica para sistemas de recomendación.
• Algoritmos clásicos de inspiración cuántica para análisis de componentes principales y agrupamiento supervisado
• Regresión estocástica de bajo rango de inspiración cuántica con dependencia logarítmica de la dimensión
• Algoritmos clásicos sublineales de inspiración cuántica para resolver sistemas lineales de bajo rango

y para Max 3LIN:

• Superar la asignación aleatoria en problemas de satisfacción de restricciones de grado acotado .

Puede ser muy útil compilar una lista de todos los algoritmos clásicos conocidos inspirados en la computación cuántica. ¿Qué otros ejemplos se conocen?

Como afirmó Leslie G. Valiant en un artículo seminal 1 de su,

Los algoritmos holográficos están inspirados en el modelo computacional cuántico. Sin embargo, son ejecutables en computadoras clásicas y no necesitan computadoras cuánticas.

Esa es una técnica de diseño algorítmico que ha sido utilizada (por el propio Valiant y otros) para producir algoritmos de tiempo polinomiales para varios problemas que son variaciones menores de problemas NP-hard importantes (más sobre esto en wikipedia 2 ).

También hay un trabajo reciente sobre programación semidefinida de bajo rango que, aunque no se basa directamente en un algoritmo cuántico, todavía utiliza las mismas técnicas inspiradas en lo cuántico.

Hay una gran cantidad de trabajo que hacer con los algoritmos evolutivos inspirados cuánticos (QIEA), con algoritmos reales que usan técnicas de computación cuántica, ver encuesta (fuente ACM) . Otro algoritmo de inspiración cuántica lo utiliza en la optimización numérica .

El algoritmo (s) de recocido cuántico cuántico Monte Carlo (QMC-QA ¹ ) o de discreto tiempo simulado (SQA ² ) funcionó mejor que el dispositivo D-Wave probado en estudios recientes :

Establecemos el primer ejemplo de una ventaja de escala para un recocido cuántico experimental sobre el recocido simulado clásico: encontramos que el dispositivo D-Wave exhibe una escala certificablemente mejor que el recocido simulado, con un 95% de confianza, sobre el rango de tamaños de problemas que podemos probar . Sin embargo, no encontramos evidencia de una aceleración cuántica: el recocido cuántico simulado exhibe la mejor escala por un margen significativo.

Dado que tanto el dispositivo D-Wave como SQA superan a SA en ciertos casos problemáticos, esto da la impresión de que SQA es una especie de algoritmo de inspiración cuántica. El estudio más reciente que prueba el procesador D-Wave 2000Q también encuentra que su rendimiento se correlaciona mejor con un modelo clásico propuesto denominado "algoritmo de Monte Carlo (SVMC) spin-vector" en ese estudio que con SQA:

Usamos esto para argumentar que una razón clave para la desaceleración del recocido cuántico en relación con SQA es su temperatura subóptimamente alta, lo que hace que se comporte más como SVMC. Por lo tanto, el sólido rendimiento de SQA en la clase de instancia plantada lógicamente sugiere que esta clase es un buen objetivo o base para la exploración de una eventual aceleración cuántica utilizando hardware QA.

Si ignoramos la historia de fondo de D-Wave, ¿podemos concluir que SQA es un algoritmo de optimización de inspiración cuántica que supera el recocido simulado clásico (y tal vez otros algoritmos de optimización) para ciertos problemas? Depende. Si el objetivo es encontrar el estado fundamental de algún sistema cuántico, entonces la respuesta es sí. Pero si el objetivo es tener un algoritmo de optimización de propósito general similar al recocido simulado, entonces la respuesta es no.

1. _{Martoňák, R., Santoro, GE y Tosatti, E. Recocido cuántico mediante el método de Monte Carlo integral de ruta: el modelo de Ising aleatorio bidimensional. Phys. Rev. B 66 , 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203}
2. _{Santoro, GE, Martoňák, R., Tosatti, E. & Car, R. Teoría del recocido cuántico de un vidrio giratorio Ising. Science 295 , 2427–2430 (2002). URL http://dx.doi.org/10.1126/science.1068774 .}

Eche un vistazo a la programación genética lineal de inspiración cuántica. Este algoritmo tiene como objetivo inducir programas de computadora en lenguajes imperativos. P.ej:

• https://www.researchgate.net/project/Quantum-Inspired-Linear-Genetic-Programming

• Programación genética lineal inspirada en cuánticos como sistema de gestión del conocimiento, agosto de 2013, The Computer Journal 56 (9): 1043-1062, Douglas Mota Dias y Marco Aurelio C. Pacheco https://doi.org/10.1093/comjnl/bxs108