Algoritmo HHL

Algoritmo de álgebra lineal cuántica que ofrece aceleración exponencial en determinadas condiciones

El algoritmo Harrow–Hassidim–Lloyd o algoritmo HHL es un algoritmo cuántico para resolver numéricamente un sistema de ecuaciones lineales , diseñado por Aram Harrow , Avinatan Hassidim y Seth Lloyd . El algoritmo estima el resultado de una medición escalar en el vector solución de un sistema de ecuaciones lineales dado. ^[1]

El algoritmo es uno de los principales algoritmos fundamentales que se espera que proporcione una aceleración sobre sus contrapartes clásicas, junto con el algoritmo de factorización de Shor , el algoritmo de búsqueda de Grover y la transformada cuántica de Fourier . Siempre que el sistema lineal sea disperso ^{[2] y tenga un} número de condición bajo , y que el usuario esté interesado en el resultado de una medición escalar en el vector solución, en lugar de los valores del vector solución en sí, entonces el algoritmo tiene un tiempo de ejecución de , donde es el número de variables en el sistema lineal. Esto ofrece una aceleración exponencial sobre el algoritmo clásico más rápido, que se ejecuta en (o para matrices semidefinidas positivas). ${\displaystyle \kappa }$ ${\displaystyle O(\log(N)\kappa ^{2})}$ ${\displaystyle N}$ ${\displaystyle O(N\kappa )}$ ${\displaystyle O(N{\sqrt {\kappa }})}$

En 2013, tres publicaciones independientes demostraron por primera vez una implementación del algoritmo cuántico para sistemas lineales de ecuaciones. ^{[3] [4] [5]} Las demostraciones consistieron en ecuaciones lineales simples en dispositivos cuánticos especialmente diseñados. ^{[3] [4] [5]} La primera demostración de una versión de propósito general del algoritmo apareció en 2018. ^[6]

Debido a la prevalencia de sistemas lineales en prácticamente todas las áreas de la ciencia y la ingeniería, el algoritmo cuántico para sistemas lineales de ecuaciones tiene el potencial de una aplicabilidad generalizada. ^[7]

Procedimiento

El algoritmo HHL aborda el siguiente problema: dada una matriz hermítica y un vector unitario , preparar el estado cuántico correspondiente al vector que resuelve el sistema lineal . Más precisamente, el objetivo es preparar un estado cuyas amplitudes sean iguales a los elementos de . Esto significa, en particular, que el algoritmo no se puede utilizar para recuperar de manera eficiente el vector en sí. Sin embargo, permite calcular de manera eficiente valores esperados de la forma para algún observable . ${\displaystyle N\times N}$ ${\displaystyle A}$ ${\displaystyle {\vec {b}}\in \mathbb {R} ^{N}}$ ${\displaystyle |x\rangle }$ ${\displaystyle {\vec {x}}\in \mathbb {R} ^{N}}$ ${\displaystyle A{\vec {x}}={\vec {b}}}$ ${\displaystyle |x\rangle }$ ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {x}}}$ ${\displaystyle \langle x|M|x\rangle }$ ${\displaystyle M}$

En primer lugar, el algoritmo representa el vector como un estado cuántico de la forma: ${\displaystyle {\vec {b}}}$

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

A continuación, se utilizan técnicas de simulación hamiltoniana para aplicar el operador unitario a para una superposición de diferentes tiempos . La capacidad de descomponer en la base propia de y encontrar los valores propios correspondientes se facilita mediante el uso de la estimación de fase cuántica . ${\displaystyle e^{iAt}}$ ${\displaystyle |b\rangle }$ ${\displaystyle t}$ ${\displaystyle |b\rangle }$ ${\displaystyle A}$ ${\displaystyle \lambda _{j}}$

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

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

donde es la base del vector propio de , y . ${\displaystyle u_{j}}$ ${\displaystyle A}$ ${\displaystyle |b\rangle =\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle }$

A continuación, nos gustaría realizar el mapeo lineal tomando como , donde es una constante normalizadora. La operación de mapeo lineal no es unitaria y, por lo tanto, requerirá una cantidad de repeticiones, ya que tiene cierta probabilidad de fallar. Una vez que tiene éxito, descompilamos el registro y nos queda un estado proporcional a: ${\displaystyle |\lambda _{j}\rangle }$ ${\displaystyle C\lambda _{j}^{-1}|\lambda _{j}\rangle }$ ${\displaystyle C}$ ${\displaystyle |\lambda _{j}\rangle }$

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

