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

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

$$W = \frac{1}{Md}[\sum_{m=1}^{m=M} \mathbf{x}^{(m)}\left(\mathbf{x}^{(m)}\right)^{T}] - \frac{\Bbb I_d}{d}$$

gdzie $\mathbf{x}^{(m)}$są $d$-wymiarowe próbki treningowe (tj $\mathbf{x} := \{x_1,x_2,...,x_d\}^{T}$ gdzie $x_i \in \{1,-1\} \ \forall \ i\in \{1,2,...,d\}$) i tu są $M$próbki treningowe ogółem. To generowanie macierzy ważenia przy użyciu mnożenia macierzy, po której następuje suma$M$ 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)

Biorąc macierz gęstości

$$\rho=W+\frac{I_d}{d}=\frac 1M \sum_{m=1}^M\left|x^{\left(m\right)}\rangle\langle x^{\left(m\right)}\right|,$$ 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 aktywacji$x$ 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ędem$d$. Alternatywnie można dostosować w pełni kwantową perspektywę i wziąć wzorce aktywacji$|x〉$bezpoś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$\left|x\right>$ w samą porę $\mathcal O\left(\log_2 d\right)$.

Jednak do tej pory nas to dotyka: można tego użyć do stworzenia państwa $\rho^{\left(m\right)} = \left|x^{\left(m\right)}\rangle\langle x^{\left(m\right)}\right|$, podczas gdy chcemy sumę ponad wszystko, co możliwe $m$„s.

Co najważniejsze, $\rho = \sum_m\rho^{\left(m\right)}/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 $\rho^{\left(m\right)}$ 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 czasu$t$(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ów$n=\lceil\log_2 d\rceil$) daje złożoność czasową wynoszącą $\mathcal O\left(\left(8n^3+n+1\right)4^{2n}\right)$. Można również zastosować dylatację Stinespring o złożoności$\mathcal O\left(27n^34^{3n}\right)$.

---

Patrząc teraz na opcję 2 ¹ , 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 rejestrze$a$, $\sum_j\psi_j\left|j\right>_a$, przeniesienie tego do rejestru danych daje stan w rejestrze danych $d$ tak jak $\sum_j\psi_j\left|j\right>_a\left|D_j\right>_d$. 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$\rho$, biorąc pod uwagę qRAM ze stanami $\left|x^{\left(m\right)}\right>$, z $\mathcal O\left(n\right)$. Jest to również złożoność tworzenia stanów$\left|x^{\left(m\right)}\right>$ po pierwsze, dając potencjalną (znacznie ulepszoną) złożoność produkcji $\rho$ z $\mathcal O\left(n\right)$.

^{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 $e^{-iAt}$ dla

$$A=\begin{pmatrix}W-\gamma I_d && P\\ P&& 0\end{pmatrix}$$ zgodnie z podrozdziałem „ Wydajna symulacja Hamiltona A ” na stronie 8.