¿Multiplicación de matriz cuántica?

No parece que se sepa esto, pero ¿hay algún límite inferior interesante sobre la complejidad de la multiplicación de matrices en el modelo de computación cuántica? ¿Tenemos alguna intuición de que podemos vencer la complejidad del algoritmo Coppersmith-Winograd usando computadoras cuánticas?

reference-request quantum-computing matrix-product Henry Yuen
fuente

Respuestas:

En arXiv: quant-ph / 0409035v2, Buhrman y Spalek presentan un algoritmo cuántico que supera al algoritmo Coppersmith-Winograd en los casos en que la matriz de salida tiene pocas entradas distintas de cero.

Actualización: también hay un algoritmo cuántico ligeramente mejorado por Dörn y Thierauf .

Actualización: Hay un algoritmo cuántico mejorado por Le Gall superando a Burhman y Spalek en general.

Martin Schwarz
fuente

Esto era nuevo para mí (sé poco sobre los resultados cuánticos), pero al mirar el papel, ¡el resultado fue aún más sorprendente! Si, para multiplicaciones matriciales, hay entradas distintas de cero en la salida, el producto puede calcularse en tiempo subcuadrático , .

A_{n x m} B_{m x n} = C_{n x n}

$A_{nxm}B_{mxn}=C_{nxn}$

o (\sqrt{n})

$o(\sqrt{n})$

o (n m)

$o(nm)$

Daniel Apon el

Hay una ligera mejora en esto para el caso especial del producto de matriz booleana, min { } cuando Hay distintos de cero en la salida. (Apareció en nuestro artículo de FOCS'10 `` Equivalencias subcúbicas entre problemas de trayectoria, matriz y triángulo ''.)

n^{1.3} w^{17 / 30}, n^{2} + w^{47 / 60} n^{13 / 15}

$n^{1.3}w^{17/30}, n^2 + w^{47/60} n^{13/15}$

w

$w$

virgi

Una mejora reciente de en el caso del producto de matriz booleana es arxiv.org/abs/1112.5855 , con límites inferiores también coincidentes.

n w^{1 / 2}

$nw^{1/2}$

Abel Molina

Si está interesado en multiplicar dos matrices y recuperar el resultado clásico completo, entonces la respuesta de Martin es probablemente una respuesta definitiva a su pregunta. Sin embargo, si desea calcular algo como , puede hacerlo de manera extremadamente eficiente. Harrow, Hassidim y Lloyd tienen un algoritmo ( arXiv: 0811.3171 ) para calcular que solo es logarítmico en las dimensiones de la matriz para matrices dispersas. Parece relativamente sencillo adaptar este enfoque para calcular productos en lugar de inversos. $v^\dagger X Y v$ $v X^{-1} v$ $X$

Joe Fitzsimons
fuente

En este caso, el tiempo de ejecución seguirá dependiendo del número de condición de las matrices, y las matrices deberán tener entradas complejas. Además, si X e Y son escasos, entonces también lo es su producto, y puede estimarse clásicamente con el mismo tipo de aceleración exponencial utilizando muestreo aleatorio.

v^{'} X Y v

$v'XYv$

Aram Harrow el

@Aram: ¡Buen punto! Sé que su algoritmo funciona para matrices dispersas, pero tenía la impresión de que también podría funcionar para ciertas matrices no dispersas. ¿Es esto correcto?

Joe Fitzsimons

Sí, funciona para matrices no dispersas cuando conocemos buenas formas de simular esos hamiltonianos. Entonces, tal vez algo no trivial sea posible aquí.

Aram Harrow

@Aram: con la codificación que usa, ¿no obtenemos también la transformación de Fourier de todas las matrices dispersas a través de QFT?

Joe Fitzsimons

@ Joe: Acabo de notar esto. Sí, esas matrices (que puedes considerar como escasas en el momento) también son utilizables. Esto no es nada exclusivo de nuestro algoritmo. Más bien es una declaración sobre la clase de hamiltonianos que sabemos simular en una computadora cuántica.

Aram Harrow