Multiplicação de matriz quântica?

Não parece que isso seja conhecido - mas existem limites inferiores interessantes sobre a complexidade da multiplicação de matrizes no modelo de computação quântica? Temos alguma intuição de que possamos superar a complexidade do algoritmo Coppersmith-Winograd usando computadores quânticos?

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

Respostas:

No arXiv: quant-ph / 0409035v2, a Buhrman e a Spalek apresentam um algoritmo quântico superando o algoritmo de Coppersmith-Winograd nos casos em que a matriz de saída possui poucas entradas diferentes de zero.

Atualização: Há também um algoritmo quântico ligeiramente aprimorado por Dörn e Thierauf .

Atualização: Existe um algoritmo quântico aprimorado por Le Gall derrotando Burhman e Spalek em geral.

Martin Schwarz
fonte

Isso era novo para mim (eu sei pouco sobre resultados quânticos), mas olhando para o jornal, o resultado foi ainda mais surpreendente! Se, para

multiplicações de matrizes, há

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

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

entradas diferentes de zero na saída, o produto pode ser calculado em temposub-quadrático,

o (\sqrt{n})

$o(\sqrt{n})$

o (n m)

$o(nm)$

Daniel Daniel Apon

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$

n w^{1 / 2}

$nw^{1/2}$

$v^\dagger X Y v$ $v X^{-1} v$ $X$

Joe Fitzsimons
fonte

v^{'} X Y v

$v'XYv$

@Aram: Bom ponto! Sei que seu algoritmo funciona para matrizes esparsas, mas fiquei com a impressão de que também poderia funcionar para certas matrizes não esparsas. Isso está correto?

precisa

Sim, funciona para matrizes não esparsas sempre que conhecemos boas maneiras de simular esses hamiltonianos. Então, talvez algo não trivial seja possível aqui.

Aram Harrow

@ Aram: Com a codificação usada, também não obtemos a transformação de Fourier de todas as matrizes esparsas via QFT?

Joe Fitzsimons

@ Joe: Acabei de perceber isso. Sim, essas matrizes (que você pode considerar esparsas na base do momento) também são utilizáveis. Isso não é nada exclusivo do nosso algoritmo. Pelo contrário, é uma declaração sobre a classe de hamiltonianos que sabemos como simular em um computador quântico.

Aram Harrow