{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T18:55:00Z","timestamp":1782327300795,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We decompose two implementations of Shor\u2019s algorithm for prime factorization into universal gate units at the logical level and predict the number of physical qubits and execution time when surface codes are used. Logical qubit encoding using a rotated surface code and logical qubits with all-to-all connectivity are assumed. We express the number of physical qubits and execution time in terms of the bit length of the number to be factorized and error rate of the physical quantum gate. We confirm the relationship between the number of qubits and the execution time by analyzing two algorithms using various bit lengths and physical gate error rates .<\/jats:p>","DOI":"10.1007\/s11128-021-03398-1","type":"journal-article","created":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T11:05:36Z","timestamp":1642676736000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Resource analysis of quantum computing with noisy qubits for Shor\u2019s factoring algorithms"],"prefix":"10.1007","volume":"21","author":[{"given":"Jinyoung","family":"Ha","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonghyun","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Heo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,1,20]]},"reference":[{"key":"3398_CR1","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th annual symposium on foundations of computer science, pp. 124\u2013134. Ieee (1994)"},{"issue":"7779","key":"3398_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F.G.S.L., Buell, D.A., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505\u2013510 (2019)","journal-title":"Nature"},{"key":"3398_CR3","unstructured":"IBM Quantum (2021)"},{"key":"3398_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018)","journal-title":"Quantum"},{"issue":"3","key":"3398_CR5","doi-asserted-by":"publisher","first-page":"032324","DOI":"10.1103\/PhysRevA.86.032324","volume":"86","author":"AG Fowler","year":"2012","unstructured":"Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N.: Surface codes: Towards practical large-scale quantum computation. Physical Review A 86(3), 032324 (2012)","journal-title":"Physical Review A"},{"issue":"3","key":"3398_CR6","doi-asserted-by":"publisher","first-page":"032338","DOI":"10.1103\/PhysRevA.95.032338","volume":"95","author":"J O\u2019Gorman","year":"2017","unstructured":"O\u2019Gorman, J., Campbell, E.T.: Quantum computation with realistic magic-state factories. Physical Review A 95(3), 032338 (2017)","journal-title":"Physical Review A"},{"issue":"5","key":"3398_CR7","doi-asserted-by":"publisher","first-page":"054033","DOI":"10.1103\/PhysRevApplied.13.054033","volume":"13","author":"Y Hwang","year":"2020","unstructured":"Hwang, Y., Kim, T., Baek, C., Choi, Byung-Soo.: Integrated analysis of performance and resources in large-scale quantum computing. Physical Review Applied 13(5), 054033 (2020)","journal-title":"Physical Review Applied"},{"key":"3398_CR8","doi-asserted-by":"publisher","first-page":"433","DOI":"10.22331\/q-2021-04-15-433","volume":"5","author":"C Gidney","year":"2021","unstructured":"Gidney, C., Eker\u00e5, M.: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433 (2021)","journal-title":"Quantum"},{"key":"3398_CR9","unstructured":"Fowler, A.G., Gidney, C.: Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709 (2018)"},{"key":"3398_CR10","doi-asserted-by":"crossref","unstructured":"Beauregard, S.: Circuit for Shor\u2019s algorithm using 2n+ 3 qubits. arXiv preprint quant-ph\/0205095 (2002)","DOI":"10.26421\/QIC3.2-8"},{"key":"3398_CR11","unstructured":"Pavlidis, A., Gizopoulos, D.: Fast quantum modular exponentiation architecture for Shor\u2019s factorization algorithm. (2012). arXiv preprint arXiv:1207.0511"},{"issue":"1","key":"3398_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1103\/PhysRevA.54.147","volume":"54","author":"V Vedral","year":"1996","unstructured":"Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Physical Review A 54(1), 147 (1996)","journal-title":"Physical Review A"},{"issue":"12","key":"3398_CR13","doi-asserted-by":"publisher","first-page":"123011","DOI":"10.1088\/1367-2630\/14\/12\/123011","volume":"14","author":"C Horsman","year":"2012","unstructured":"Horsman, C., Fowler, A.G., Devitt, S., Van Meter, R.: Surface code quantum computing by lattice surgery. New Journal of Physics 14(12), 123011 (2012)","journal-title":"New Journal of Physics"},{"issue":"5","key":"3398_CR14","doi-asserted-by":"publisher","first-page":"052312","DOI":"10.1103\/PhysRevA.80.052312","volume":"80","author":"AG Fowler","year":"2009","unstructured":"Fowler, A.G., Stephens, Ashley\u00a0M., Groszkowski, P.: High-threshold universal quantum computation on the surface code. Physical Review A 80(5), 052312 (2009)","journal-title":"Physical Review A"},{"issue":"1954","key":"3398_CR15","doi-asserted-by":"publisher","first-page":"2551","DOI":"10.1098\/rspa.1996.0136","volume":"452","author":"A Steane","year":"1996","unstructured":"Steane, A.: Multiple-particle interference and quantum error correction. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452(1954), 2551\u20132577 (1996)","journal-title":"Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences"},{"key":"3398_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.22331\/q-2019-04-30-135","volume":"3","author":"C Gidney","year":"2019","unstructured":"Gidney, C., Fowler, A.G.: Efficient magic state factories with a catalyzed $$| {CCZ}\\rangle $$ to 2$$|{T}\\rangle $$ transformation. Quantum 3, 135 (2019)","journal-title":"Quantum"},{"key":"3398_CR17","doi-asserted-by":"crossref","unstructured":"Knill, E., Laflamme, R.: Concatenated quantum codes. arXiv preprint quant-ph\/9608012 (1996)","DOI":"10.2172\/369608"},{"issue":"4","key":"3398_CR18","doi-asserted-by":"publisher","first-page":"042322","DOI":"10.1103\/PhysRevA.68.042322","volume":"68","author":"AM Steane","year":"2003","unstructured":"Steane, A.M.: Overhead and noise threshold of fault-tolerant quantum error correction. Physical Review A 68(4), 042322 (2003)","journal-title":"Physical Review A"},{"key":"3398_CR19","volume-title":"Quantum Computation and Quantum Information: 10th Anniversary Edition","author":"MA Nielsen","year":"2011","unstructured":"Nielsen, M.A., Chuang, Isaac L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, USA (2011)","edition":"10"},{"issue":"11\u201312","key":"3398_CR20","doi-asserted-by":"publisher","first-page":"932","DOI":"10.26421\/QIC15.11-12-4","volume":"15","author":"Neil\u00a0J Ross","year":"2015","unstructured":"Ross, Neil\u00a0J.: Optimal ancilla-free Clifford+ V approximation of z-rotations. Quantum Information & Computation 15(11\u201312), 932\u2013950 (2015)","journal-title":"Quantum Information & Computation"},{"issue":"3","key":"3398_CR21","doi-asserted-by":"publisher","first-page":"032329","DOI":"10.1103\/PhysRevA.70.032329","volume":"70","author":"AG Fowler","year":"2004","unstructured":"Fowler, A.G., Hollenberg, L.C.L.: Scalability of Shor\u2019s algorithm with a limited set of rotation gates. Physical Review A 70(3), 032329 (2004)","journal-title":"Physical Review A"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03398-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03398-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03398-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T09:38:23Z","timestamp":1645004303000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03398-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["3398"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03398-1","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,20]]},"assertion":[{"value":"8 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"60"}}