donde es una representación mecánico-cuántica del vector solución deseado  x . Para leer todos los componentes de x se requeriría repetir el procedimiento al menos N veces. Sin embargo, a menudo sucede que uno no está interesado en sí mismo, sino más bien en algún valor esperado de un operador lineal M que actúa sobre  x . Al asignar M a un operador mecánico-cuántico y realizar la medición cuántica correspondiente a M , obtenemos una estimación del valor esperado . Esto permite extraer una amplia variedad de características del vector x , incluida la normalización, los pesos en diferentes partes del espacio de estados y los momentos sin calcular realmente todos los valores del vector solución  x . ${\displaystyle |x\rangle }$ ${\displaystyle x}$ ${\displaystyle \langle x|M|x\rangle }$

Explicación

Inicialización

En primer lugar, el algoritmo requiere que la matriz sea hermítica para que pueda convertirse en un operador unitario . En el caso de que no sea hermítica, defina ${\displaystyle A}$ ${\displaystyle A}$

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

Como es hermítico, ahora el algoritmo se puede utilizar para resolver y obtener . ${\displaystyle C}$ ${\displaystyle Cy={\begin{bmatrix}b\\0\end{bmatrix}}}$ ${\displaystyle y={\begin{bmatrix}0\\x\end{bmatrix}}}$

En segundo lugar, el algoritmo requiere un procedimiento eficiente para preparar , la representación cuántica de b. Se supone que existe algún operador lineal que puede tomar algún estado cuántico arbitrario de manera eficiente o que este algoritmo es una subrutina en un algoritmo más grande y se proporciona como entrada. Cualquier error en la preparación del estado se ignora. ${\displaystyle |b\rangle }$ ${\displaystyle B}$ ${\displaystyle |\mathrm {initial} \rangle }$ ${\displaystyle |b\rangle }$ ${\displaystyle |b\rangle }$ ${\displaystyle |b\rangle }$

Finalmente, el algoritmo supone que el estado se puede preparar de manera eficiente, donde ${\displaystyle |\psi _{0}\rangle }$

