Algoritmo cuántico para sistemas de ecuaciones lineales

El algoritmo cuántico para sistemas de ecuaciones lineales, diseñado por Aram Harrow, Avinatan Hassidim, y Seth Lloyd (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). es un algoritmo cuántico para resolver sistemas de ecuaciones lineales formulado en 2009. El algoritmo estima el resultado de una medida sobre el vector solución de un sistema de ecuaciones lineales dado.​

Es uno de los algoritmos fundamentales que junto con el algoritmo de Shor, el algoritmo de Grover y el algoritmo de simulación cuántica de Feynman esperan proporcionar un aumento de la velocidad exponencial respecto de sus versiones clásicas. Dado un sistema lineal disperso con un número de condición k, bajo y estando el usuario interesado en una medida sobre el vector solución, en vez del propio vector solución, el algoritmo tiene un tiempo de ejecución de O(log Nk²). Esto ofrece un aumento exponencial de la velocidad respecto al algoritmo clásico más rápido, cuyo tiempo de ejecución es O(N√k), donde N es el número de variables del sistema lineal.

Una implementación del algoritmo fue realizada en paralelo por primera vez en 2013 por Cai et al., Barz et al. y Pan et al. La demostración consistió en la resolución de un sistema simple de ecuaciones lineales especialmente diseñado para dispositivos cuánticos.​​​ La primera implementación de una versión genérica del algoritmo fue realizada en 2018 por Zhao et al.​

Debido al uso de los sistemas lineales en prácticamente todas las áreas de la ciencia y la ingeniería, el algoritmo cuántico para sistemas de ecuaciones lineales tiene el potencial de ser el algoritmo cuántico más utilizado hasta ahora. Este es un importante hito para la computación cuántica ya que los anteriores algoritmos ofrecen una aceleración exponencial pero no tienen ni versatilidad ni obvias aplicaciones en el mundo real.​

Procedimiento

El problema que estamos tratando de resolver es el siguiente: dada una matriz $A$ Hermítica $N\times N$ y un vector ${\overrightarrow {b}}$, encontrar el vector solución ${\overrightarrow {x}}$ que satisfaga $A{\overrightarrow {x}}={\overrightarrow {b}}$. Este algoritmo asume que el usuario no está interesado en los valores de ${\overrightarrow {x}}$ en sí mismos, sino más bien en el resultado de aplicar algún operador $M$ sobre $x$, $\langle x|M|x\rangle$.

Primero, el algoritmo representa el vector ${\overrightarrow {b}}$ como un estado cuántico de la forma:

$|b\rangle =\sum _{i\mathop {=} 1}^{N}b_{i}|i\rangle .$

Después utilizamos técnicas de simulación de hamiltonianos para aplicar el operador unitario $e^{iAt}$ a $|b\rangle$ para una superposición de diferentes tiempos $t$. Las operaciones de descomposición de $|b\rangle$ en la eigenbase de $A$ y de encontrar los correspondientes eigenvalores $\lambda _{j}$, son facilitadas por el uso del algoritmo cuántico de estimación de fase.

El estado del sistema después de esta descomposición es aproximadamente.

$\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle |\lambda _{j}\rangle ,$

Donde $u_{j}$ es el eigenvector de la base $A$, y $|b\rangle =\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle$

Nos gustaría realizar una aplicación lineal de $|\lambda _{j}\rangle$ a $C\lambda _{j}^{-1}|\lambda _{j}\rangle$, donde $C$ es una constante de normalización. La operación no es unitaria y por tanto requerimos un número de repeticiones debido a que tiene una probabilidad de error. Después de tener éxito, calculamos el registro $|\lambda _{j}\rangle$ y es inversamente proporcional al estado:

$\sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle ,$

Donde $|x\rangle$ es la representación cuántica del vector solución x deseado. Para obtener todas las componentes de x deberíamos repetir el procedimiento al menos N veces. Sin embargo, es frecuente el caso de que no interese x en sí mismo, sino más bien el valor esperado de un operador lineal Mactuando sobre x Gracias al mapeo de M al operador cuántico y realizando la medida cuántica correspondiente a M, obtenemos un valor esperado estimado $\langle x|M|x\rangle$.. Esto permite extraer una amplia variedad de características del vector x incluyendo la normalización, los pesos en las diferentes partes del espacio de estado, y los momentos, sin calcular realmente todos los valores de la solución x.

Explicación del algoritmo

Inicialización

Primero, el algoritmo requiere que la matriz $A$ sea hermitica de forma que podamos convertirla en un operador unitario. En el caso de que A no sea hermítica, definimos:

$\mathbf {C} ={\begin{bmatrix}0&A\\A^{t}&0\end{bmatrix}}.$

