Algoritmo HHL: ¿por qué el conocimiento requerido sobre eigenspectrum no es un inconveniente importante?

9

Esta pregunta es una continuación de la estimación de fase cuántica y el algoritmo HHL: ¿se requiere conocimiento sobre valores propios? .


En la pregunta vinculada anteriormente, pregunté sobre la necesidad de que HHL tenga información sobre el espectro propio de la matriz A considerada. Resultó que el algoritmo HHL necesita una matriz con valores propios λj[0,1) para funcionar correctamente.

Siguiendo esta condición, dada una matriz A , para aplicar el algoritmo HHL necesitamos verificar una de las siguientes condiciones:

  1. Los valores propios de la matriz están todos dentro de [0,1) .
  2. Un par que atado (desde abajo para L y desde arriba para M ) los valores propios lambda j de la matriz A . Estos límites se pueden usar para reescalar la matriz A de modo que se valide la condición 1.(L,M)R2LMλjAA

Primer grupo de preguntas: leí muchos artículos sobre HHL y ninguno de ellos mencionó esta restricción. ¿Por qué? ¿Se conoce esta restricción pero se considera débil (es decir, es fácil tener este tipo de información)? ¿O no se conocía la restricción? ¿Hay algún trabajo de investigación que mencione esta restricción?


Hablemos ahora sobre el análisis de complejidad de HHL. A partir de algoritmos de sistemas lineales cuánticos: un cebador (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) , la complejidad de HHL (y varias mejoras) se escribe en la imagen a continuación.

complejidad de HHL

El análisis de complejidad no tiene en cuenta (al menos no lo encontré) el conocimiento necesario sobre el espectro propio.

El caso en el que la matriz considerada tiene propiedades suficientemente buenas para estimar sus valores propios analíticamente es poco común (al menos para las matrices del mundo real) y se ignora.