${\displaystyle |\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 algunos grandes . Los coeficientes de se eligen para minimizar una cierta función de pérdida cuadrática que induce un error en la subrutina descrita a continuación. ${\displaystyle T}$ ${\displaystyle |\psi _{0}\rangle }$ ${\displaystyle U_{\mathrm {invert} }}$

Simulación hamiltoniana

La simulación hamiltoniana se utiliza para transformar la matriz hermítica en un operador unitario, que luego se puede aplicar a voluntad. Esto es posible si A es s -disperso y eficientemente computable por filas, lo que significa que tiene como máximo s entradas distintas de cero por fila y, dado un índice de fila, estas entradas se pueden calcular en tiempo O( s ). Bajo estos supuestos, la simulación hamiltoniana cuántica permite simular en tiempo . ${\displaystyle A}$ ${\displaystyle e^{iAt}}$ ${\displaystyle O(\log(N)s^{2}t)}$

U invertida subrutina

La subrutina clave del algoritmo, denominada , se define de la siguiente manera e incorpora una subrutina de estimación de fase : ${\displaystyle U_{\mathrm {invert} }}$

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

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

3. Aplique la transformada de Fourier al registro  C. Denote los estados base resultantes con para k  = 0, ...,  T  − 1. Defina . ${\displaystyle |k\rangle }$ ${\displaystyle \lambda _{k}:=2\pi k/t_{0}}$

4. Adjuntar un registro tridimensional S en el estado

${\displaystyle |h(\lambda _{k})\rangle ^{S}:={\sqrt {1-f(\lambda _{k})^{2}-g(\lambda _{k})^{2}}}|\mathrm {nothing} \rangle ^{S}+f(\lambda _{k})|\mathrm {well} \rangle ^{S}+g(\lambda _{k})|\mathrm {ill} \rangle ^{S},}$

5. Invierta los pasos 1 a 3, descompilando cualquier basura producida en el camino.

El procedimiento de estimación de fase en los pasos 1 a 3 permite la estimación de valores propios de A hasta un error de . ${\displaystyle \epsilon }$

El registro ancilla en el paso 4 es necesario para construir un estado final con valores propios invertidos correspondientes a la inversa diagonalizada de A . En este registro, las funciones f , g , se denominan funciones de filtro. Los estados 'nothing', 'well' y 'ill' se utilizan para indicar al cuerpo del bucle cómo proceder; 'nothing' indica que la inversión de matriz deseada aún no se ha producido, 'well' indica que la inversión se ha producido y el bucle debe detenerse, y 'ill' indica que parte de está en el subespacio mal condicionado de A y el algoritmo no podrá producir la inversión deseada. Para producir un estado proporcional a la inversa de A es necesario medir 'well', después de lo cual el estado general del sistema colapsa al estado deseado por la regla de Born extendida . ${\displaystyle |b\rangle }$

Bucle principal

El cuerpo del algoritmo sigue el procedimiento de amplificación de amplitud : comenzando con , se aplica repetidamente la siguiente operación: ${\displaystyle U_{\mathrm {invert} }B|\mathrm {initial} \rangle }$

${\displaystyle U_{\mathrm {invert} }BR_{\mathrm {init} }B^{\dagger }U_{\mathrm {invert} }^{\dagger }R_{\mathrm {succ} },}$

dónde

${\displaystyle R_{\mathrm {succ} }=I-2|\mathrm {well} \rangle \langle \mathrm {well} |}$

y

${\displaystyle R_{\mathrm {init} }=I-2|\mathrm {initial} \rangle \langle \mathrm {initial} |.}$

Después de cada repetición, se mide y producirá un valor de "nada", "bien" o "mal", como se describió anteriormente. Este ciclo se repite hasta que se mide , lo que ocurre con una probabilidad de . En lugar de repetir las veces para minimizar el error, se utiliza la amplificación de amplitud para lograr la misma resistencia al error utilizando solo repeticiones. ${\displaystyle S}$ ${\displaystyle |\mathrm {well} \rangle }$ ${\displaystyle p}$ ${\displaystyle {\frac {1}{p}}}$ ${\displaystyle O\left({\frac {1}{\sqrt {p}}}\right)}$

Medición escalar

Después de medir con éxito 'bien' el sistema estará en un estado proporcional a: ${\displaystyle S}$

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

Finalmente, ejecutamos el operador mecánico-cuántico correspondiente a M y obtenemos una estimación del valor de . ${\displaystyle \langle x|M|x\rangle }$

Análisis del tiempo de ejecución

Eficiencia clásica

El mejor algoritmo clásico que produce el vector de solución real es la eliminación gaussiana , que se ejecuta en el tiempo. ${\displaystyle {\vec {x}}}$ ${\displaystyle O(N^{3})}$

Si A es s -escaso y semidefinido positivo, entonces se puede utilizar el método del gradiente conjugado para encontrar el vector solución , que se puede encontrar en el tiempo minimizando la función cuadrática . ${\displaystyle {\vec {x}}}$ ${\displaystyle O(Ns\kappa )}$ ${\displaystyle |A{\vec {x}}-{\vec {b}}|^{2}}$

Cuando solo se necesita una estadística de resumen del vector solución , como es el caso del algoritmo cuántico para sistemas lineales de ecuaciones, una computadora clásica puede encontrar una estimación de en . ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {x}}^{\dagger }M{\vec {x}}}$ ${\displaystyle O(N{\sqrt {\kappa }})}$

Eficiencia cuántica

Se demostró que el tiempo de ejecución del algoritmo cuántico para resolver sistemas de ecuaciones lineales propuesto originalmente por Harrow et al. era , donde es el parámetro de error y es el número de condición de . Esto fue mejorado posteriormente a por Andris Ambainis ^[8] y un algoritmo cuántico con polinomio de tiempo de ejecución en fue desarrollado por Childs et al. ^[9] Dado que el algoritmo HHL mantiene su escala logarítmica en solo para matrices dispersas o de bajo rango, Wossnig et al. ^[10] extendieron el algoritmo HHL basado en una técnica de estimación de valor singular cuántico y proporcionaron un algoritmo de sistema lineal para matrices densas que se ejecuta en el tiempo en comparación con el del algoritmo HHL estándar. ${\displaystyle O(\kappa ^{2}\log N/\varepsilon )}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \kappa }$ ${\displaystyle A}$ ${\displaystyle O(\kappa \log ^{3}\kappa \log N/\varepsilon ^{3})}$ ${\displaystyle \log(1/\varepsilon )}$ ${\displaystyle N}$ ${\displaystyle O({\sqrt {N}}\log N\kappa ^{2})}$ ${\displaystyle O(N\log N\kappa ^{2})}$

Optimalidad

