Algorytmy kwantowe dla konwolucji

9

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.

DPL
źródło
Artykuł kończy się stwierdzeniem „Ostatnia uwaga: ten wynik został zainspirowany komentarzem Davida Meyera, który uzyskał podobne wyniki niezależnie”. Czy sprawdziłeś papier autorstwa Meyera?
Norbert Schuch,
@NorbertSchuch Zrobiłem to i nie byłem w stanie znaleźć takiego, który mógłby złożyć podobny wniosek.
DPL

Odpowiedzi:

3

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:fg

F1(F(f).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=F(f)=1Ni=0N1|i=i=1N1F(i)

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

F(f).F(g)=F.G=(F(0)F(1).F(N1))(G(0)G(1).G(N1))

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=F(f)=12(|0+|2+|5+|7)
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

Ali Javadi
źródło
3

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.

ijαiβj|ijiαiβi|i
P=i|iii|.
|ii|i0,
DaftWullie
źródło
3
Czy nie jest wymagane, aby operacja była jednolita?
Craig Gidney
2
@CraigGidney Theorem 16 mówi konkretnie o połączeniu jednostek i miary i twierdzi, że nie ma indywidualnych wyników pomiarów, które mogłyby osiągnąć tę mapę.
DaftWullie
To wygląda na dobry kontrprzykład. Czy masz sens w jakimkolwiek błędzie w logice autora w dowodzeniu Lemat 14 (który wykorzystuje jako podstawę do udowodnienia Twierdzenia 16?)
DPL
@DPL Nie sądzę, aby Lemma 14 się myliła (przynajmniej wierzę w wynik. Nie wiem o dowodzie) Jest jednak dziwny argument w twierdzeniu 16 (może być w porządku, nie wydałem żadnego czas się nad tym zastanawiać, po prostu wygląda to podejrzanie) coś o tym, ponieważ coś było prawdą w jednostkach, to prawda w przypadku operatorów liniowych, a zatem także w przypadku pomiarów.
DaftWullie
@DPL bardziej precyzyjnie, wierzę, że Lemma 14 ma zastosowanie do unitarów.
DaftWullie,