Paper 2023/092
Estimation of Shor's Circuit for 2048bit Integers based on Quantum Simulator
Abstract
Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSAtype composite numbers up to 9bit using a quantum computer simulator. In the largest case, $N=511$ was factored within 2 hours. Then, based on these experiments, we estimate the number of gates and the depth of Shor's quantum circuits for factoring 1024bit and 2048bit integers. In our estimation, Shor's quantum circuit for factoring 1024bit integers requires $2.78 \times 10^{11}$ gates, and with depth $2.24 \times 10^{11}$, while $2.23 \times 10^{12}$ gates, and with depth $1.80 \times 10^{12}$ for 2048bit integers.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint.
 Keywords
 Shor algorithminteger factorizationquantum computerquantum computer simulator
 Contact author(s)

jyamaguchi @ fujitsu com
izu @ fujitsu com  History
 20230126: approved
 20230125: received
 See all versions
 Short URL
 https://ia.cr/2023/092
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/092, author = {Junpei Yamaguchi and Masafumi Yamazaki and Akihiro Tabuchi and Takumi Honda and Tetsuya Izu and Noboru Kunihiro}, title = {Estimation of Shor's Circuit for 2048bit Integers based on Quantum Simulator}, howpublished = {Cryptology ePrint Archive, Paper 2023/092}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/092}}, url = {https://eprint.iacr.org/2023/092} }