Un factor importante en el rendimiento del algoritmo de inversión de matrices es el número de condición , que representa la relación entre los valores propios más grandes y más pequeños de . A medida que aumenta el número de condición, disminuye la facilidad con la que se puede encontrar el vector solución utilizando métodos de descenso de gradiente como el método de gradiente conjugado , ya que se acerca a una matriz que no se puede invertir y el vector solución se vuelve menos estable. Este algoritmo supone que todos los valores singulares de la matriz se encuentran entre y 1, en cuyo caso se alcanzará el tiempo de ejecución declarado proporcional a . Por lo tanto, la aceleración sobre los algoritmos clásicos aumenta aún más cuando es a . ^[1] ${\displaystyle \kappa }$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle {\frac {1}{\kappa }}}$ ${\displaystyle \kappa ^{2}}$ ${\displaystyle \kappa }$ ${\displaystyle \mathrm {poly} (\log(N))}$

Si el tiempo de ejecución del algoritmo se hiciera polilogarítmico, entonces los problemas resolubles en n qubits podrían resolverse en tiempo poli( n ), lo que haría que la clase de complejidad BQP fuera igual a PSPACE . ^[1] ${\displaystyle \kappa }$

Análisis de errores

La simulación hamiltoniana, que es la fuente dominante de error, se realiza simulando . Suponiendo que es s-disperso, esto se puede hacer con un error limitado por una constante , que se traducirá en el error aditivo logrado en el estado de salida . ${\displaystyle e^{iAt}}$ ${\displaystyle A}$ ${\displaystyle \varepsilon }$ ${\displaystyle |x\rangle }$

El paso de estimación de fase comete un error al estimar , lo que se traduce en un error relativo de en . Si , tomar induce un error final de . Esto requiere que la eficiencia general del tiempo de ejecución se incremente proporcionalmente a para minimizar el error. ${\displaystyle O\left({\frac {1}{t_{0}}}\right)}$ ${\displaystyle \lambda }$ ${\displaystyle O\left({\frac {1}{\lambda t_{0}}}\right)}$ ${\displaystyle \lambda ^{-1}}$ ${\displaystyle \lambda \geq 1/\kappa }$ ${\displaystyle t_{0}=O(\kappa \varepsilon )}$ ${\displaystyle \varepsilon }$ ${\displaystyle O\left({\frac {1}{\varepsilon }}\right)}$

Realización experimental

Si bien aún no existe un ordenador cuántico que realmente pueda ofrecer una aceleración superior a la de un ordenador clásico, 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 lineales de ecuaciones siguió siendo un desafío durante años después de su propuesta hasta 2013, cuando fue demostrado por Cai et al., Barz et al. y Pan et al. en paralelo.

Cai y otros.

Cai et al. publicaron en Physical Review Letters 110, 230501 (2013) una demostración experimental de la instancia más simple y significativa de este algoritmo, es decir, la solución de ecuaciones lineales para varios vectores de entrada. El circuito cuántico se optimiza y compila en una red óptica lineal con cuatro bits cuánticos fotónicos (qubits) y cuatro puertas lógicas controladas, que se utiliza para implementar de manera coherente cada subrutina para este algoritmo. Para varios vectores de entrada, la computadora cuántica brinda soluciones para las ecuaciones lineales con una precisión razonablemente alta, que varía desde fidelidades de 0,825 a 0,993. ^[11] ${\displaystyle 2\times 2}$

Barz y otros.

El 5 de febrero de 2013, Stefanie Barz y sus colaboradores demostraron el algoritmo cuántico para sistemas lineales de ecuaciones en una arquitectura de computación cuántica fotónica. Esta implementación utilizó dos puertas entrelazadas consecutivas en el mismo par de cúbits codificados por polarización. Se implementaron dos puertas NOT controladas por separado, donde la operación exitosa de la primera fue anunciada por una medición de dos fotones auxiliares. Barz et al. descubrieron que la fidelidad en el estado de salida obtenido oscilaba entre el 64,7 % y el 98,1 % debido a la influencia de emisiones de orden superior de la conversión descendente paramétrica espontánea. ^[4]

Pan y otros.

El 8 de febrero de 2013, Pan et al. informaron sobre una demostración experimental de prueba de concepto del algoritmo cuántico utilizando un procesador de información cuántica de resonancia magnética nuclear de 4 qubits. La implementación se probó utilizando sistemas lineales simples de solo 2 variables. A lo largo de tres experimentos, obtuvieron el vector de solución con una fidelidad superior al 96 %. ^[5]

Wen y otros.

^{Wen et al. [12]} informaron en 2018 otra demostración experimental que utiliza RMN para resolver un sistema 8*8 utilizando el algoritmo desarrollado por Subaşı et al. ^[13].

Aplicaciones

