Institute of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
•    understand and discuss current problems in quantum informatics,
•    discuss new quantum computing technologies,
•    exchange ideas and research results,
•    integrate information across different research teams,
•    build a community around quantum informatics.
Venue:  via Internet, Webex

Tuesday, 1st of June 2021, 9:30-11:00

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

Topic: 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:

  • 3 years ago