{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T04:09:07Z","timestamp":1749614947928,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>\n            Recently, Cai [\n            <jats:xref ref-type=\"bibr\">3<\/jats:xref>\n            ] showed that Shor\u2019s quantum factoring algorithm fails to factor large integers when algorithm\u2019s quantum Fourier transform (QFT) is corrupted by a vanishing level of random noise on the QFT\u2019s precise controlled rotation gates. We show that under the same error model, Shor\u2019s quantum discrete log algorithm, and its various modifications, fail to compute discrete logs modulo\n            <jats:italic>P<\/jats:italic>\n            for a positive density of primes\n            <jats:italic>P<\/jats:italic>\n            and a similarly vanishing level of noise. We also show that the same noise level causes Shor\u2019s algorithm to fail with probability\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1-o(1)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            to compute discrete logs modulo\n            <jats:italic>P<\/jats:italic>\n            for randomly selected primes\n            <jats:italic>P<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3736421","type":"journal-article","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T11:06:26Z","timestamp":1747479986000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Algorithms for Discrete Log Require Precise Rotations"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-0675-6060","authenticated-orcid":false,"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[{"name":"Computer Sciences, University of Wisconsin-Madison, Madison, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1921-7253","authenticated-orcid":false,"given":"Ben","family":"Young","sequence":"additional","affiliation":[{"name":"Computer Sciences, University of Wisconsin-Madison, Madison, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.54.139"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44750-4_34"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-023-3961-3"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1515\/jmc-2013-0038"},{"key":"e_1_3_2_6_2","unstructured":"D. Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph\/0201067 [quant-ph] https:\/\/arxiv.org\/abs\/quant-ph\/0201067"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1515\/jmc-2020-0006"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","unstructured":"Martin Eker\u00e5 and Joel G\u00e4rtner. 2024. Extending regev\u2019s factoring algorithm to compute discrete logarithms. In Post-Quantum Cryptography - 15th International Workshop PQCrypto 2024 Oxford UK June 12-14 2024 Proceedings Part II (Lecture Notes in Computer Science Vol. 14772) Markku-Juhani O. Saarinen and Daniel Smith-Tone (Eds.). Springer 211\u2013242. arXiv:2311.05545 [quant-ph]. DOI:10.1007\/978-3-031-62746-0_10","DOI":"10.1007\/978-3-031-62746-0_10"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59879-6_20"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388980"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.032329"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.75.029905"},{"key":"e_1_3_2_15_2","unstructured":"Kurt Girstmair. 2024. Private communication."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.3228"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892139"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-019-2562-5"},{"key":"e_1_3_2_19_2","first-page":"745","article-title":"A quantum \u201cMagic Box\u201d for the discrete logarithm problem","volume":"2017","author":"Kaliski Burton S.","year":"2017","unstructured":"Burton S. Kaliski. 2017. A quantum \u201cMagic Box\u201d for the discrete logarithm problem. IACR Cryptol. ePrint Arch. 2017 (2017), 745. Retrieved from https:\/\/api.semanticscholar.org\/CorpusID:42139218","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_20_2","unstructured":"Alexei Y. Kitaev. 1996. Quantum measurements and the Abelian Stabilizer Problem. Electron. Colloquium Comput. Complex. TR96-003 (1996). ECCC:TR96-003 https:\/\/eccc.weizmann.ac.il\/eccc-reports\/1996\/TR96-003\/index.html"},{"key":"e_1_3_2_21_2","unstructured":"Chris Lomont. 2004. The Hidden Subgroup Problem\u2014Review and Open Problems. (Nov.2004). Retrieved from http:\/\/arxiv.org\/abs\/quant-ph\/0411037arXiv:quant-ph\/0411037."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49208-9_15"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749904000109"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.032333"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.89.042337"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","unstructured":"Y. S. Nam and R. Bl\u00fcmel. 2015. Performance scaling of the quantum Fourier transform with defective rotation gates. Quantum Inf. Comput. 15 9&10 (2015) 721\u2013736. DOI:10.26421\/QIC15.9-10-1","DOI":"10.26421\/QIC15.9-10-1"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-015-0923-2"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011528.2011531"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","unstructured":"Oded Regev. 2025. An efficient quantum factoring algorithm. J. ACM 72 1 (Jan. 2025) 10:1\u201310:13. DOI:10.1145\/3708471","DOI":"10.1145\/3708471"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022317"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T12:48:58Z","timestamp":1749559738000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3736421"],"URL":"https:\/\/doi.org\/10.1145\/3736421","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"type":"print","value":"2643-6809"},{"type":"electronic","value":"2643-6817"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-02-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}