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

^{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 $\lambda_j \in [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) \in \mathbb{R}^2$$L$$M$$\lambda_j$$A$$A$

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.

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 ( $\mathcal{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).$\mathcal{O}(\sqrt{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?

La restricción de los valores propios generalmente se da en forma de un número de condición . Este es el $\kappa$ que ves en todos los tiempos de ejecución en tu tabla. $\kappa = |\lambda_{\rm{max}}/\lambda_{\rm{min}}|$donde $\lambda_{\rm{max}}$ y $\lambda_{\rm{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$\epsilon$ se mantienen fijos).

En términos de necesidad de saber que $\lambda_{\rm{max}} < M$ y $\lambda_{\rm{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 $|\psi\rangle$ 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\rangle$ . Esto puede ser descrito por la ecuación:

donde el $|\psi\rangle$ satisfacer esta ecuación es lo que quiere saber. Puedes encontrar tu deseado $|\psi\rangle$ utilizando el algoritmo de HHL con $A = e^{-\frac{i}{\hbar}Ht}$y$|\psi\rangle = |x\rangle$.

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 $e^{0}=1$ tenemos $L=1$ y $M = e^{-\frac{i}{\hbar} 10 \rm{eV} \cdot 10 \rm{ps}}$. Puede convertir eV a Hz y ps a segundos para evaluar$M$numé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 calcular$A$e invertirlo para obtener$|\psi\rangle$) 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 $\mathcal{O}(\sqrt{N})$porque el costo dominante en ese algoritmo es buscar en todas las$N$filas 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 de$s \lll N$. No hay forma de hacer esta búsqueda más rápido que $\mathcal{O}(\sqrt{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,