Algorytmy kwantowe dla konwolucji

Przyglądałem się aplikacjom obliczeń kwantowych do uczenia maszynowego i natknąłem się na następujący przedruk z 2003 roku. Algorytmy kwantowej konwolucji i korelacji są fizycznie niemożliwe . Artykuł nie wydaje się być opublikowany w żadnym czasopiśmie, ale cytowano go kilkadziesiąt razy.

Autor artykułu twierdzi, że niemożliwe jest obliczenie dyskretnego splotu ponad stanami kwantowymi. Intuicyjnie wydaje mi się to niepoprawne, ponieważ wiem, że możemy wykonać mnożenie macierzy kwantowej i wiem, że dyskretne zwoje można po prostu sformułować jako zwielokrotnienie za pomocą macierzy Toeplitz (lub krążącej).

Sednem jego argumentów wydaje się być to, że nie ma możliwego do zrealizowania składu operatorów unitarnych dla iloczynu elementarnego (Hadamarda) dwóch wektorów.

Gdzie jest moje rozłączenie? Czy jest jakiś powód, dla którego generalnie nie możemy skonstruować macierzy Toeplitza dla dyskretnego splotu w komputerze kwantowym?

A może artykuł jest po prostu niepoprawny? Przepracowałem sprzeczność, którą autor przedstawia w swoim dowodzie na temat Lemat 14, i wydaje mi się, że ma to sens.

Możesz faktycznie przeprowadzić splot na komputerze kwantowym (i wykładniczo szybszym w tym przypadku), jeśli twoje sygnały wejściowe mają określoną strukturę. Ale w przypadku ogólnych danych wejściowych wydaje się to trudne, a może nawet fizycznie niemożliwe, co wydaje się argumentować w dokumencie.

Zastanów się, jak można obliczyć splot dwóch oddzielnych sygnałów i klasycznie. Możesz wziąć transformatę Fouriera obu sygnałów, wykonać punktowe mnożenie uzyskanych wektorów, a następnie wykonać odwrotną transformatę Fouriera:$f$$g$

$$\mathscr{F}^{-1} (\mathscr{F}(f) . \mathscr{F}(g))$$

Zauważ, że transformata Fouriera to bardzo tania operacja na komputerze kwantowym. To wydaje się świetne. Problem polega na tym, że punktowe zwielokrotnienie dwóch wektorów nie jest takie łatwe. Zobaczmy, jakie czynniki to determinują.

Załóżmy, że mamy szczęście, a spektrum Fouriera okazuje się płaskie: $f$

$$F = \mathscr{F}(f) = \frac{1}{N}\sum_{i=0}^{N-1}{|i\rangle} = \sum_{i=1}^{N-1}F(i)$$

W takim przypadku komputer kwantowy może wykonać operację macierzy diagonalnej, która daje punktowe mnożenie:

$$\mathscr{F}(f) . \mathscr{F}(g) = F.G = \left(\begin{array}{cccc} F(0) & & & \\ & F(1) & & \\ & & . & \\ & & & F(N-1) \end{array}\right) \left(\begin{array}{c} G(0) \\ G(1) \\ . \\ G(N-1) \end{array}\right)$$

Jednak algorytmy kwantowe, które znajdują punktowe zwielokrotnienie dwóch wektorów, mogą być fizycznie niemożliwe w ogólnym przypadku. Wynika to z faktu, że operacja ta ogólnie nie jest jednolita. Jako prosty przykład załóżmy, że transformata Fouriera jest funkcją kolczastą, z zerami w większości miejsc:$f$

$$F = \mathscr{F}(f) = \frac{1}{2}(|0\rangle + |2\rangle + |5\rangle + |7\rangle)$$ Celowe zwielokrotnienie tego stanu z innym stan jest nieodwracalny (z powodu zer), a zatem nie jest jednostkowy.

Wcześniej prowadzone były prace nad odkryciem funkcji, które dają płaskie lub prawie płaskie widmo Fouriera, a zatem są łatwe do zwoju:

https://arxiv.org/abs/0811.3208

https://arxiv.org/abs/quant-ph/0211140

Jestem bardzo podejrzliwy w stosunku do wyniku. Jeśli spojrzysz na Twierdzenie 16, twierdzi ono, że nie ma operacji, która osiąga mapę aż do normalizacji. Weźmy jednak pod uwagę operator pomiaru To wyraźnie implementuje pożądaną mapę (dla tego konkretnego wyniku pomiaru). Co więcej, jego wdrożenie jest dość proste. Istnieje jednolity (faktycznie uogólniony kontrolowany-nie), który może zmapować dzięki czemu można zmierzyć drugi obrót i wybrać po uzyskaniu wyniku 0. Wydaje się, że unieważnia to dowód pracy.

$$\sum_{ij}\alpha_i\beta_j|ij\rangle\mapsto \sum_i\alpha_i\beta_i|i\rangle$$ $$P=\sum_{i}|i\rangle\langle ii|.$$ $$|ii\rangle\mapsto|i0\rangle,$$