Los ordenadores cuánticos son dispositivos que aprovechan la mecánica cuántica para realizar cálculos de una manera que los ordenadores clásicos no pueden. Para determinados problemas, los algoritmos cuánticos proporcionan aceleraciones exponenciales con respecto a sus homólogos clásicos; el ejemplo más famoso es el algoritmo de factorización de Shor. Se conocen pocas aceleraciones exponenciales de este tipo, y las que se conocen (como el uso de ordenadores cuánticos para simular otros sistemas cuánticos) hasta ahora han encontrado un uso práctico limitado debido al pequeño tamaño actual de los ordenadores cuánticos. Este algoritmo proporciona un método exponencialmente más rápido para estimar las características de la solución de un conjunto de ecuaciones lineales, que es un problema omnipresente en la ciencia y la ingeniería, tanto por sí solo como como subrutina en problemas más complejos.

Dispersión electromagnética

Clader et al. proporcionaron una versión preacondicionada del algoritmo de sistemas lineales que proporcionó dos avances. En primer lugar, demostraron cómo se podía incluir un preacondicionador dentro del algoritmo cuántico. Esto amplía la clase de problemas que pueden lograr la aceleración exponencial prometida, ya que el escalamiento de HHL y los mejores algoritmos clásicos son ambos polinómicos en el número de condición . El segundo avance fue la demostración de cómo utilizar HHL para resolver la sección transversal de radar de una forma compleja. Este fue uno de los primeros ejemplos de extremo a extremo de cómo utilizar HHL para resolver un problema concreto exponencialmente más rápido que el mejor algoritmo clásico conocido. ^[14]

Solución de ecuaciones diferenciales lineales

Dominic Berry propuso un nuevo algoritmo para resolver ecuaciones diferenciales lineales dependientes del tiempo como una extensión del algoritmo cuántico para resolver sistemas lineales de ecuaciones. Berry proporciona un algoritmo eficiente para resolver la evolución en tiempo completo bajo ecuaciones diferenciales lineales dispersas en una computadora cuántica. ^[15]

Resolución de ecuaciones diferenciales no lineales

Dos grupos propusieron ^[16] algoritmos eficientes para integrar numéricamente ecuaciones diferenciales ordinarias no lineales disipativas. Liu et al. ^[17] utilizaron la técnica de linealización de Carleman para ecuaciones de segundo orden y Lloyd et al. ^[18] emplearon un método de linealización de campo medio inspirado en la ecuación no lineal de Schrödinger para no linealidades de orden general. Las ecuaciones lineales resultantes se resuelven utilizando algoritmos cuánticos para ecuaciones diferenciales lineales.

Método de elementos finitos

El método de elementos finitos utiliza grandes sistemas de ecuaciones lineales para encontrar soluciones aproximadas a varios modelos físicos y matemáticos. Montanaro y Pallister demuestran que el algoritmo HHL, cuando se aplica a ciertos problemas FEM, puede lograr una aceleración cuántica polinómica. Sugieren que una aceleración exponencial no es posible en problemas con dimensiones fijas y para los cuales la solución cumple ciertas condiciones de suavidad.

Las aceleraciones cuánticas para el método de elementos finitos son mayores para problemas que incluyen soluciones con derivadas de orden superior y grandes dimensiones espaciales. Por ejemplo, los problemas en dinámica de muchos cuerpos requieren la solución de ecuaciones que contienen derivadas en órdenes que escalan con el número de cuerpos, y algunos problemas en finanzas computacionales , como los modelos de Black-Scholes , requieren grandes dimensiones espaciales. ^[19]

Ajuste por mínimos cuadrados

Wiebe et al. proporcionan un nuevo algoritmo cuántico para determinar la calidad de un ajuste de mínimos cuadrados en el que se utiliza una función continua para aproximar un conjunto de puntos discretos mediante la extensión del algoritmo cuántico para sistemas lineales de ecuaciones. A medida que aumenta el número de puntos discretos, el tiempo necesario para producir un ajuste de mínimos cuadrados utilizando incluso una computadora cuántica que ejecute un algoritmo de tomografía de estados cuánticos se vuelve muy grande. Wiebe et al. descubren que, en muchos casos, su algoritmo puede encontrar de manera eficiente una aproximación concisa de los puntos de datos, eliminando la necesidad del algoritmo de tomografía de mayor complejidad. ^[20]

Aprendizaje automático y análisis de big data

El aprendizaje automático es el estudio de sistemas que pueden identificar tendencias en los datos. Las tareas del aprendizaje automático con frecuencia implican la manipulación y clasificación de un gran volumen de datos en espacios vectoriales de alta dimensión. El tiempo de ejecución de los algoritmos de aprendizaje automático clásicos está limitado por una dependencia polinómica tanto del volumen de datos como de las dimensiones del espacio. Las computadoras cuánticas son capaces de manipular vectores de alta dimensión utilizando espacios de productos tensoriales y, por lo tanto, son plataformas adecuadas para algoritmos de aprendizaje automático. ^[21]

