Numerical estimation of the quantum factorization effectiveness

• Autorzy: Zawadzki P.

Warianty tytułu

PL

Numeryczna ocena skuteczności algorytmu kwantowej faktoryzacji

• Języki publikacji: EN

Abstrakty

EN

The quantum factorization is probably the most famous algorithm in quantum computation. The algorithm succeeds only when some random number with an even order relative to factorized composite integer is fed as the input to the quantum order finding algorithm. Moreover, post processing of the quantum measurement recovers the correct order only for some subset of possible values. It is well known that numbers with even orders are found with probability not less than 1=2. However, numerical simulation proves that probability of such event exhibits grouping on some discrete levels above that limit. Thus, one may conclude that usage of the lowest estimate leads to underestimation of the successful factorization probability. The understanding of the observed grouping requires further research in that field.

PL

Algorytm kwantowej faktoryzacji liczb stał się jednym z głównych czynników stymulujących rozwój informatyki kwantowej. Algorytm ten, zaproponowany przez Shora [1], bazuje na redukcji problemu rozkładu na czynniki do problemu wyznaczenia rzędu liczby (1) w arytmetyce modularnej. Wyznaczanie rzędu liczb przy użyciu klasycznych komputerów ma złożoność wykładniczą, a więc nie przynosi żadnych korzyści w stosunku do standardowych algorytmów faktoryzacji, jednak komputery kwantowe umożliwiają jednoczesne wykonanie obliczeń dla wielu danych wejściowych (11) co prowadzi do obniżenia złożoności obliczeniowej problemu. Wprowadzenie losowego czynnika oraz właściwości kwantowego pomiaru prowadzą do probabilistycznego charakteru algorytmu. Prawdopodobieństwo niepowodzenia związane z niepewnością wyniku kwantowego pomiaru może być dowolnie zminimalizowane (14), jednak prawdopodobieństwo niepowodzenia klasycznego algorytmu rozwinięcia na ułamki łańcuchowe oraz wybrania czynnika nie spełniającego warunków algorytmu faktoryzacji są znaczne. Wyniki komputerowej symulacji wspomnianych prawdopodobieństw dla liczb złożonych stanowiących iloczyn dwóch liczb pierwszych, a więc o postaci wykorzystywanej w systemach kryptograficznych, przedstawiono odpowiednio na rys. 2 i rys. 3. Prawdopodobieństwo niepowodzenia wyznaczenia parzystego rzędu liczby na podstawie prawidłowego pomiaru kwantowego jest stosunkowo wysokie i jest bezpośrednim skutkiem właściwości funkcji totient Eulera (18). Powodzenie tego kroku może by´c zwiększone poprzez testowanie prawidłowości wielokrotności liczby otrzymanej z estymacji, jednak wpływu działań tego typu nie rozważano ze względu na mnogość dostępnych scenariuszy działania. Prawidłowy wybór czynnika x w równaniu (1) ma kluczowe znaczenie dla powodzenia dalszej części algorytmu. W literaturze [7] przyjmuje się, że prawdopodobieństwo właściwego wyboru x jest zawsze większe od 1=2. Jednak komputerowe symulacje dowodzą, że dla wielu liczb złożonych prawdopodobieństwo to znacznie przewyższa dolny kres, a w niektórych przypadkach jest bliskie 1. Można więc wnioskować, że funkcjonujące dotąd oceny skuteczności kwantowej faktoryzacji są znacznie zaniżone. Wyraźnie widoczne na rys. 3 grupowanie się wartości wspomnianego prawdopodobieństwa wokół dyskretnych poziomów sugeruje istnienie pewnej wewnętrznej zależności wynikającej z właściwości czynników tworzących liczbę złożoną. Wyniki tego typu nie były dotąd prezentowane w literaturze i wymagają dalszych badań.

Słowa kluczowe

EN

quantum computation; probabilistic algorithm

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2010
• Tom: Vol. 22, No. 1
• Strony: 63--72
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Zawadzki P.

• Silesian University of Technology, Institute of Electronics, Akademicka 16, 44-100 Gliwice, Poland,

Bibliografia

• 1. P. W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Sci. Comput. 26, 1484-1509 (1997).
• 2. L. K. Grover: A fast quantum mechanical algorithm for database search. In: 28th Annual ACM Symposium on the Theory of Computing. pp. 212-219 (1996).
• 3. E. Gerjuoy: Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers. A. J. Phys. 73, 521-540 (2005).
• 4. E. Knill: On Shor’s quantum factor finding algorithm: Increasing the probability of success and tradeoffs involving the Fourier Transform modulus, Technical Report LAUR-95-3350, Los Alamos Laboratory, (1995).
• 5. D. McAnally: A refinement of Shor’s algorithm. (2001).
• 6. P.S. Bourdon, H.T. Williams: Probability estimates for Shor’s algorithm. Quant. Inf. Comput. 7, 522-550 (2007).
• 7. A. Ekert, R. Jozsa: Quantum computation and Shor’s factoring algorithm. Rev. Mod. Phys. 68, 733-753 (1996).
• 8. M. A. Nielsen, I. L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press (2000).
• 9. E. Desurvire: Classical and Quantum Information Theory. Cambridge University Press (2009).
• 10. L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, I. L. Chuang: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature. 414, 883-887 (2001).