Czy można przyspieszyć generowanie macierzy ważenia za pomocą algorytmu kwantowego?


9

W tym [1] artykule na stronie 2 wspominają, że generują macierz wag w następujący sposób:

W=1Md[m=1m=Mx(m)(x(m))T]Idd

gdzie x(m)d-wymiarowe próbki treningowe (tj x:={x1,x2,...,xd}T gdzie xi{1,1}  i{1,2,...,d}) i tu są Mpróbki treningowe ogółem. To generowanie macierzy ważenia przy użyciu mnożenia macierzy, po której następuje sumaM warunki wydają się być kosztowną operacją pod względem złożoności czasowej, to znaczy chyba O(Md) (?).

Czy istnieje jakiś algorytm kwantowy, który może zapewnić znaczne przyspieszenie generowania macierzy ważenia? Myślę, że w artykule ich główne przyspieszenie pochodzi z algorytmu inwersji macierzy kwantowej (o którym wspomniano w dalszej części artykułu), ale wydaje się, że nie uwzględnili tego aspektu generowania macierzy ważenia.

[1]: A Quantum Hopfield Neural Network Lloyd i in. (2018)

Odpowiedzi:


5

Biorąc macierz gęstości

ρ=W+Idd=1Mm=1M|x(m)x(m)|,
wiele szczegółów znajduje się w następującym akapicie na stronie 2:

Kluczowe dla kwantowych adaptacji sieci neuronowych jest klasyczne do kwantowego wczytywania wzorców aktywacyjnych. W naszym ustawieniu czytanie według wzorca aktywacjix sprowadza się do przygotowania stanu kwantowego |x. Można to zasadniczo osiągnąć za pomocą rozwijających się technik kwantowej pamięci o swobodnym dostępie (qRAM) [33] lub wydajnego przygotowania stanu kwantowego, dla których istnieją ograniczone wyniki oparte na wyroczni [34]. W obu przypadkach narzut obliczeniowy jest logarytmiczny pod względemd. Alternatywnie można dostosować w pełni kwantową perspektywę i wziąć wzorce aktywacji|xbezpośrednio z urządzenia kwantowego lub jako wyjście kanału kwantowego. W przypadku tych pierwszych czas działania naszego przygotowania jest efektywny, ilekroć urządzenie kwantowe składa się z wielu bramek skalowanych najwyżej wielomianowo z liczbą kubitów. Zamiast tego w przypadku tych ostatnich zwykle widzimy kanał jako pewną formę stałej interakcji system-środowisko, która nie wymaga wdrożenia narzutu obliczeniowego.

Odniesienia w powyższym są:

[33]: V. Giovannetti Lloyd S. L. Maccone Quantum pamięć o dostępie swobodnym, Physical Review Letters 100, 160501 (2008) [ związek PRL , arXiv łącza ]

[34]: AN Soklakov, R. Schack, Skuteczne przygotowanie stanu dla rejestru bitów kwantowych, Physical Review A 73, 012307 (2006). [ PRA związek , arXiv łącza ]


Bez wchodzenia w szczegóły, w jaki sposób oba powyższe są rzeczywiście schematami odpowiednio do wdrażania wydajnej qRAM; i skuteczne przygotowanie stanu, które odtwarza stan|x w samą porę O(log2d).

Jednak do tej pory nas to dotyka: można tego użyć do stworzenia państwa ρ(m)=|x(m)x(m)|, podczas gdy chcemy sumę ponad wszystko, co możliwe m„s.

Co najważniejsze, ρ=mρ(m)/M jest mieszany, więc nie może być reprezentowany przez pojedynczy stan czysty, więc drugie z dwóch powyższych odniesień dotyczących odtwarzania stanów czystych nie ma zastosowania, a pierwszy wymaga, aby stan był już w qRAM.

W związku z tym autorzy przyjmują jedno z trzech możliwych założeń:

  1. Mają urządzenie, które akurat daje im właściwy stan wejściowy

  2. Albo mają stany ρ(m) w qRAM,

  3. Są w stanie tworzyć te stany do woli, korzystając z drugiego z powyższych odniesień. Stan mieszany jest następnie tworzony za pomocą kanału kwantowego (tj. Całkowicie dodatnia mapa zachowująca ślad (CPTP)).

Zapominając o dwóch pierwszych z powyższych opcji na razie (pierwsza i tak magicznie rozwiązuje problem), kanał może być:

  • system inżynieryjny, w którym zostałby stworzony dla konkretnego wystąpienia w czymś podobnym do symulacji analogowej. Innymi słowy, masz fizyczny kanał, który zajmuje fizycznie dużo czasut(w przeciwieństwie do złożoności czasowej). Jest to „stała interakcja system-środowisko, która nie wymaga nakładów obliczeniowych do wdrożenia”.

  • Sam kanał jest symulowany. Jest na ten temat kilka artykułów, takich jak przybliżona symulacja kanałów kwantowych Bény'ego i Oreshkowa ( link arXiv - wygląda to na dokładny artykuł, ale nie mogłem znaleźć stwierdzeń o złożoności czasowej), Lu i in. al. eksperymentalna symulacja kanału kwantowego (wydaje się, że nie istnieje wersja arXiv) oraz preprint Wei, Xin i Long arXiv Wydajna symulacja uniwersalnego kanału kwantowego w chmurowym komputerze kwantowym IBM , który (dla kilku kubitówn=log2d) daje złożoność czasową wynoszącą O((8n3+n+1)42n). Można również zastosować dylatację Stinespring o złożonościO(27n343n).


Patrząc teraz na opcję 2 1 , jedną z możliwych bardziej wydajnych metod byłoby przeniesienie stanów z rejestru adresów do rejestru danych w zwykły sposób: dla adresów w rejestrzeza, jotψjot|jotza, przeniesienie tego do rejestru danych daje stan w rejestrze danych re tak jak jotψjot|jotza|rejotre. Powinno być możliwe po prostu rozszyfrowanie adresu i rejestru danych, aby przekształcić to w stan mieszany, co daje niewielki narzut czasowy, chociaż nie ma dodatkowego narzutu złożoności obliczeniowej, co daje znacznie lepszą złożoność wytwarzaniaρ, biorąc pod uwagę qRAM ze stanami |x(m), z O(n). Jest to również złożoność tworzenia stanów|x(m) po pierwsze, dając potencjalną (znacznie ulepszoną) złożoność produkcji ρ z O(n).

1 Dzięki @glS za wskazanie tej możliwości na czacie


Tę matrycę gęstości podaje się następnie do „qHop” (kwantowy Hopfield), gdzie stosuje się ją do symulacji mi-jaZAt dla

ZA=(W.-γjareP.P.0)
zgodnie z podrozdziałem „ Wydajna symulacja Hamiltona A ” na stronie 8.

tak samo mała uwaga na temat edycji: tak naprawdę nie trzeba „odszyfrowywać” rejestru adresów ani nic robić. Sam fakt nieużywania go powoduje, że zawartość rejestru danych jest nierozróżnialna od wielu różnych|rejot
glS
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.