Zapraszamy na Krakow Quantum Informatics Seminar organizowane wspólnie przez Instytut Informatyki AGH i IBM Software Lab Kraków. Spotkanie odbędzie się we wtorek 1.06.2021 w godzinach 9:30-11:00 via Internet, Webex

W programie: 

Bartłomiej Stępień, Institute of Computer Science, AGH Krakow

Temat: A survey of current research on Shor Algorithm with Qiskit



Shor's algorithm is one of the most famous example of quantum computing application. This algorithm, first proposed by Peter Shor in 1994 [1], solves the problem of factorization integer in polynomial time. Although it’s the best known realisation comes from 2003 [2], it is still considered to be of interest among researchers. As a part of this talk, the basis of Shor's algorithm will be introduced. The state of the art regarding variants of implementation (e.g. [3], [4], [5]) will be presented. Also, improved implementation of [3] will be proposed, and its properties and performance will be compared with other implementations.


[1] P. W. Shor, ‘Algorithms for quantum computation: discrete logarithms and factoring’, in Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124–134. doi: 10.1109/SFCS.1994.365700.

[2] S. Beauregard, ‘Circuit for Shor’s algorithm using 2n+3 qubits’, arXiv:quant-ph/0205095, Feb. 2003, Accessed: May 19, 2021. [Online]. Available:

[3] Y. Takahashi and N. Kunihiro, ‘A quantum circuit for Shor’s factoring algorithm using 2n+2 qubits’, QIC, vol. 6, no. 2, pp. 184–192, Mar. 2006, doi: 10.26421/QIC6.2-4.

[4] T. Häner, M. Roetteler, and K. M. Svore, ‘Factoring using 2n+2 qubits with Toffoli based modular multiplication’, arXiv:1611.07995 [quant-ph], Jun. 2017, Accessed: May 19, 2021. [Online]. Available:

[5] C. Gidney, ‘Factoring with n+2 clean qubits and n-1 dirty qubits’, arXiv:1706.07884 [quant-ph], Jan. 2018, Accessed: May 19, 2021. [Online]. Available:

  • 1 rok, 8 miesięcy temu