En esta respuesta , @DaftWullie usa el teorema del círculo de Gershgorin para estimar los límites superior e inferior del espectro propio. El problema con este enfoque es que requiere operaciones ( O ( O(N)si la amplificación de amplitud es aplicable). Este número de operaciones destruye la complejidad logarítmica de HHL (y solo es una ventaja sobre los algoritmos clásicos al mismo tiempo).O(N)

Segundo grupo de preguntas: ¿Existe un mejor algoritmo en términos de complejidad? Si no es así, ¿por qué el algoritmo HHL todavía se presenta como una mejora exponencial sobre los algoritmos clásicos?

Nelimee
fuente
Supongo que la mejor manera de abordar esto es preguntar en qué contexto se aplicará el algoritmo HHL. Una vez que conozca el contexto, eso ayuda a especificar lo que sabe sobre la matriz.
DaftWullie
3
Por cierto, la restricción es ciertamente conocida. En la introducción del documento HHL (versión actual de arXiv), dice "Nuestros algoritmos generalmente supondrán que los valores singulares de A se encuentran entre 1 / κ y 1"
DaftWullie
2
El artículo de Scott Aaronson sobre "leer la letra pequeña" para el algoritmo de aprendizaje automático cuántico puede ser especialmente interesante para cualquier persona interesada en esta pregunta. scottaaronson.com/papers/qml.pdf
Jalex Stark
¡Un recurso muy útil! Gracias por el enlace @JalexStark
Nelimee

Respuestas:

5

La restricción de los valores propios generalmente se da en forma de un número de condición . Este es el κ que ves en todos los tiempos de ejecución en tu tabla. κ=|λmax/λmin|donde λmax y λmin son los valores propios máximo y mínimo respectivamente.

En todos los tiempos de ejecución enumerados en su tabla, se supone que se conoce el número de condición. Por lo general, no se piensa en "calcular el número de condición" como parte del algoritmo para resolver Ax=b , por ejemplo. Si el número de condición es mayor, el sistema es más difícil de resolver, y si es más pequeño, el sistema es más fácil de resolver (suponiendo todos los demás parámetros, incluido el error máximo deseadoϵ se mantienen fijos).

En términos de necesidad de saber que λmax<M y λmin>L , hay muchos ejemplos en los que podemos conocer los límites de los valores propios sin pasar realmente por el esfuerzo de calcular los valores propios. De esta manera, HHL puede ser una excelente manera de encontrar el estado que está buscando, sin el costo de calcular el número de condición o cualquier valor propio.

Permítanme dar solo un ejemplo del mundo real. Digamos que quiero encontrar el estado vibracional molecular |ψ tal que después de t=10 ps de evolucionar bajo su hamiltoniano H , los extremos de la molécula hasta en el estado |b . Esto puede ser descrito por la ecuación:

eiHt|ψ=|b

donde el |ψ satisfacer esta ecuación es lo que quiere saber. Puedes encontrar tu deseado |ψ utilizando el algoritmo de HHL con A=eiHty|ψ=|x.

Obtener los valores propios más pequeños y más grandes de un Hamiltoniano molecular con precisión arbitraria es extremadamente costoso en un compilador clásico, pero saber que se encuentran dentro del rango (L,M) puede determinarse sin costo alguno. Por ejemplo, si la molécula es el dímero de nitrógeno, sabemos que los estados vibracionales más bajos y más altos tienen energías (valores propios) entre 0 y 10 eV y dado que e0=1 tenemos L=1 y M=ei10eV10ps. Puede convertir eV a Hz y ps a segundos para evaluarMnuméricamente, y luego puede obtener los límites inferior y superior que necesita usar al escalar su matriz de la manera que describió en su pregunta anterior. En ningún momento necesité calcular los valores propios de un Hamiltoniano molecular de 14 electrones (lo que sería extremadamente difícil y anularía el propósito de usar HHL, porque si pudiera calcular los valores propios, podría calcularAe invertirlo para obtener|ψ) Acabo de usar la energía de disociación de la molécula para descubrir los límites de sus energías vibratorias. Podría haber encontrado límites aún mejores utilizando la aproximación semiclásica de WKB , también con un costo mucho menor que el cálculo real de los valores propios, pero el primer ejemplo ya es suficiente.

Así que ahora abordemos todas sus preguntas individuales:

Primer grupo de preguntas: leí muchos documentos sobre HHL y ninguno de ellos mencionó esta restricción. ¿Por qué? ¿Se conoce esta restricción pero se considera débil (es decir, es fácil tener este tipo de información)? ¿O no se conocía la restricción? ¿Hay algún trabajo de investigación que mencione esta restricción?

De los 539 documentos que (en la actualidad) han citado el documento original de HHL, muchos de ellos no conocerán los detalles más finos, como la dependencia de su desempeño del número de condición o los valores propios. Algunos de los documentos seguramente sabrán que el rendimiento del algoritmo dependerá del número de condición o de los valores propios de la matriz, a saber, los documentos enumerados en su tabla sobre mejoras al algoritmo HHL. Robin Kothari también lo mencionó, por ejemplo, al comienzo de su charla en 2016 sobre el algoritmo CKS (que se menciona en su tabla).

Segundo grupo de preguntas: ¿Existe un mejor algoritmo en términos de complejidad? Si no es así, ¿por qué el algoritmo HHL todavía se presenta como una mejora exponencial sobre los algoritmos clásicos?

El algoritmo que menciona, sugerido por DaftWulie, para estimar los límites de los valores propios, no se mejorará con respecto a O(N)porque el costo dominante en ese algoritmo es buscar en todas lasNfilas los valores máximos y mínimos. El costo de todo lo demás es pequeño debido a que la matriz se supone que tiene una escasez desN. No hay forma de hacer esta búsqueda más rápido que O(N) tiempo (a menos que tenga algún otro conocimiento adicional del sistema) porque el algoritmo de Grover ha demostrado ser óptimo.

Tienes razón, la gente debería mencionar las advertencias de los algoritmos con más frecuencia en sus documentos. En términos de su pregunta específica "por qué el algoritmo HHL todavía se presenta como una mejora exponencial sobre los algoritmos clásicos", creo que los autores originales HHL hicieron su debida diligencia al explicar el algoritmo y sus advertencias, ya que dijeron que hay un exponencial escalar pero el costo crece cuadráticamente con el número de condición y la escasez e inversamente con el tamaño del error que está dispuesto a tolerar. ¿Por qué la mayoría de las personas después de HHL no mencionan todas las advertencias? Bueno, muchos de ellos no conocen las advertencias, y aquellos que sí lo hicieron podrían haber sentido que no era necesario porque calcular el número de condición no es parte del algoritmo. Conocer el número de condición le dirá qué tan bien funcionará el algoritmo,

usuario1271772
fuente
1
+1, bien dirigido.
Niel de Beaudrap
2
La conclusión es "El caso en el que la matriz considerada tiene propiedades suficientemente buenas para estimar sus valores propios (o límites inferior / superior) analíticamente es poco común (al menos para las matrices del mundo real) pero es la única con la que podemos tratar en este momento si queremos aplicar HHL ". Mi pregunta probablemente era demasiado limitada para responder con la limitación de los casos analíticos "simples". ¡Gracias! Su caso de uso específico es interesante y también estaría bien aquí: quantumcomputing.stackexchange.com/questions/2697/…
Nelimee
@NieldeBeaudrap: Es un honor recibir ese comentario tuyo, ya que eres un tipo que sabe que le gustan las cosas precisas y rigurosas. Sé que muchas de mis otras respuestas han tenido lagunas, que fueron las primeras en señalar, como el caso en el que mi respuesta solo funcionó para estados ortogonales.
usuario1271772