Jaka jest minimalna liczba całkowita, aby warto było dokonać kwantowej faktoryzacji?

Załóżmy, że mamy komputery kwantowe i klasyczne takie, że eksperymentalnie każda elementarna logiczna operacja faktoryzacji matematycznej jest w równym stopniu kosztowna w przypadku klasycznej, jak i faktoryzacji kwantowej: która jest najniższą wartością całkowitą, dla której przebieg kwantowy jest szybszy niż klasyczna jeden?

Kwantowa część algorytmu Shora jest zasadniczo pojedynczym potęgowaniem modułowym wykonanym w superpozycji, po którym następuje transformata Fouriera, a następnie pomiar. Modułowe potęgowanie jest zdecydowanie najdroższą częścią.

Załóżmy, że [...] każda elementarna logiczna operacja faktoryzacji matematycznej jest w równym stopniu kosztowna w przypadku faktoryzacji klasycznej i kwantowej

Jeśli założymy, że potęgowanie modułowe zajmuje dokładnie tyle samo czasu na komputerze kwantowym, co na komputerze klasycznym, to przejście, w którym obliczenia kwantowe stały się lepsze, nastąpiłoby przy bardzo małej liczbie. Obliczanie modułowych potęgowań jest bardzo szybkie, klasycznie, ponieważ można użyć powtarzania kwadratu. Szalenie bym oszacował, że doszło do crossovera, zanim jeszcze dojdziesz do liczb 30-bitowych (liczby ponad miliard).

Ale komputery kwantowe nie będą robić matematyki tak szybko, jak klasyczne komputery . Na przykład na moim laptopie mogę wykonać 1000-bitowe potęgowanie modułowe w pythonie w ułamku sekundy. Ale na przewidywalnych komputerach kwantowych zajęłoby to godziny lub dni. Problemem jest ogromna ( masywna ) różnica w koszcie bramki AND.

$|T\rangle$

Załóżmy więc, że otrzymujemy milion stanów T na sekundę i chcemy przekonwertować to na szybkość 64-bitowych dodatków w celu porównania z klasyczną maszyną. 64-bitowy dodatek wymaga 64 bramek AND, z których każda wymaga 4 bramek T. 1 milion podzielony przez 4 podzielony przez 64 daje ... około 4KHz. Dla kontrastu klasyczna maszyna z łatwością wykona miliard dodatków na sekundę. Sumatory kwantowe są milion razy wolniejsze niż klasyczne sumatory (ponownie, szalenie szacując, i pamiętaj, że ta liczba powinna z czasem ulec poprawie).

Kolejnym czynnikiem wartym rozważenia są różne koszty komputerów kwantowych i klasycznych. Jeśli masz sto milionów dolarów i wybierasz między jednym komputerem kwantowym a tysiącem klasycznych komputerów, ten współczynnik 1000 musi zostać uwzględniony. W tym sensie można powiedzieć, że sumatory kwantowe są miliard razy mniej wydajne niż klasyczne sumatory (w FLOPS / $).

Stała kara umowna w wysokości miliarda jest zwykle natychmiastowym przełamaniem umowy. A w przypadku algorytmów kwantowych o jedynie kwadratowej przewadze (takich jak Grover) twierdzę, że w rzeczywistości jest to przełom. Ale algorytm Shora staje się wykładniczo lepszy w stosunku do klasycznej strategii, gdy zwiększasz liczbę bitów liczby do współczynnika. Ile bitów zanim zjemy tę „nędzną” 10 ^ 9 stałą z przewagą naszego wykładniczego wzrostu?

Weź pod uwagę, że RSA-640 został uwzględniony w 2005 r. Przy użyciu ~ 33 lat procesora. Komputer kwantowy powinien być w stanie wykonać tę liczbę w ciągu jednego dnia. Jeśli masz tysiąc klasycznych komputerów pracujących nad problemem, skończyłyby się za około dwa tygodnie. Wygląda więc na to, że kwant wygrywa o 640 bitów, ale tylko o rząd wielkości lub trzy. Więc może odcięcie nastąpiłoby gdzieś około 500 bitów?