El algoritmo cuántico para sistemas lineales de ecuaciones se ha aplicado a una máquina de vectores de soporte, que es un clasificador binario lineal o no lineal optimizado. Una máquina de vectores de soporte se puede utilizar para el aprendizaje automático supervisado, en el que se dispone de un conjunto de entrenamiento de datos ya clasificados, o para el aprendizaje automático no supervisado, en el que todos los datos proporcionados al sistema no están clasificados. Rebentrost et al. muestran que una máquina de vectores de soporte cuántico se puede utilizar para la clasificación de big data y lograr una aceleración exponencial con respecto a las computadoras clásicas. ^[22]

En junio de 2018, Zhao et al. desarrollaron un algoritmo para realizar el entrenamiento bayesiano de redes neuronales profundas en computadoras cuánticas con una aceleración exponencial sobre el entrenamiento clásico debido al uso del algoritmo cuántico para sistemas lineales de ecuaciones, ^[6] proporcionando también la primera implementación de propósito general del algoritmo que se ejecutará en computadoras cuánticas basadas en la nube . ^[23]

Finanzas

Las propuestas para utilizar HHL en finanzas incluyen la resolución de ecuaciones diferenciales parciales para la ecuación de Black-Scholes y la determinación de la optimización de la cartera a través de una solución de Markowitz . ^[24]

Química cuántica

En 2023, Baskaran et al. propusieron el uso del algoritmo HHL para los cálculos de química cuántica, a través del método de clúster acoplado linealizado (LCC). ^[25] La conexión entre el algoritmo HHL y el método LCC se debe al hecho de que este último se puede reformular en forma de sistema de ecuaciones lineales. Un factor clave que hace que este enfoque sea útil para la química cuántica es que el número de qubits del registro de estado es el logaritmo natural del número de excitaciones, lo que ofrece una supresión exponencial en el número de qubits requeridos en comparación con el solucionador de eigens cuánticos variacionales o los algoritmos de estimación de fase cuántica . Esto conduce a una "coexistencia a través de escalas", donde en una era de computación cuántica dada, HHL-LCC podría aplicarse a sistemas mucho más grandes, mientras que QPE- CASCI podría emplearse para sistemas moleculares más pequeños, pero con mejor precisión en la predicción de propiedades moleculares. Desde el punto de vista algorítmico, los autores introducen el enfoque 'AdaptHHL', que evita la necesidad de gastar una sobrecarga clásica de ~Ο(N ³ ) asociada con la fijación de un valor para el parámetro 'c' en el módulo de rotación controlada del algoritmo.

Crítica

Reconociendo la importancia del algoritmo HHL en el campo del aprendizaje automático cuántico , Scott Aaronson ^[26] analiza las advertencias y los factores que podrían limitar la ventaja cuántica real del algoritmo.

1. El vector de solución, , tiene que prepararse de manera eficiente en el estado cuántico. Si el vector no es casi uniforme, la preparación del estado probablemente sea costosa y, si se toman medidas, la ventaja exponencial de HHL desaparecería. ${\displaystyle |b\rangle }$ ${\displaystyle O(n^{c})}$
2. Las fases de QPE requieren la generación de la matriz unitaria y su aplicación controlada. La eficiencia de este paso depende de que la matriz sea dispersa y esté "bien acondicionada" (baja ). De lo contrario, la aplicación de crecería a medida que aumentaba y, una vez más, la ventaja cuántica del algoritmo desaparecería. ${\displaystyle e^{iAt}}$ ${\displaystyle A}$ ${\displaystyle \kappa }$ ${\displaystyle e^{iAt}}$ ${\displaystyle O(n^{c})}$
3. Por último, el vector, , no es fácilmente accesible. El algoritmo HHL permite aprender un 'resumen' del vector, es decir, el resultado de medir la expectativa de un operador . Si se necesitan valores reales de , entonces HHL debería repetirse varias veces, lo que eliminaría la aceleración exponencial. Sin embargo, se han propuesto tres formas de evitar obtener los valores reales: primero, si solo se necesitan algunas propiedades de la solución; ^[27] segundo, si los resultados se necesitan solo para alimentar operaciones matriciales posteriores; tercero, si solo se necesita una muestra de la solución. ^[28] ${\displaystyle |x\rangle }$ ${\displaystyle \langle x|M|x\rangle }$ ${\displaystyle {\vec {x}}}$ ${\displaystyle O(n)}$

