¿Podría una computadora cuántica realizar álgebra lineal más rápido que una computadora clásica?

8

Suponiendo que tuviéramos una computadora cuántica con un número suficiente de qubits, ¿podríamos usarla para hacer álgebra lineal más rápido que con una computadora clásica? ¿Qué tipo de aceleración podríamos esperar? ¿Alguien ha creado un algoritmo cuántico para álgebra lineal, y cuál es su tiempo de ejecución? En teoría, una operación como la multiplicación matriz-matriz es altamente paralelizable, sin embargo, en la práctica requiere mucho trabajo implementar la multiplicación matriz-matriz paralela que se ejecuta rápidamente. ¿Una computadora cuántica proporcionaría alguna ventaja práctica?

J. Antonio Perez
fuente

Respuestas:

3

Aquí hay algunos consejos:

Yuval Filmus
fuente
Por cierto, estos indicadores estuvieron entre los primeros resultados en Google.
Yuval Filmus
Su respuesta se basa en enlaces, ¿es correcto?
De hecho así. Confieso que en realidad no he leído los periódicos.
Yuval Filmus
Está bien, al menos una respuesta.
1
También recomendaría el resumen de estos algoritmos de Scott Aaronson: Algoritmos de aprendizaje automático cuántico: lea la letra
pequeña
1

Modelo matemático con matriz

El algoritmo HHL se puede encontrar en los enlaces ya mencionados, impleméntelo en una computadora cuántica. Queremos resolver un sistema de ecuaciones lineales.A|x>=|b> De esto |x>=A1|b>

Con matriz A=[1.50.50.51.5] y entrada b=[10]

A1.|b>=[0.750.25]

Diseño de circuito cuántico

Usamos el circuito cuántico en arXiv 1302.1210 con 2 qubits, un qubit con entrada b. El segundo qubit es un bit ancilla y uno en la salida significa que la salida está lista. ingrese la descripción de la imagen aquí El circuito usa un circuito PEA (puerta R) como entrada y un circuito PEA inverso en la salida. La estimación de fase o PEA se utiliza para descomponer el estado cuántico de | b> en una base particular y los valores propios de A se almacenan en un registro de valores propios. La puerta de rotación R (y) se transforma con un ángulo dependiendo del valor en el registro de valores propios. Luego ejecutamos un PEA a la inversa para descontinuar el valor propio y encontrar la respuesta. En la computadora cuántica, solo se puede medir la posibilidad de encontrar 1 o 0.

Parámetros de la puerta

R es la matriz de vectores propios de la matriz A y Rdagger es su transposición. De la Matriz A encontramos los valores propiosλ1=1λ2=2El ángulo de rotación de la puerta de rotación Y está determinado por la relación de valores propios. Ángulo de rotaciónθ=2arccosλ1λ2

θ=2arccos(1/2)=2π3. Implemente este circuito en la computadora cuántica de IBM con el enlace al circuito:

quantumexperience.ng.bluemix.net/qx/editor?codeId=9da9d545772273118671911e1078ac42 ingrese la descripción de la imagen aquí

Bram
fuente
Esto se parece más a una publicación de blog. ¿Cómo responde la pregunta?
Yuval Filmus
La primera parte de la pregunta sobre el algoritmo ya fue respondida por los punteros con los enlaces al algoritmo HHL. La segunda parte de la pregunta es sobre el equilibrio entre la teoría y las implicaciones prácticas con las multiplicaciones de matrices. No respondí eso, pero al menos mostré una posible implementación y, por lo tanto, algo para analizar y llegar a una conclusión.
Bram