W każdym razie wiem, że nie jest to trudna i szybka odpowiedź. Mam jednak nadzieję, że przekazałem pewien sens wielkości, o których myślałbym, porównując klasykę i kwant. Naprawdę nikt jeszcze nie zna stałych czynników, więc zdziwiłbym się, gdyby ktoś mógł lepiej oszacować dane niż „gdzieś w setkach bitów”.

Jak wspomniałem w komentarzach, bardzo precyzyjna odpowiedź będzie prawdopodobnie zależeć od wielu technicznych wyborów, które są nieco arbitralne. Prawdopodobnie ważniejsze będzie uzyskanie oszacowania rzędu wielkości i uwzględnienie jego możliwie największej liczby.

Ta odpowiedź nie ma być ostateczną odpowiedzią, ale krokiem we właściwym kierunku poprzez odniesienie do istniejącej literatury (choć trzeba przyznać, że ma już ponad dekadę), w szczególności:

• Van Meter, Itoh i Ladd. Czas wykonania algorytmu Shora zależny od architektury . Proc. Nadprzewodnictwo mezoskopowe + Spintronics 2006; [ arXiv: quant-ph / 0507023 ]

Van Meter, Itoh i Ladd próbują porównać wydajność algorytmu Shora z dostępną technologią obliczeniową wykonującą sito numerowe (najbardziej znany klasyczny algorytm faktoryzacji). Nie miałem czasu, aby zagłębić się w szczegóły artykułu - prawdopodobnie można by uzyskać lepszą odpowiedź - ale rysunek 1 tego artykułu pozwala nam dokonać rozsądnej oceny numerycznej:

Tutaj strome krzywe reprezentują czas obliczeniowy klasycznych sieci komputerowych. Krzywa oznaczona jako „NFS, 104 komputery, 2003” wydaje się wskazywać na obliczenia (i przewidywany czas obliczeń) stu czterech komputerów osobistych około 2003 r., Jak podał RSA Security Inc. w 2004 r. [ Http: //www.rsasecurity. com / rsalabs / node.asp? id = 2096] .

$n$$n \cdot v$$v$$2 \times 10^{11}$operacje na sekundę. Trzeba by przeprowadzić hipotetyczną analizę porównawczą algorytmu Shora względem komputera kwantowego działającego z porównywalną częstotliwością zegara.

$10^9$

• Pomimo przewagi operacji na sekundę wynoszącej 200 lub więcej, wykres wskazuje, kiedy ta klasyczna implementacja NFS 200GHz zostaje przekroczona przez komputer kwantowy 1GHz wykonujący algorytm Shora (przy liczbach około 200 cyfr) oraz przez komputer kwantowy 1 MHz ( około 330 cyfr).
• Mamy również krzywą przewidującą wydajność „w 2018 roku”, reprezentującą 1000 razy klasyczną moc obliczeniową: przechwyty z komputerami kwantowymi 1GHz i 1MHz mają liczby 350 bitów i liczby 530 bitów.

Wzrost punktów przecięcia w obliczeniach kwantowych, od obliczeń w 2003 r. Do prognozowanego w 2018 r., Reprezentujący przyspieszenie zegara o 1000, jest współczynnikiem około 5/3. Na podstawie tego możemy oszacować, że przewaga obliczeniowa w stosunku do wielkości liczb, którą można szybko rozwiązać za pomocą klasycznego komputera, ze względu na wzrost prędkości o współczynnik 200, wynosi około 7/6. Następnie możemy oszacować, że punkt przecięcia pojedynczego klasycznego komputera 1GHz wykonującego NFS z komputerem kwantowym 1GHz wykonującym algorytm Shora wynosi około 170 bitów.

Podsumowując - dokładna odpowiedź będzie zależeć od wielu założeń technicznych, które mogą znacznie zmienić dokładny wynik, więc lepiej jest szukać przybliżonych szacunków. Ale to pytanie zostało zbadane przynajmniej raz wcześniej, a biorąc pod uwagę pewną liczbę założeń i ekstrapolacji wydajności opartych na klasycznej wydajności w 2003 r., Wydaje się, że algorytmy Shora przewyższą najbardziej znany klasyczny algorytm pod względem operacji na liczbach około 170 bitów.