Algoritmo cuántico hiperparalelo para la multiplicación de matrices

Dibujo20160503 standard matrix multiplication stoimen com

El algoritmo estándar de multiplicación de matrices tiene una complejidad de O(n³) en tiempo. Se ha conjeturado que el algoritmo (clásico) óptimo debe alcanzar O(n²) en tiempo. Se publica un algoritmo cuántico para la multiplicación de matrices de números binarios (matrices booleanas) que alcanzan O(n²) usando estados hiperentrelazados y O(n² log n) cuando solo están entrelazados.

Los autores han usado el término algoritmo hiperparalelo para la versión hiperentrelazada. Por supuesto, se trata de una propuesta teórica y el cableado cuántico de este algoritmo tiene un alto coste espacial, O(n²). Por ello, en la práctica este algoritmo no es útil para n grande, máxime cuando hay que luchar contra la decoherencia en un sistema con O(n²) estados, algo que raya lo imposible para n grande.

El artículo es Xin-Ding Zhang, Xiao-Ming Zhang, Zheng-Yuan Xue, “Quantum hyperparallel algorithm for matrix multiplication,” Scientific Reports 6: 24910 (29 Apr 2016), doi: 10.1038/srep24910.

Por cierto, el mejor algoritmo conocido de Le Gall (2014) que alcanza O(nω) con ω < 2,37286, la última ligera mejora del algoritmo de Coppersmith–Winograd (1990) que logra ω < 2,37548. Se ha conjeturado que el algoritmo clásico óptimo debe alcanzar ω = 2+ε. Lograr descubrirlo se considera el problema abierto más importante en álgebra lineal numérica.

Los artículos que cito son François Le Gall,” Powers of Tensors and Fast Matrix Multiplication,” arXiv:1401.7714 [cs.DS]; Don Coppersmith, Shmuel Winograd, “Matrix multiplication via arithmetic progressions,” Journal of Symbolic Computation 9: 251-280 (1990), doi: 10.1016/S0747-7171(08)80013-2; también recomiendo Sara Robinson, “Toward an Optimal Algorithm for Matrix Multiplication,” SIAM News 38 (Nov 2005) [PDF].

Y ya que estamos, el hiperentrelazamiento es el entrelazamiento simultáneo entre dos sistemas en varios grados de libertad diferentes. Por ejemplo, dos fotones se pueden entrelazar en polarización o en momento angular, pero también se pueden hiperentrelazar en ambos, tanto en polarización como en momento angular. La ventaja es que se pueden medir el entrelazamiento en un grado de libertad sin afectar a los otros grados de libertad. Gracias a ello se pueden implementar puertas lógicas cuánticas más robustas y desarrollar nuevos algoritmos en computación cuántica.

Sobre hiperentrelazamiento usando fotones recomiendo Olivier Pfister, “Quantum optics: Jumping to hyperentanglement,” Nature Photonics 9: 483–485 (2015), doi: 10.1038/nphoton.2015.131.


3 Comentarios

Participa Suscríbete

Anon1Anon1

Muy interesante. Es genial que no se dé nada por sentado y finiquitado y sigan investigando métodos para optimizar cosas tan elementales como estas.

VíctorVíctor

Me pregunto, Francis, si la computación cuántica no tendrá más aplicación futura en operaciones enteramente cuánticas. Es decir, en un álgebra cuántica, en lugar de operar sobre elementos no cuánticos (en el caso que nos comentas, sobre dígitos binarios -no qbits-).

Saludos

Francisco R. Villatoro

Víctor, la entrada y la salida de un algoritmo cuántico deben ser cuánticas; sin embargo, el estado cuántico de la entrada se prepara a partir de una entrada clásica (para que nos sea útil el algoritmo le debemos poder dar datos clásicos), y la salida cuántica del algoritmo debe ser sometida a una medida cuántica para que al final nos dé una salida clásica (para que podamos manipularla con ordenadores clásicos).

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>