Como $C$ es Hermitica, el algoritmo puede ahora ser usado para resolver $Cy={\begin{bmatrix}b\\0\end{bmatrix}}.$ para obtener $y={\begin{bmatrix}0\\x\end{bmatrix}}$.

Segundo, el algoritmo requiere un procedimiento eficiente para preparar $|b\rangle$, la representación cuántica de b. Se asume que existe un operador lineal $B$ que puede tomar eficientemente algún estado arbitrario $|\mathrm {inicial} \rangle$ de $|b\rangle$ o que este algoritmo es una subrutina de un algoritmo más grande y este $|b\rangle$ es tomado como una entrada. Cualquier error en la preparación del estado $|b\rangle$ es ignorado.

Finalmente, el algoritmo asume que el estado $|\psi _{0}\rangle$ puede ser preparado eficientemente. Donde

$|\psi _{0}\rangle :={\sqrt {2/T}}\sum _{\tau \mathop {=} 0}^{T-1}\sin \pi \left({\tfrac {\tau +{\tfrac {1}{2}}}{T}}\right)|\tau \rangle$

para algún $T$ grande. Los coeficientes de $|\psi _{0}\rangle$ son escogidos para minimizar la pérdida de una cierta función cuadrática que induce error en la subrutina $U_{\mathrm {invert} }$ que se describe a continuación.

Estimación de la fase

La estimación de la fase es usada para transformar la matriz Hermítica $A$ en un operador unitario, el cual pueda ser aplicado en el futuro. Esto es posible si A es s-sparse y eficientemente fila computable, lo que significa que tiene al menos s entradas no nulas por fila y dado un índice de fila estas entradas pueden ser calculadas en un tiempo del orden O(s). Bajo estas suposiciones, la estimación de fase produce $e^{i}At$ para ser simulada en un tiempo $O(\log(N)s^{2}t)$.

Subrutina de inversión de U

La subrutina clave del algoritmo, denotada por $U_{\mathrm {invertida} }$ es definida como:

1. Preparar $|\psi _{0}\rangle ^{C}$ sobre el registro C

2. Aplicar la evolución condicional Hamiltoniana (suma)

3. Aplicar la transformada de Furier al registro C. Marcamos los estados base resultantes con $|k\rangle$ para $k$:= 0, ..., T − 1. Definiendo $\lambda _{k}:=2\pi k/t_{0}$.

4. Unir un registro tri-dimensional S al estado

$|h(\lambda _{k})\rangle ^{S}:={\sqrt {1-f(\lambda _{k})^{2}-g(\lambda _{k})^{2}}}|\mathrm {nada} \rangle ^{S}+f(\lambda _{k})|\mathrm {bien} \rangle ^{S}+g(\lambda _{k})|\mathrm {mal} \rangle ^{S},$

5. Invertimos los pasos 1-3, sin calcular cualquier basura producida en el camino.

Donde las funciones f y g son funciones de filtro. Los estados 'nada', 'bien', y 'mal' son usados para indicar al cuerpo del bucle como proceder, 'nada' indica que la inversión de la matriz deseada todavía no se ha producido, 'bien' indica que la inversión ha tenido lugar, y 'mal' indica que parte de $|b\rangle$ está en el subespacio de A mal acondicionada y que el algoritmo no será capaz de producir la inversión deseada.

Lazo principal

El cuerpo del algoritmo sigue el procedimiento de amplificación de la amplitud: empezando con $U_{\mathrm {invertido} }B|\mathrm {inicial} \rangle$, se repiten las siguientes operaciones:

$U_{\mathrm {invertido} }BR_{\mathrm {inicial} }B^{\dagger }U_{\mathrm {invertido} }^{\dagger }R_{\mathrm {succ} }$

donde

$R_{\mathrm {succ} }=I^{2}-2|\mathrm {bien} \rangle \langle \mathrm {bien} |^{2},$

y

$R_{\mathrm {inicial} }=I^{2}-2|\mathrm {inicial} \rangle \langle \mathrm {inicial} |.$

Después de cada repetición, $S$ es medido y producirá un valor de 'nada', 'bien', o 'mal' como se describió anteriormente. Este bucle es repetido hasta que $S$ es medido 'bien', lo cual ocurre con una probabilidad $p$. En lugar de repetir ${\frac {1}{p}}$ veces para minimizar el error, se utiliza la amplificación de amplitud para lograr la misma capacidad de recuperación de error usando solo $O\left({\frac {1}{\sqrt {p}}}\right)$ repeticiones.

Media escalar

Después de medir satisfactoriamente 'bien' en el sistema S el sistema estará en un estado proporcional a:

$\sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle .$