Véase también

• Programación diferenciable

Referencias

1. Harrow, Aram W; Hassidim, Avinatan; Lloyd, Seth (2008). "Algoritmo cuántico para sistemas lineales de ecuaciones". Physical Review Letters . 103 (15): 150502. arXiv : 0811.3171 . Código Bibliográfico :2009PhRvL.103o0502H. doi :10.1103/PhysRevLett.103.150502. PMID  19905613. S2CID  5187993.
2. Johnston, Eric (3 de julio de 2019). Programación de computadoras cuánticas: algoritmos esenciales y ejemplos de código. O'Reilly Media . p. 267. ISBN 9781492039655.
3. Cai, X.-D; Weedbrook, C; Su, Z.-E; Chen, M.-C; Gu, Mile; Zhu, M.-J; Li, Li; Liu, Nai-Le; Lu, Chao-Yang; Pan, Jian-Wei (2013). "Computación cuántica experimental para resolver sistemas de ecuaciones lineales". Physical Review Letters . 110 (23): 230501. arXiv : 1302.4310 . Código Bibliográfico :2013PhRvL.110w0501C. doi :10.1103/PhysRevLett.110.230501. PMID  25167475. S2CID  20427454.
4. Barz, Stefanie; Kassal, Ivan; Ringbauer, Martin; Lipp, Yannick Ole; Dakić, Borivoje; Aspuru-Guzik, Alán; Walther, Philip (2014). "Un procesador cuántico fotónico de dos qubits y su aplicación para resolver sistemas de ecuaciones lineales". Scientific Reports . 4 : 6115. arXiv : 1302.1210 . Bibcode :2014NatSR...4E6115B. doi :10.1038/srep06115. ISSN  2045-2322. PMC 4137340 . PMID  25135432. 
5. Pan, Jian; Cao, Yudong; Yao, Xiwei; Li, Zhaokai; Ju, Chenyong; Peng, Xinhua; Kais, Sabre; Du, Jiangfeng; Du, Jiangfeng (2014). "Realización experimental de un algoritmo cuántico para resolver sistemas lineales de ecuaciones". Physical Review A . 89 (2): 022313. arXiv : 1302.1946 . Código Bibliográfico :2014PhRvA..89b2313P. doi :10.1103/PhysRevA.89.022313. S2CID  14303240.
6. Zhao, Zhikuan; Pozas-Kerstjens, Alejandro; Rebentrost, Patrick; Wittek, Peter (2019). "Aprendizaje profundo bayesiano en una computadora cuántica". Inteligencia artificial cuántica . 1 (1–2): 41–51. arXiv : 1806.11463 . doi :10.1007/s42484-019-00004-7. S2CID  49554188.
7. La computadora cuántica ejecuta el algoritmo cuántico más útil en la práctica, por Lu y Pan.
8. Ambainis, Andris (2010). "Amplificación de amplitud de tiempo variable y un algoritmo cuántico más rápido para resolver sistemas de ecuaciones lineales". arXiv : 1010.4458 [quant-ph].
9. Childs, Andrew M.; Kothari, Robin; Somma, Rolando D. (2017). "Algoritmo cuántico para sistemas de ecuaciones lineales con dependencia exponencialmente mejorada de la precisión". Revista SIAM de Computación . 46 (6): 1920–1950. arXiv : 1511.02306 . doi :10.1137/16m1087072. ISSN  0097-5397. S2CID  3834959.
10. Wossnig, Leonard; Zhao, Zhikuan; Prakash, Anupam (2018). "Un algoritmo de sistema lineal cuántico para matrices densas". Physical Review Letters . 120 (5): 050502. arXiv : 1704.06174 . Código Bibliográfico :2018PhRvL.120e0502W. doi :10.1103/PhysRevLett.120.050502. PMID  29481180. S2CID  3714239.
11. Cai, X. -D; Weedbrook, Christian; Su, Z. -E; Chen, M. -C; Gu, Mile; Zhu, M. -J; Li, L; Liu, N. -L; Lu, Chao-Yang; Pan, Jian-Wei (2013). "Computación cuántica experimental para resolver sistemas de ecuaciones lineales". Physical Review Letters . 110 (23): 230501. arXiv : 1302.4310 . Código Bibliográfico :2013PhRvL.110w0501C. doi :10.1103/PhysRevLett.110.230501. PMID  25167475. S2CID  20427454.
12. Jingwei Wen, Xiangyu Kong, Shijie Wei, Bixue Wang, Tao Xin y Guilu Long (2019). "Realización experimental de algoritmos cuánticos para un sistema lineal inspirado en la computación cuántica adiabática". Phys. Rev. A 99 , 012320.
13. Subaşı, Yiğit; Somma, Rolando D.; Orsucci, Davide (14 de febrero de 2019). "Algoritmos cuánticos para sistemas de ecuaciones lineales inspirados en la computación cuántica adiabática". Physical Review Letters . 122 (6): 060504. arXiv : 1805.10549 . Código Bibliográfico :2019PhRvL.122f0504S. doi :10.1103/physrevlett.122.060504. ISSN  0031-9007. PMID  30822089. S2CID  73493666.
14. Clader, B. D; Jacobs, B. C; Sprouse, C. R (2013). "Algoritmo de sistema lineal cuántico preacondicionado". Physical Review Letters . 110 (25): 250504. arXiv : 1301.2340 . Código Bibliográfico :2013PhRvL.110y0504C. doi :10.1103/PhysRevLett.110.250504. PMID  23829722. S2CID  33391978.
15. Berry, Dominic W (2010). "Algoritmo cuántico de orden superior para resolver ecuaciones diferenciales lineales". Journal of Physics A: Mathematical and Theoretical . 47 (10): 105301. arXiv : 1010.2745 . Bibcode :2014JPhA...47j5301B. doi :10.1088/1751-8113/47/10/105301. S2CID  17623971.
16. Levy, Max G. (5 de enero de 2021). «Los nuevos algoritmos cuánticos finalmente resuelven ecuaciones no lineales». Revista Quanta . Consultado el 31 de diciembre de 2022 .
17. Liu, JP; Kolden, H.Ø.; Krovi, HK; Loureiro, NF; Trivisa, K.; Childs, AM (2021). "Algoritmo cuántico eficiente para ecuaciones diferenciales no lineales disipativas". PNAS . 118 (35): e2026805118. arXiv : 2011.03185 . Bibcode :2021PNAS..11826805L. doi : 10.1073/pnas.2026805118 . PMC 8536387 . PMID  34446548. 
18. Lloyd, S.; De Palma, G.; Gokler, C.; Kiani, B.; Liu, ZW; Marvian, M.; Tennie, F.; Palmer, T. (2020). "Algoritmo cuántico para ecuaciones diferenciales no lineales". arXiv : 2011.06571 [quant-ph].
19. Montanaro, Ashley; Pallister, Sam (2016). "Algoritmos cuánticos y el método de elementos finitos". Physical Review A . 93 (3): 032324. arXiv : 1512.05903 . Código Bibliográfico :2016PhRvA..93c2324M. doi :10.1103/PhysRevA.93.032324. S2CID  44004935.
20. Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2012). "Ajuste de datos cuánticos". Physical Review Letters . 109 (5): 050505. arXiv : 1204.5242 . Código Bibliográfico :2012PhRvL.109e0505W. doi :10.1103/PhysRevLett.109.050505. PMID  23006156. S2CID  118439810.
21. Lloyd, Seth; Mohseni, Masoud; Rebentrost, Patrick (2013). "Algoritmos cuánticos para aprendizaje automático supervisado y no supervisado". arXiv : 1307.0411 [quant-ph].
22. Rebentrost, Patrick; Mohseni, Masoud; Lloyd, Seth (2013). "Máquina de vectores de soporte cuántico para clasificación de grandes características y grandes datos". arXiv : 1307.0471v2 [quant-ph].
23. "apozas/bayesian-dl-quantum". GitLab . Consultado el 30 de octubre de 2018 .
24. Jacquier, Antoine (31 de octubre de 2022). Aprendizaje automático cuántico y optimización en finanzas: en el camino hacia la ventaja cuántica. Packt . p. 349. ISBN 9781801817875.
25. Baskaran, N (2023). "Adaptación del algoritmo Harrow-Hassidim-Lloyd a la teoría cuántica de muchos cuerpos". Physical Review Research . 5 (4): 043113. Bibcode :2023PhRvR...5d3113B. doi : 10.1103/PhysRevResearch.5.043113 .
26. Aaronson, Scott (2015). "Lea la letra pequeña". Nature Physics . 11 (4): 291–293. Bibcode :2015NatPh..11..291A. doi :10.1038/nphys3272. S2CID  122167250 . Consultado el 9 de mayo de 2023 .
27. Schuld, Maria (2018). Aprendizaje supervisado con computadoras cuánticas. Springer Publishing . p. 218. ISBN 9783319964249.
28. Schuld, Maria (2018). Aprendizaje supervisado con computadoras cuánticas. Springer Publishing . p. 219. ISBN 9783319964249.