Quantum algorithms simulations

NAISS 2023/22-808


NAISS Small Compute

Principal Investigator:

Martin Ekerå


Kungliga Tekniska högskolan

Start Date:


End Date:


Primary Classification:

10201: Computer Sciences




This is a continuation of project SNIC 2022/22-35: "Quantum algorithms simulations" previously approved by PDC. Since 2016, I have developed and analyzed quantum algorithms with cryptanalytical and number theoretical applications — with a particular focus on algorithms for order finding, discrete logarithms and factoring. For further details, please see e.g. references [1-7]. As of writing, there are no known large-scale fault-tolerant quantum computers in existence that are capable of running these quantum algorithms in practice with respect to interesting problem instances. However, there is considerable traction in this field of research, and it is conceivable that such quantum computers may become available sometime in the future. The aforementioned quantum algorithms do not immediately yield the quantities sought; rather, the output from one or more runs of these algorithms must be post-processed using classical algorithms. In order to develop estimates for how many times the quantum algorithms will need to be run on future large-scale quantum computers for the post-processing to yield the quantities sought, and in order to estimate the post-processing complexity and the success probability, numerical simulations sometimes constitute a useful complement to mathematical analysis. Some of these simulations require HPC resources. I am currently working on some improvements and generalizations of my earlier works, on verifying some new mathematical analyses, and on answering questions posed with respect to my works — for instance by reviewers and by fellow researchers with whom I cooperate academically. As I foresee that I may need to undertake additional computations to finish this line of work, and that there may potentially also be new avenues to explore, I am hereby requesting a small local allocation on Dardel at PDC. References: [1] Ekerå, M. and Håstad, J.: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: Proceedings of PQCrypto 2017, Utrecht, the Netherlands, Springer LNCS 10346, pp. 347–363 (2017). [2] Ekerå, M.: On post-processing in the algorithm for computing short discrete logarithms. Des. Codes, Cryptogr. 88(11), pp. 2313–2335 (2020). [3] Ekerå, M.: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs, J. Math. Cryptol. 15(1), pp. 359-407 (2021). [4] Gidney, C. and Ekerå, M.: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5:433, pp. 1-31 (2021). [5] Ekerå, M.: On completely factoring any integer efficiently in a single run of an order finding algorithm, Quantum Inf. Process. 20:205, pp. 1–14 (2021). [6] Ekerå, M.: On the success probability of quantum order finding, arXiv:2201.07791v2 (2022). [7] Ekerå, M.: Revisiting Shor's quantum algorithm for computing general discrete logarithms, arXiv:1905.09084v3 (2019–2023).