Finalmente, realizamos la operación correspondiente a M y obtenemos una estimación del valor de $\langle x|M|x\rangle$.

Análisis del tiempo de ejecución

Eficiencia clásica

El mejor algoritmo clásico que produce actualmente la solución ${\overrightarrow {x}}$ es la eliminación Gaussiana, la cual corre en un tiempo de $O(N^{3})$.

Si A es s-sparse, donde s es significativamente más pequeño que  N, entonces el método del gradiente conjugado puede ser usado para encontrar el vector solución ${\overrightarrow {x}}$ en tiempo $O(N\log(N))$ minimizando la función cuadrática $|A{\overrightarrow {x}}-{\overrightarrow {b}}|^{2}$.

Cuando solo se necesita un resumen estadístico del vector solución ${\overrightarrow {x}}$, como en el caso del algoritmo cuántico para sistemas de ecuaciones lineales, un cálculo clásico puede encontrar una estimación de ${\overrightarrow {x}}^{\dagger }M{\overrightarrow {x}}$ en $O(N{\sqrt {\kappa }})$.

Eficiencia cuántica

El algoritmo cuántico para resolver el sistema de ecuaciones originalmente propuesto por Harrow et al. demostró ser del orden $O(\kappa ^{2}\log N)$. El tiempo de ejecución de este algoritmo mejorado por Andris Ambainis se incrementó a $O(\kappa \log ^{3}\kappa \log N)$.​

Optimización

Un importante factor en la realización del algoritmo de inversión es el número de condición $\kappa$, el cual representa el ratio del mayor y el menor eigenvalor de $A$. A medida que el número de condición aumenta, la facilidad con la que el vector solución puede ser encontrada usando los métodos del gradiente descendente tales como el método del gradiente conjugado descendente, la matriz $A$ está más cerca de una matriz que no puede ser invertida y el vector solución se convierte en menos estable. Este algoritmo asume que todos los elementos de la matriz $A$ se encuentran entre ${\frac {1}{\kappa }}$ y 1, en cuyo caso se logra un tiempo de ejecución proporcional a $\kappa ^{2}$. Por tanto, el incremento de velocidad sobre los algoritmos clásicos se ve incrementado cuando $\kappa$ es un $\mathrm {poly} (\log(N))$.​

Si el tiempo de ejecución del algoritmo fuera polilogarítmico en $\kappa$ entonces los problemas que tienen solución sobre n qubits podrían resolverse en tiempo poly(n). Haciendo que la fase de complejidad BQP sea igual a PSPACE.​

Análisis del error

La realización de la estimación de fase, que es la fuente dominante de error, se hace simulando $e^{iAt}$. Asumiendo que $A$ es s-dispersa, esta puede ser realizada con un error acotado por la constante $\varepsilon$, la cual que se traducirá en el error aditivo logrado en el estado de salida $|x\rangle$.

El paso de estimación de fase falla del $O\left({\frac {1}{t_{0}}}\right)$ en la estimación de$\lambda$, lo cual se traslada dentro del error relativo a $O\left({\frac {1}{\lambda t_{0}}}\right)$ como $\lambda ^{-1}$. Si $\lambda \geq 1/\kappa$, tomando $t_{0}=O(\kappa \varepsilon )$, induce un error final $\varepsilon$. Esto requiere que el tiempo total de ejecución sea incrementado proporcionalmente a $O\left({\frac {1}{\varepsilon }}\right)$ para minimizar el error.

Realización experimental

Si bien aún no existe un ordenador cuántico que realmente pueda ofrecer un aumento de velocidad sobre la computadora clásica, la implementación de una "prueba de concepto" sigue siendo un hito importante en el desarrollo de un nuevo algoritmo cuántico. Demostrar el algoritmo cuántico para sistemas de ecuaciones lineales seguía siendo un desafío en los años posteriores a su propuesta hasta que en el año 2013 fue demostrado por Cai et al., Barz et al. y Pan et al. en paralelo.

Cai et al.

Publicado en Physical Review Letters 110, 230501 (2013), Cai et al. informaron de una demostración experimental del ejemplo significativo más simple de este algoritmo, esto es, resolvieron un sistema de ecuaciones lineales 2*2 para varios vectores de entrada. El circuito cuántico está optimizado y compilado dentro de una red óptica lineal con cuatro bits fotónicos (qubits) y cuatro puertas lógicas controladas, las cuales son usadas para implementar coherentemente todas las subrutinas de este algoritmo. Para varios vectores de entrada, la computación cuántica da soluciones para las ecuaciones lineales con precisión razonablemente alta, que van desde fidelidades de 0.825 to 0.993.

Barz et al.

