Czy implementacja algorytmu Shora w 2016 r. Jest naprawdę skalowalna?

W artykule naukowym z 2016 r. „ Realizacja skalowalnego algorytmu Shora ” [ 1 ] autorzy uwzględniają 15 z jedynie 5 kubitami, czyli mniej niż 8 kubitów „wymaganych” zgodnie z tabelą 1 z [ 2 ] i tabelą 5 z [ 3] ]. Wymóg 8 kubitów pochodzi z końca [ 4 ], który stwierdza, że liczba kubitów potrzebnych do faktorowania liczby bitowej wynosi co dla 15 wynosi . $n$ $1.5n+2$ $1.5\cdot 4 + 2=8$

Artykuł, który wykorzystuje tylko 5 kubitów, stwierdza, że ich algorytm „zastępuje QFT działający na kubitach M półklasycznym QFT działającym wielokrotnie na jednym kubicie”, ale konsekwencje tego dla złożoności algorytmu nie zostały nigdy wspomniane w pracy.

Teraz ostro skrytykowano artykuł twierdzący, że czynnik 15 jest „skalowalny”, jak powiedziano w części 2, że argument złożoności algorytmu Shora już nie obowiązuje. Jednak krytyka ta nie została nigdzie potwierdzona, a artykuł naukowy zyskuje popularność jako „skalowalna” wersja algorytmu Shora. Jaka jest złożoność „skalowalnego” algorytmu Shor?

[ 1 ] Monz i in. (2016) Science . Vol. 351, wydanie 6277, s. 1068–1070
[ 2 ] Smolin i in. (2013) Nature . 499, 163–165
[ 3 ] Dattani & Bryans (2014) arXiv: 1411.6758
[ 4 ] Zalka (2008) arXiv: quant-ph / 0601097
[ 5 ] Cao & Luo „Komentarz do: Realizacja skalowalnego algorytmu Shor”

cc.complexity-theory ds.algorithms quantum-computing factoring security użytkownik1271772
źródło

Zależy od tego, co rozumiesz przez „skalowalny”. Niektóre krytyki Cao i Liu wydają się dość wybredne. Na przykład jednym z ich zarzutów jest to, że Kitaev nie twierdził, że można użyć tylko jednego kubita w cytowanej pracy. Wydaje się, że nie badają, czy to twierdzenie jest rzeczywiście prawdziwe czy fałszywe. Algorytm Kitaeva może tak naprawdę zostać zmodyfikowany, aby używał tylko jednego kubita, jak twierdzi artykuł naukowy, nawet jeśli twierdzenie to nie jest zawarte w dokumencie Kitaeva na temat jego algorytmu.

Peter Shor,

@PeterShor, co za zaszczyt usłyszeć od ciebie! Ok, więc autorzy (poprawnie) rozszerzyli wyniki pracy Kitaeva, aby było to możliwe za pomocą jednego kubita, a Cao i Liu narzekają, że nazywają to „algorytmem Kitaeva”, a nie „zmodyfikowanym algorytmem Kitaeva lub coś w tym rodzaju”. Mówią jednak również, że argument złożoności nie ma już miejsca, gdy QFT jest zamieniany w „półklasyczny QFT”. Nadal jestem studentem, jeśli chodzi o tego rodzaju analizy, więc byłbym wdzięczny za wkład. Czy złożoność jest nadal O (log n) ^ 3? Czy nadal jest „skalowalny” pod względem wielomianu, a przynajmniej <GNFS?

user1271772,

Pozwolę komuś innemu odpowiedzieć na to pytanie, ponieważ ludzie mogą twierdzić, że jestem stronniczy. Chciałbym jednak zauważyć , że autorzy artykułu naukowego nie rozszerzyli algorytmu Kitaeva ... jest to dobrze znane rozszerzenie. Po prostu nie podali prawidłowego odniesienia.

Peter Shor,

Te formuły, które dochodzą do 8 kubitów, wymagają określonej implementacji algorytmu Shora i obliczają, ile kubitów zajmuje ta implementacja. Nie twierdzą, że jest to najlepsze możliwe wdrożenie.

Peter Shor,

@ user1271772 To oznaczono jako przeznaczone do moderacji, ponieważ jesteś jednym z autorów wymienionych w swoim poście. Nie jest to złe, niektóre autoreklamy są nieuniknioną częścią nauki, ale może najlepiej to wyjaśnić?

Bjørn Kjos-Hanssen

Głównym założeniem argumentu Cao i Luo jest to, że w wariancie algorytmu, który został zaimplementowany, pierwszy rejestr, który ostatecznie zawiera dane wyjściowe, zawiera tylko 1 bit. A jeśli otrzymujesz tylko 1 bit wyniku z algorytmu, to nie wystarczy do faktoryzacji. (Po pierwsze, chociaż nie jest to ich argument, 1 bit wyraźnie nie zawiera wystarczającej ilości informacji, aby określić czynniki.)

Cao i Luo wydają się nie zdawać sobie sprawy z tego, że dla odmiany transformacji Fouriera z tylko jednym bitem w pierwszym rejestrze, wyprowadzana jest taka sama wartość jak w standardowym algorytmie faktoryzacji; to tylko wyjście po trochu. Ta zmiana nie wpływa na czas działania . $c$ $O(\log^3 N)$

Aby spróbować być uczciwym wobec Cao i Luo, mówią, że nie sądzą, że ten algorytm działa, a jeśli działa, to nie jest algorytmem Shora, ponieważ nie jest on dokładnie zgodny z algorytmem opisanym w oryginalnej pracy faktoringowej . Cytat z ich pracy:

Na koniec chcielibyśmy podkreślić, że jeśli implementacja jest rzeczywiście wiarygodna, byłby to nowy algorytm faktorowania kwantowego, a nie algorytm Shora, ponieważ wszystkie wymagania pierwotnego algorytmu Shora nie są spełnione.

I rzeczywiście, nie jest to algorytm z mojego oryginalnego dokumentu faktoringowego. Korzysta z procedury szacowania fazy z algorytmu faktoringu Kitaeva i jej wariantu, odkrytego przez Griffithsa i Niu (nie przez Parkera i Plenio, jak powiedziałem w poprzedniej edycji tej odpowiedzi), która pozwala algorytmowi wygenerować oszacowanie fazy po trochu.

Peter Shor
źródło

Pokaż mi, gdzie w pracy Cao i Luo mówią, że wyjście po jednym kawałku wpływa na koszt operacji. Jeśli prawidłowo czytam ich gazetę, nie robią tego. Myślę, że odpowiednio obaliłem ich krytykę.

Peter Shor,

c

$c$

x \cdot t

$x\cdot t$

t

$t$

Nie zamierzam przejść przez obwód w celu oszacowania fazy wyjściowej w jednym kubicie i wyjaśnić, dlaczego stosunkowo niewielka zmiana konieczna do osiągnięcia tego nie wpływa na złożoność czasu. To „pół-klasyczne” modyfikacje opisane na stronie 2 Parker i Plenio'S papieru , Efficient faktoryzacji jednego czystego qubitu i log n mieszane qubitów .

Peter Shor,

\log N + 1

$\log N + 1$

1

$1$

\log N + 1

$\log N + 1$

Jak powiedziałem, musisz przeczytać i zrozumieć artykuł. Policz je sam, jeśli mi nie ufasz. Podstawowa struktura algorytmu nie uległa zmianie.

Peter Shor,

Czy implementacja algorytmu Shora w 2016 r. Jest naprawdę skalowalna?

Odpowiedzi: