Efficient quantum algorithm for factorization

• Autorzy: Miszczak J.
• Języki publikacji: EN

Abstrakty

EN

This article for fast factorization on quantum computer. Quantum mechanic introduces to information processing new that can be used to solve efficiently problems classical known as hard. Simon algorithms was one of the first proofs that quantum computer has some advantages over classical model of computation. Shor generalized ideas introduce by Simon and show that real world problems are in range of quantum computation. Article presents also general description of quantum Fourier transform (QFT), which is without doubt the most powerful tool used in algorithms described in this paper. Generalization of algorithms for Simon problem and fast factorization gives new class of problems for which fast quantum algorithms can be construct.

PL

Artykuł prezentuje algorytm szybkiej faktoryzacji na komputerze kwantowym. Mechanika kwantowa wprowadziła do informatyki nowe efekty, które pozwalają na efektywne rozwiązywanie problemów klasycznie uważanych za trudne. Algorytm Simona był jednym z pierwszych dowodów na to, że komputer kwantowych posiada pewną przewagę nad klasycznym modelem obliczeń. Shor uogólniając idee Simona pokazał, że komputer kwantowy może służyć do rozwiązywania rzeczywistych problemów takich jak kryptoanaliza systemu RSA. W artykule omówiona jest także kwantowa transformacja Fouriera, która jest bez wątpienia najpotężniejszym narzędziem wykorzystywanym w omawianych algorytmach. Uogólnienie kwantowych algorytmów dla problemu Simona i faktoryzacji liczb pierwszych daje nową klasę problemów, dla których możliwa jest konstrukcja szybkich algorytmów kwantowych.

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2002
• Tom: T. 14, z. 2
• Strony: 117--129
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Miszczak J.

• Institute of Theoretical and Applied Informatics (IITiS), Polish Academy of Sciences , Gliwice, ul. Bałtycka 5, Poland

Bibliografia

• [1] David Deutsch, Rapid Solutions of Problems by Quantum Computation, Proc. R. Soc. Lond A 439, 1992, p. 553;
• [2] Daniel R. Simon, On the Power of Quantum Computation, Proceedings of the 35th Annual Sympo¬sium on Foundations of Computer Science, 1994, pp. i 16-123. Available at http://citeseer.nj.nec.com/8731 .html
• [3] Peter W. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, IEEE Symposium on Foundations of Computer Science, 1994, pp. 124-134. Available at http://citeseer.nj.nec.com/14533.html.
• [4] Samuel J. Lomonaco, A lecture on Shor’s Factoring Algorithm. Version 1.1.
• [5] Available at http://www.arxiv.org/abs/quant-ph/0010034.
• [6] Sławomir Bugajski, Jerzy Klamka, Stefan Węgrzyn, Foundations of quantum computing. Part I, Archiwum Informatyki Teoretycznej i Stosowanej, 13, 2001, pp. 97-142.
• [7] David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society, London, vol. A400, 1985. pp. 97-117.
• [8] Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood, Isaac L. Chuang, Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 2001, pp. 883-887.
• [9] Available at http://www.arxiv.org/abs/quant-ph/0112176
• [10] Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Richard Cleve, Isaac L. Chuang, Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer, Phys. Rev. Lett. 85, 25, pp. 5452-5455.
• [11] Available at http://www.arxiv.org/abs/quant-ph/0007017
• [12] Mika Hirvensalo, Quantum Computing, Springcr-Verlag, 2001.
• [13] David Deutsch, Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer, Proceedings of the Royal Society of London, vol. A400, 1985, pp. 97-117.
• [14] lohn Preskill, Lecture notes on physics: quantum compuation. Available at http://www.theory.caltech.edu/people/preskill/ph229/
• [15] Ethan Bernstein and Umesh Vazirani, Quantum Complexity Theory, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 11-20.
• [16] Available at http://citeseer.nj.nec.com/bemstein97quantum.html
• [17] Lov K. Grover, Quantum Mechanics Helps in Searching for a Needle in a Haystack, Phys. Rev. Lett, vol. 79,325,(1997).
• [18] Available at http://xxx.lanl.gov/abs/quant-ph/9706033.
• [19] Richard Jozsa, Searching in Grover's Search Algorithm. Available at http://xxx.lanl.gov/abs/quant- ph/9701021.
• [20] Samuel J. Lomonaco, Jr., Louis H. Kauffman, Quantum hidden subgroup algorithms: a mathematical perspective. Available at http://xxx.lanl.gov/abs/quant-ph/0201095.
• [21] Richard Jozsa, Quantum factoring, discrete logarithms and the hidden subgroup problem, Available at http://xxx.lanl.gov/abs/quant-ph/0012084.
• [22] Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptogra¬phy. Available at http://www.cacr.math.uwaterloo.ca/hac/.
• [23] Bruce Schneier, Kryptografia dla praktyków, WNT, 1996.
• [24] Richard Jozsa, Noan Linden, On the role of entanglement in quantum computational speedup. Avail¬able at http://xxx. 1 an 1. gov/abs/auant-nh/0201143.