El 5 de febrero, 2013 Barz et al. demostraron el algoritmo cuántico para un sistema lineal de ecuaciones sobre una arquitectura de computación cuántica fotónica. Esta implementación uso dos puertas entrelazadas consecutivas sobre el mismo par de qubits con codificación en la polarización. Se utilizaron dos puertas separadas NOT-controladas donde la operación exitosa de la primera era anunciada por una medida sobre dos fotones auxiliares. Barz et al. encontraron que la fidelidad en el estado de salida varió desde el 64.4% al 98.1% debido a la influencia de las emisiones de orden superior por conversión paramétrica descendente espontánea.​

Pan et al.

El 8 de febrero, 2013 Pan et al. informaron de una prueba experimental de concepto del algoritmo cuántico utilizando un procesador de información cuántica de resonancia magnética nuclear de 4 qubit. La aplicación fue probada usando sistemas lineales simples de solo 2 variables. A través de tres experimentos obtuvieron el vector solución con más de 96% de fidelidad.​

Aplicaciones

Los ordenadores cuánticos son dispositivos que aprovechan la mecánica cuántica para realizar cálculos en formas que los ordenadores clásicos no pueden. Para ciertos problemas, los algoritmos cuánticos proporcionan aceleraciones exponenciales respecto a sus homólogos clásicos, el ejemplo más famoso es el algoritmo de factorización de Shor. Pocas de estas aceleraciones son conocidas, y las que lo son (como el uso de las computadoras cuánticas para simular otros sistemas cuánticos) han encontrado hasta ahora un uso limitado fuera del dominio de la mecánica cuántica. Este algoritmo proporciona un método exponencialmente rápido para estimar las características de la solución de un conjunto de ecuaciones lineal, el cual es un problema omnipresente en la ciencia de ingeniería, tanto en sí mismo como siendo una subrutina de problemas más complejos.

Resolución de ecuaciones diferenciales lineales

Domic Berry propuso un nuevo algoritmo para resolver ecuaciones diferenciales lineales dependientes del tiempo como una extensión del algoritmo cuántico para resolver sistemas de ecuaciones lineales. Berry proporciona un algoritmo eficiente para resolver la evolución a tiempo completo bajo ecuaciones diferenciales lineales dispersas sobre un ordenador cuántico.​

Mínimos cuadrados apropiados

Wiebe et al. proporcionan un nuevo algoritmo cuántico para determinar la calidad de los mínimos cuadrados de una función continua utilizada para aproximar un conjunto de puntos discretos, aplicando el algoritmo cuántico para sistemas de ecuaciones lineales. Al aumentar la cantidad de puntos discretos, el tiempo requerido para producir el ajuste de mínimos cuadrados usando incluso un ordenador cuántico que ejecuta un algoritmo cuántico de estado tomográfico se hace muy grande. Weibe et al. encontraron que en muchos casos, su algoritmo puede encontrar de una manera eficiente una concisa aproximación a los puntos dados, eliminando la necesidad del algoritmo tomográfico de mayor complejidad.​

Aprendizaje automático y análisis de Big Data

El aprendizaje automático es el estudio de los sistemas que pueden identificar tendencias en los datos. Las tareas del aprendizaje automático involucran frecuentemente manipulación y clasificación de grandes volúmenes de datos en espacios vectoriales de grandes dimensiones. El tiempo de ejecución de los algoritmos de aprendizaje automático clásicos está limitado por la dependencia polinómica de ambos, volumen de datos y dimensiones del espacio. Los computadores cuánticos son capaces de manipular vectores de grandes dimensiones usando el producto tensorial de espacios, por lo que son la plataforma perfecta para los algoritmos de aprendizaje automático.​

El algoritmo cuántico para sistemas de ecuaciones lineales se ha aplicado a una máquina de soporte vectorial, la cual es una optimización lineal de la clasificación binaria no lineal. Una máquina de soporte vectorial se puede utilizar para el aprendizaje automático supervisado, en el cual se encuentra disponible un conjunto de datos de entrenamiento ya clasificado, o en el aprendizaje no supervisado, en el cual todos los datos del sistema están no clasificados. Rebentrost et al. demostraron que una máquina de soporte vectorial cuántica se puede utilizar en la clasificación de big data, para lograr una aceleración exponencial con respecto a los ordenadores clásicos.​

En junio de 2018, Zhao et al. desarrollaron un algorithmo para realizar entrenamiento Bayesiano de redes neuronales profundas en ordenadores cuánticos con una ventaja exponencial con respecto al entrenamiento clásico, gracias al uso del algoritmo cuántico para sistemas de ecuaciones lineales. En dicho trabajo también se presenta la primera implementación genérica del algoritmo, que es ejecutada en ordenadores cuánticos en la nube.​

Referencias

• Datos: Q17083575