Institute of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
Objectives:
• 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 https://ibm.webex.com/meet/tomasz.stopa
Program:
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
Presentation
Abstract:
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.
References
[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: http://arxiv.org/abs/quant-ph/0205095
[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: http://arxiv.org/abs/1611.07995
[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: http://arxiv.org/abs/1706.07884