Jest to „pytanie historyczne” bardziej niż pytanie badawcze, ale czy klasyczne sprowadzenie do ustalania porządku w algorytmie Shora dla faktoryzacji zostało początkowo odkryte przez Petera Shora, czy też było wcześniej znane? Czy istnieje artykuł opisujący redukcję, która poprzedza Shora, czy jest to tak zwany „wynik ludowy”? A może był to po prostu kolejny przełom w tym samym artykule?
Odpowiedzi:
Muszę przyznać (zaskakujące, jak się wydaje), że tak naprawdę nie znam odpowiedzi. Sam odkryłem lub odkryłem tę redukcję.
Najpierw odkryłem algorytm dziennika dyskretnego, a drugi algorytm faktoryzacji, więc z dziennika dyskretnego wiedziałem, że okresowość jest przydatna. Wiedziałem, że faktoring był równoznaczny ze znalezieniem dwóch nierównych liczb o równych kwadratach (mod N) - jest to podstawa algorytmu kwadratowego sita. Widziałem także redukcję faktoringu do znalezienia funkcji Eulera , która jest dość podobna.
Wprawdzie wymyśliłem redukcję tego pytania do znajdowania zamówień, nie jest to trudne, więc nie zdziwiłbym się, gdyby istniał inny artykuł opisujący tę redukcję, który poprzedza moje. Nie sądzę jednak, aby był to powszechnie znany „wynik ludowy”. Nawet jeśli ktoś to odkrył, przed obliczeniami kwantowymi dlaczego ktoś miałby przejmować się redukowaniem faktoringu do kwestii znajdowania zamówień (możliwe wykładnicze na klasycznym komputerze)?
EDYCJA: Zauważ, że ustalanie kolejności jest możliwe do wykładniczego tylko w ustawieniach wyroczni; znalezienie modułu modulo jest równoznaczne z faktoringiem , co zostało udowodnione wcześniej przez Heather Woll, jak wskazuje druga odpowiedź.
Losowa redukcja od faktoryzacji do ustalania kolejności (mod N) była bardzo dobrze znana osobom pracującym w algorytmach teorii liczb na przełomie lat 70. i 80. Rzeczywiście, pojawia się w pracy Heather Woll, Redukcje wśród wielu problemów teoretycznych, Information and Computation 72 (1987) 167-179 oraz Eric Bach i ja znaliśmy to wcześniej.
Zastanawiam się, dlaczego Peter Shor twierdzi, że poszukiwanie porządku „jest możliwe do udowodnienia na klasycznym komputerze”. Jeśli znamy faktoryzację N, a także (oba obliczalne w czasie sub wykładniczym) i pracujemy modulo na każdej mocy pierwotnej, można znaleźć zamówienia.