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,