Jakie liczby całkowite zostały uwzględnione w algorytmie Shora?


19

Algorytm Shora powinien umożliwić nam uwzględnienie liczb całkowitych znacznie większych niż można to zrobić na nowoczesnych komputerach klasycznych.

Obecnie uwzględniono tylko mniejsze liczby całkowite. Na przykład w tym artykule omówiono faktoryzację .15=5×3

Co w tym sensie jest najnowocześniejszym badaniem? Czy jest jakiś najnowszy artykuł, w którym mówi się, że niektóre większe liczby zostały podzielone na czynniki?


Odpowiedzi:


13

Faktoryzacja pierwotna 21 (7x3) wydaje się być największą jak dotąd wykonaną algorytmem Shora; zrobiono to w 2012 r., jak szczegółowo opisano w tym dokumencie . Należy jednak zauważyć, że znacznie większe liczby, takie jak 56 153 w 2014 r., Zostały uwzględnione przy użyciu algorytmu minimalizacji, jak wyszczególniono tutaj . Aby uzyskać wygodne odniesienie, zobacz Tabela 5 tego dokumentu :

Table 5: Quantum factorization recordsNumber# of factors# of qubitsneededAlgorithmYearimplementedImplementedwithout priorknowledge ofsolution1528Shor2001 [2]χ28Shor2007 [3]χ28Shor2007 [3]χ28Shor2009 [5]χ28Shor2012 [6]χ21210Shor2012 [7]χ14324minimization2012 [1]5615324minimization2012 [1]29131126minimizationnot yet17533minimizationnot yet.

@SqueamishOssifrage: Gdzie jest powiedziane, że algorytm minimalizacji jest „ograniczony do liczb, których czynniki mają znane relacje, dzięki czemu przestrzeń wyszukiwania jest znacznie mniejsza, np. Różni się tylko kilkoma pozycjami bitowymi lub różni się wszystkimi pozycjami oprócz kilku”?
użytkownik1271772,

@ user1271772 Jak rozumiem, technika polega na zmniejszeniu problemu, wymagając jedynie możliwej do wyliczenia liczby kubitów poprzez wyeliminowanie zmiennych przez znane relacje między bitami czynników. Chociaż liczba kubitów do czynnika może być skalowana tylko z O ( log 2 N ) , żaden z czytanych artykułów nie wydawał się podejmować żadnej próby oszacowania wzrostu czasu do rozwiązania w zależności od liczby kubitów lub log N . N.O(log2)N.)logN.
Squeamish Ossifrage

log(N)log2Nlog(N)log2N.
użytkownik1271772,

@SqueamishOssifrage: „żaden z artykułów, które czytałem, nie wydawał się podejmować żadnej próby oszacowania upływu czasu do rozwiązania w zależności od liczby kubitów”. Ten podjął próbę: journals.aps.org/prl/abstract/10.1103/PhysRevLett.101.220405 Ale „czas na rozwiązanie” nie jest ważny, ale wymaga wysiłku. Przesiewanie GNF jest łatwe, ale krok matrycy jest strasznie niewygodny. Wykonywanie algorytmu Shora w racjonalnie optymalny sposób jest uciążliwe. Algorytm minimalizacji jest prosty.
user1271772

@SqueamishOssifrage: Wreszcie: „Zauważ, że algorytm minimalizacji jest ograniczony do liczb, których czynniki mają znane relacje”. Żadna część algorytmu nie jest ograniczona do „znanych” relacji. Algorytm nie zakłada niczego o czynnikach. Brak relacji. Wszystkie bity to nieznane zmienne, które są określane przez minimalizację. Minimalizację można wykonać przy użyciu mniejszej liczby kubitów dla niektórych liczb niż dla innych. To samo dotyczy algorytmu Shora. To samo dotyczy GNFS. W rzeczywistości, jeśli liczba, którą chcesz wziąć pod uwagę, jest parzysta, raczej łatwo ją wyliczyć.
user1271772

5

Algorytm Shora : stan techniki to wciąż 15 . Aby „uwzględnić” 21 w dokumencie, o którym wspomina Heather, musieli skorzystać z tego faktu21=7×3) wybrać swoją bazę za. Zostało to wyjaśnione w 2013 r. W artykule Udając, że obliczamy liczby na komputerze kwantowym , opublikowanym później przez Nature o nieco bardziej przyjaznym tytule . Komputer kwantowy nie uwzględnił współczynnika 21, ale potwierdził, że współczynniki 7 i 3 są rzeczywiście poprawne.

W przypadku algorytmu wyżarzania : stan techniki wynosi 376289 . Ale nie wiemy, jak to się skaluje. Bardzo przybliżona górna granica liczby kubitów potrzebnych do współczynnika RSA-230 wynosi 5,5 miliarda kubitów (ale można to znacznie obniżyć dzięki lepszym kompilatorom), podczas gdy algorytm Shora może to zrobić z 381 kubitami .


Zauważysz w tabeli w mojej odpowiedzi, że jest kolumna „zaimplementowana bez wcześniejszej wiedzy o rozwiązaniu”, jest „x” dla wszystkich implementacji algorytmu shora, co prowadzi mnie do przekonania, że ​​coś podobnego jest prawdą w faktoringu 15.
wrzos

4

Wielkość uwzględnionej liczby nie jest dobrym miernikiem złożoności problemu faktoryzacji i, odpowiednio, mocy algorytmu kwantowego. Odpowiednią miarą powinna być raczej okresowość wynikowej funkcji pojawiającej się w algorytmie.

Jest to omówione w J. Smolin, G. Smith, A. Vargo: Udawanie , że rozkłada duże liczby na komputerze kwantowym , Nature 499, 163-165 (2013) . W szczególności autorzy podają również przykład liczby z 20000 cyfr binarnych, którą można rozliczyć za pomocą komputera kwantowego o dwóch kubitach, z dokładnie tą samą implementacją, która była wcześniej używana do obliczania innych liczb.

Należy zauważyć, że „ręczne uproszczenia”, których dokonują autorzy, aby dojść do tego algorytmu kwantowego, zostały również wykonane np. W przypadku faktoringu z oryginalnego eksperymentu 15.

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.