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

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{\times}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?

shors-algorithm Leżący tancerz
źródło

Ściśle związany, ale nie dokładny duplikat: Która z najwyższych liczb jest uwzględniona przez QC w niespecyficznym eksperymencie?

agaitaarino,

Odpowiedzi:

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 :

{\begin{matrix} Table 5: Quantum factorization records \\ \begin{array}{cccccc} Number & # of factors & \begin{matrix} # of qubits \\ needed \end{matrix} & Algorithm & \begin{matrix} Year \\ implemented \end{matrix} & \begin{matrix} Implemented \\ without prior \\ knowledge of \\ solution \end{matrix} \\ 15 & 2 & 8 & Shor & 2001 [2] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2009 [5] & χ \\ 2 & 8 & Shor & 2012 [6] & χ \\ 21 & 2 & 10 & Shor & 2012 [7] & χ \\ 143 & 2 & 4 & minimization & 2012 [1] & ✓ \\ 56153 & 2 & 4 & minimization & 2012 [1] & ✓ \\ 291311 & 2 & 6 & minimization & not yet & ✓ \\ 175 & 3 & 3 & minimization & not yet & ✓ \end{array} \end{matrix}}_{.}

$\begin{array}{c} \textbf{Table 5:}~\text{Quantum factorization records} \\ \hline \small{ \begin{array}{cccccc} \text{Number} & \text{# of factors} & \begin{array}{c}\text{# of qubits} \\ \text{needed} \end{array} & \text{Algorithm} & \begin{array}{c}\text{Year} \\ \text{implemented} \end{array} & \begin{array}{c}\text{Implemented} \\ \text{without prior} \\ \text{knowledge of} \\ \text{solution} \end{array} \\ \hline 15 & 2 & 8 & \text{Shor} & 2001~\left[2\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2009~\left[5\right] & \chi \\ & 2 & 8 & \text{Shor} & 2012~\left[6\right] & \chi \\ 21 & 2 & 10 & \text{Shor} & 2012~\left[7\right] & \chi \\ 143 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ 56153 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ \hline 291311 & 2 & 6 & \text{minimization} & \text{not yet} & \checkmark \\ 175 & 3 & 3 & \text{minimization} & \text{not yet} & \checkmark \end{array}} \end{array}_{\Large{.}}$

wrzos
źródło

@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

, ż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

N

$N$

O (\log^{2} N)

$O(\log^2 N)$

\log N

$\log N$

Squeamish Ossifrage

\log (N)

$\log(N)$

\log^{2} N

$\log^2 N$

\log (N)

$\log(N)$

\log^{2} N

$\log^2 N$

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

Algorytm Shora : stan techniki to wciąż 15 . Aby „uwzględnić” 21 w dokumencie, o którym wspomina Heather, musieli skorzystać z tego faktu $21=7\times 3$ wybrać swoją bazę $a$ . 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 .

użytkownik1271772
źródło

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

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.

Norbert Schuch
źródło