Mnożenie macierzy kwantowej?

Nie wydaje się, żeby to było znane - ale czy są jakieś interesujące dolne granice złożoności mnożenia macierzy w modelu obliczeń kwantowych? Czy mamy intuicję, że możemy pokonać złożoność algorytmu Coppersmith-Winograd za pomocą komputerów kwantowych?

reference-request quantum-computing matrix-product Henry Yuen
źródło

Odpowiedzi:

W arXiv: quant-ph / 0409035v2 Buhrman i Spalek przedstawiają algorytm kwantowy pokonujący algorytm Coppersmitha-Winograda w przypadkach, gdy macierz wyjściowa ma niewiele niezerowych wpisów.

Aktualizacja: Istnieje również nieco ulepszony algorytm kwantowy autorstwa Dörna i Thieraufa .

Aktualizacja: Ulepszony algorytm kwantowy Le Gall pokonał Burhmana i Spalka w ogóle.

Martin Schwarz
źródło

To było dla mnie nowe (niewiele wiem o wynikach kwantowych), ale patrząc na papier, wynik był jeszcze bardziej zaskakujący! Jeśli dla

mnożenia macierzy, istnieje

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

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

niezerowe wpisy na wyjściu, iloczyn można obliczyć wczasiesubkwadratowym,

o (\sqrt{n})

$o(\sqrt{n})$

o (n m)

$o(nm)$

Daniel Apon,

Istnieje niewielka poprawa tego szczególnego przypadku Boole'a iloczyn macierzy min {

}, gdy istnieje

nonzeroes w produkcji. (Pojawił się w naszym artykule FOCS'10 `` Subcubic Equivalences Between Path, Matrix, and Triangle Problems ''.)

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

n w^{1 / 2}

$nw^{1/2}$

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

Joe Fitzsimons
źródło

v^{'} X Y v

$v'XYv$

@Aram: Dobra uwaga! Wiem, że twój algorytm działa dla rzadkich macierzy, ale miałem wrażenie, że można go również uruchomić w przypadku niektórych nierzadkich macierzy. Czy to jest poprawne?

Joe Fitzsimons,

Tak, działa na nieskomplikowanych matrycach, ilekroć znamy dobre sposoby symulowania tych hamiltonianów. Może więc możliwe jest tutaj coś nietypowego.

Aram Harrow,

@Aram: Czy przy używanym kodowaniu nie otrzymujemy również transformacji Fouriera wszystkich rzadkich macierzy za pośrednictwem QFT?

Joe Fitzsimons

@Joe: Właśnie to zauważyłem. Tak, te matryce (które można uznać za rzadkie w oparciu o pęd) są również użyteczne. To nie jest nic wyjątkowego w naszym algorytmie. Jest to raczej stwierdzenie o klasie Hamiltonianów, których wiemy, jak symulować na komputerze kwantowym.

Aram Harrow,