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

11

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?

SalvaCardona
źródło
2
Bardzo precyzyjne obliczanie zależałoby od szczegółów, takich jak implementacja operacji dodawania w algorytmie kwantowym, a także od dokładnych operacji zastosowanych w najlepszym klasycznym algorytmie faktoryzacji. W obu przypadkach często jesteśmy przyzwyczajeni do ignorowania stałych czynników w ilości wymaganej pracy, ale nawet więcej w przypadku klasycznym niż przypadek kwantowy. Czy byłbyś zadowolony z oszacowania rzędu wielkości (np. Przewaga kwantowa uzyskana gdzieś pomiędzy 350-370 bitów --- aby zapewnić możliwą odpowiedź, którą stworzyłem z cienkiego powietrza w oparciu o brak rzeczywistej analizy)?
Niel de Beaudrap,
@NieldeBeaudrap Powiedziałbym, że z podanych przez ciebie powodów dokładna liczba byłaby niemożliwa do podania. Jeśli twoje oszacowanie „z powietrza” opiera się na pewnym rozumowaniu, myślę, że byłoby to interesujące. (Innymi słowy, wykształcone przypuszczenie ma wartość, ale dzikie przypuszczenie nie ma)
Dyskretna jaszczurka
@DiscreteLizard: gdybym miał dobry sposób oszacowania gotowy pod ręką, nie dałbym przykładowej odpowiedzi opartej na braku analizy :-) Jestem pewien, że istnieje rozsądny sposób na uzyskanie ciekawej oceny, ale te byłyby w stanie łatwo podać, paski błędów byłyby zbyt duże, aby były bardzo interesujące.
Niel de Beaudrap,
Ponieważ ten problem jest (lub był) powszechnie uznawany za typowy „dowód”, że komputery kwantowe są zdolne do osiągnięć poza sferą obliczeń klasycznych, ale prawie zawsze w kategoriach ścisłej złożoności obliczeniowej (a więc z pominięciem wszystkich stałych i tylko w przypadku arbitralnie wysokich danych wejściowych rozmiary) Powiedziałbym, że wstępna odpowiedź rzędu wielkości (i jej wyprowadzenie) byłaby już użyteczna / pedagogiczna. Może ludzie z CS / theoreticalCS byliby gotowi pomóc.
agaitaarino
1
@agaitaarino: Zgadzam się, choć odpowiedź będzie wymagać bardziej lub mniej precyzyjnego opisu wydajności najlepszych klasycznych algorytmów do faktoryzacji. Resztę może następnie wykonać dość dobry student obliczeń kwantowych.
Niel de Beaudrap,

Odpowiedzi:

8

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

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”.

Craig Gidney
źródło
To dobry wysiłek, ale jak oceniasz 30 bitów? Do czego dokładnie porównujesz algorytm Shora, jeśli uważasz, że to prawdopodobny punkt podziału?
Niel de Beaudrap,
1
@NieldeBeaudrap Tak jak powiedziałem, to szalone przypuszczenie. Myślę, że: modularne mnożenie ma przyzwoity stały współczynnik (klasycznie). Podobnie kontynuowane frakcje. Czy algorytmy faktoringowe mają również dobre stałe czynniki? Prawdopodobnie nie? Jeśli tak, crossover miałby miejsce niemal natychmiast, a nie przy dużych liczbach. Jeśli ktoś chce porównać te dwie rzeczy ze sobą, zaktualizuję odpowiedź. „Mięso” uważam za resztę.
Craig Gidney
1
Zwykle nie sprzeciwiałbym się temu jako zapewnieniu intuicji, z wyjątkiem tego, że twoje dzikie domysły dotyczą właśnie pytania. (Pytanie jest również postawione w taki sposób, że sugeruje świadomość problemów z zegarem). Najszybsze techniki faktoryzacji bardzo dużych liczb wymagają dużych stałych czynników, ale w rzeczywistości chodzi o to, aby się z nimi pogodzić; ale w przypadku liczb około miliarda możemy nawet rozważyć podział próbny przy użyciu tabeli liczb pierwszych do około 32 767, co w praktyce byłoby bardzo szybkie. Nawet porównanie ilościowe byłoby początkiem.
Niel de Beaudrap,
6

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:

wprowadź opis zdjęcia tutaj

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] .

nnvv2×1011operacje 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.

109

  • 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.

Niel de Beaudrap
źródło
To dobra odpowiedź. Warto zauważyć, że idea tego artykułu dotycząca „elementarnej operacji logicznej” jest (bardzo odpowiednio) na poziomie bramki AND, w przeciwieństwie do instrukcji procesora lub operacji BigInt (podejrzewam, że pytający był tym, o co pytał myślący). W mojej własnej odpowiedzi zakładałem, że potęgowanie modułowe zostało wykonane „jak klasycznie”, co wiązałoby się np. Z mnożeniem FFT. Właśnie dlatego odgadłem liczbę, która była o wiele niższa niż ta praca, która (odpowiednio) dokonuje mnożenia podręczników za pomocą dodatków do przenoszenia tętnień dla jego arytmetyki kwantowej.
Craig Gidney
@SalvaCardona: I zaleca, aby nie nie przyjąć moją odpowiedź. Moja analiza jest bardzo pobieżna i powinieneś się spodziewać lepszej analizy.
Niel de Beaudrap,