{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T17:11:25Z","timestamp":1775754685685,"version":"3.50.1"},"publisher-location":"Cham","reference-count":104,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032226945","type":"print"},{"value":"9783032226952","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22695-2_1","type":"book-chapter","created":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T16:29:14Z","timestamp":1775752154000},"page":"3-36","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Practicality of\u00a0Quantum Sieving Algorithms for\u00a0the\u00a0Shortest Vector Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8265-7334","authenticated-orcid":false,"given":"Joao F.","family":"Doriguello","sequence":"first","affiliation":[]},{"given":"George","family":"Giapitzakis","sequence":"additional","affiliation":[]},{"given":"Alessandro","family":"Luongo","sequence":"additional","affiliation":[]},{"given":"Aditya","family":"Morolia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,10]]},"reference":[{"key":"1_CR1","unstructured":"https:\/\/github.com\/TheCharmingSociopath\/qsieve"},{"key":"1_CR2","doi-asserted-by":"publisher","unstructured":"Achlioptas, D.: Database-friendly random projections. In: Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. PODS \u201901, New York, NY, USA, pp. 274\u2013281. Association for Computing Machinery (2001). https:\/\/doi.org\/10.1145\/375551.375608","DOI":"10.1145\/375551.375608"},{"issue":"4","key":"1_CR3","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671\u2013687 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00025-4","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR4","doi-asserted-by":"publisher","unstructured":"Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in $$2^n$$ time using discrete Gaussian sampling: Extended abstract. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC \u201915, New York, NY, USA, pp. 733\u2013742. Association for Computing Machinery (2015). https:\/\/doi.org\/10.1145\/2746539.2746606","DOI":"10.1145\/2746539.2746606"},{"issue":"8","key":"1_CR5","doi-asserted-by":"publisher","first-page":"2201","DOI":"10.1109\/TIT.2002.800499","volume":"48","author":"E Agrell","year":"2002","unstructured":"Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Trans. Inf. Theory 48(8), 2201\u20132214 (2002). https:\/\/doi.org\/10.1109\/TIT.2002.800499","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1_CR6","doi-asserted-by":"publisher","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC \u201996, New York, NY, USA, pp. 99\u2013108. Association for Computing Machinery (1996). https:\/\/doi.org\/10.1145\/237814.237838","DOI":"10.1145\/237814.237838"},{"key":"1_CR7","doi-asserted-by":"publisher","unstructured":"Ajtai, M.: The shortest vector problem in $${L}_2$$ is NP-hard for randomized reductions (extended abstract). In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC \u201998, New York, NY, USA, pp. 10\u201319. Association for Computing Machinery (1998). https:\/\/doi.org\/10.1145\/276698.276705","DOI":"10.1145\/276698.276705"},{"key":"1_CR8","doi-asserted-by":"publisher","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: An overview of the sieve algorithm for the shortest lattice vector problem. In: Silverman, J.H. (ed.) Cryptography and Lattices. pp.\u00a01\u20133. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44670-2_1","DOI":"10.1007\/3-540-44670-2_1"},{"key":"1_CR9","doi-asserted-by":"publisher","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. STOC \u201901, New York, NY, USA, pp. 601\u2013610. Association for Computing Machinery (2001). https:\/\/doi.org\/10.1145\/380752.380857","DOI":"10.1145\/380752.380857"},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 717\u2013746. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17656-3_25","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"1_CR11","doi-asserted-by":"publisher","unstructured":"Albrecht, M.R., Gheorghiu, V., Postlethwaite, E.W., Schanck, J.M.: Estimating quantum speedups for lattice sieves. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 583\u2013613. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64834-3_20","DOI":"10.1007\/978-3-030-64834-3_20"},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Allcock, J., Bao, J., Doriguello, J.F., Luongo, A., Santha, M.: Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates. Quantum 8, 1530 (2024). https:\/\/doi.org\/10.22331\/q-2024-11-20-1530","DOI":"10.22331\/q-2024-11-20-1530"},{"key":"1_CR13","doi-asserted-by":"publisher","unstructured":"Andoni, A., Indyk, P., Nguyen, H.L., Razenshteyn, I.: Beyond locality-sensitive hashing. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201914, USA, pp. 1018\u20131028. Society for Industrial and Applied Mathematics (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.76","DOI":"10.1137\/1.9781611973402.76"},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Andoni, A., Razenshteyn, I.: Optimal data-dependent hashing for approximate near neighbors. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC \u201915, New York, NY, USA, pp. 793\u2013801. Association for Computing Machinery (2015). https:\/\/doi.org\/10.1145\/2746539.2746553","DOI":"10.1145\/2746539.2746553"},{"issue":"12","key":"1_CR15","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/17\/12\/123010","volume":"17","author":"S Arunachalam","year":"2015","unstructured":"Arunachalam, S., Gheorghiu, V., Jochym-O\u2019Connor, T., Mosca, M., Srinivasan, P.V.: On the robustness of bucket brigade quantum RAM. New J. Phys. 17(12), 123010 (2015). https:\/\/doi.org\/10.1088\/1367-2630\/17\/12\/123010","journal-title":"New J. Phys."},{"key":"1_CR16","unstructured":"Avanzi, R., et al.: CRYSTALS-Kyber (version 3.02) \u2013 submission to round 3 of the NIST post-quantum project (2021). https:\/\/pq-crystals.org\/kyber\/data\/kyber-specification-round3-20210131.pdf"},{"key":"1_CR17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.8.041015","volume":"8","author":"R Babbush","year":"2018","unstructured":"Babbush, R., et al.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8, 041015 (2018). https:\/\/doi.org\/10.1103\/PhysRevX.8.041015","journal-title":"Phys. Rev. X"},{"key":"1_CR18","unstructured":"Bai, S., et al.: CRYSTALS-Dilithium: algorithm specifications and supporting documentation (version 3.1) (2021). https:\/\/pq-crystals.org\/dilithium\/data\/dilithium-specification-round3-20210208.pdf"},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Bai, S., van Hoof, M.I., Johnson, F.B., Lange, T., Ngo, T.: Concrete analysis of quantum lattice enumeration. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023. LNCS, vol. 14440, pp. 131\u2013166. Springer, Singapore (2023). https:\/\/doi.org\/10.1007\/978-981-99-8727-6_5","DOI":"10.1007\/978-981-99-8727-6_5"},{"key":"1_CR20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.060504","volume":"117","author":"CJ Ballance","year":"2016","unstructured":"Ballance, C.J., Harty, T.P., Linke, N.M., Sepiol, M.A., Lucas, D.M.: High-fidelity quantum logic gates using trapped-ion hyperfine qubits. Phys. Rev. Lett. 117, 060504 (2016). https:\/\/doi.org\/10.1103\/PhysRevLett.117.060504","journal-title":"Phys. Rev. Lett."},{"key":"1_CR21","doi-asserted-by":"publisher","unstructured":"Battistel, F., et al.: Real-time decoding for fault-tolerant quantum computing: progress, challenges and outlook. Nano Futures 7(3), 032003 (2023). https:\/\/doi.org\/10.1088\/2399-1984\/aceba6","DOI":"10.1088\/2399-1984\/aceba6"},{"key":"1_CR22","doi-asserted-by":"publisher","unstructured":"Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201916, USA, pp. 10\u201324. Society for Industrial and Applied Mathematics (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch2","DOI":"10.1137\/1.9781611974331.ch2"},{"key":"1_CR23","unstructured":"Becker, A., Gama, N., Joux, A.: Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. Cryptology ePrint Archive (2015)"},{"key":"1_CR24","doi-asserted-by":"publisher","unstructured":"Becker, A., Laarhoven, T.: Efficient (ideal) lattice sieving using cross-polytope LSH. In: Pointcheval, D., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 3\u201323. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-31517-1_1","DOI":"10.1007\/978-3-319-31517-1_1"},{"issue":"7671","key":"1_CR25","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1038\/nature23461","volume":"549","author":"DJ Bernstein","year":"2017","unstructured":"Bernstein, D.J., Lange, T.: Post-quantum cryptography. Nature 549(7671), 188\u2013194 (2017). https:\/\/doi.org\/10.1038\/nature23461","journal-title":"Nature"},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Bindel, N., Bonnetain, X., Tiepelt, M., Virdia, F.: Quantum lattice enumeration in limited depth. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14925, pp. 72\u2013106. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68391-6_3","DOI":"10.1007\/978-3-031-68391-6_3"},{"key":"1_CR27","doi-asserted-by":"publisher","unstructured":"Bonnetain, X., Chailloux, A., Schrottenloher, A., Shen, Y.: Finding many collisions via reusable quantum walks. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 221\u2013251. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30589-4_8","DOI":"10.1007\/978-3-031-30589-4_8"},{"key":"1_CR28","doi-asserted-by":"publisher","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4-5), 493\u2013505 (1998). https:\/\/doi.org\/10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory 6(3) (2014). https:\/\/doi.org\/10.1145\/2633600","DOI":"10.1145\/2633600"},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume":"305","author":"G Brassard","year":"2002","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53\u201374 (2002). https:\/\/doi.org\/10.1090\/conm\/305\/05215","journal-title":"Contemp. Math."},{"key":"1_CR31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022316","volume":"71","author":"S Bravyi","year":"2005","unstructured":"Bravyi, S., Kitaev, A.: Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316 (2005). https:\/\/doi.org\/10.1103\/PhysRevA.71.022316","journal-title":"Phys. Rev. A"},{"key":"1_CR32","doi-asserted-by":"publisher","unstructured":"Cade, C., Folkertsma, M., Niesen, I., Weggemans, J.: Quantifying Grover speed-ups beyond asymptotic analysis. Quantum 7, 1133 (2023). https:\/\/doi.org\/10.22331\/q-2023-10-10-1133","DOI":"10.22331\/q-2023-10-10-1133"},{"key":"1_CR33","doi-asserted-by":"publisher","unstructured":"Chailloux, A., Loyer, J.: Lattice sieving via quantum random walks. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13093, pp. 63\u201391. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-92068-5_3","DOI":"10.1007\/978-3-030-92068-5_3"},{"key":"1_CR34","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.010331","volume":"3","author":"C Chamberland","year":"2022","unstructured":"Chamberland, C., Campbell, E.T.: Universal quantum computing with twist-free and temporally encoded lattice surgery. PRX Quantum 3, 010331 (2022). https:\/\/doi.org\/10.1103\/PRXQuantum.3.010331","journal-title":"PRX Quantum"},{"key":"1_CR35","doi-asserted-by":"publisher","unstructured":"Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing. STOC \u201902, New York, NY, USA, pp. 380\u2013388. Association for Computing Machinery (2002). https:\/\/doi.org\/10.1145\/509907.509965","DOI":"10.1145\/509907.509965"},{"key":"1_CR36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.127.130505","volume":"127","author":"CR Clark","year":"2021","unstructured":"Clark, C.R., et al.: High-fidelity Bell-state preparation with $$^{40}{\\rm Ca }^{+}$$ optical qubits. Phys. Rev. Lett. 127, 130505 (2021). https:\/\/doi.org\/10.1103\/PhysRevLett.127.130505","journal-title":"Phys. Rev. Lett."},{"key":"1_CR37","doi-asserted-by":"publisher","unstructured":"Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv preprint quant-ph\/0410184 (2004). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0410184","DOI":"10.48550\/arXiv.quant-ph\/0410184"},{"key":"1_CR38","doi-asserted-by":"publisher","unstructured":"Dalzell, A.M., et al.: A distillation-teleportation protocol for fault-tolerant QRAM. arXiv preprint arXiv:2505.20265 (2025). https:\/\/doi.org\/10.48550\/arXiv.2505.20265","DOI":"10.48550\/arXiv.2505.20265"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2020.2965803","volume":"1","author":"O Di Matteo","year":"2020","unstructured":"Di Matteo, O., Gheorghiu, V., Mosca, M.: Fault-tolerant resource estimation of quantum random-access memories. IEEE Trans. Quantum Eng. 1, 1\u201313 (2020). https:\/\/doi.org\/10.1109\/TQE.2020.2965803","journal-title":"IEEE Trans. Quantum Eng."},{"key":"1_CR40","doi-asserted-by":"publisher","unstructured":"Doriguello, J.F., Giapitzakis, G., Luongo, A., Morolia, A.: On the practicality of quantum sieving algorithms for the shortest vector problem. arXiv preprint arXiv:2410.13759 (2024). https:\/\/doi.org\/10.48550\/arXiv.2410.13759","DOI":"10.48550\/arXiv.2410.13759"},{"key":"1_CR41","doi-asserted-by":"publisher","unstructured":"Draper, T., Kutin, S., Rains, E., Svore, K.: A logarithmic-depth quantum carry-lookahead adder. Quantum Inf. Comput. 6(4&5), 351\u2013369 (2006). https:\/\/doi.org\/10.26421\/qic6.4-5-4","DOI":"10.26421\/qic6.4-5-4"},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170), 463\u2013471 (1985), http:\/\/www.jstor.org\/stable\/2007966","DOI":"10.1090\/S0025-5718-1985-0777278-8"},{"key":"1_CR43","doi-asserted-by":"publisher","unstructured":"Fowler, A.G., Gidney, C.: Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709 (2018). https:\/\/doi.org\/10.48550\/arXiv.1808.06709","DOI":"10.48550\/arXiv.1808.06709"},{"key":"1_CR44","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.060505","volume":"117","author":"JP Gaebler","year":"2016","unstructured":"Gaebler, J.P., Tan, T.R., Lin, Y., Wan, Y., Bowler, R., Keith, A.C., Glancy, S., Coakley, K., Knill, E., Leibfried, D., Wineland, D.J.: High-fidelity universal gate set for $${^{9}\\rm Be }^{+}$$ ion qubits. Phys. Rev. Lett. 117, 060505 (2016). https:\/\/doi.org\/10.1103\/PhysRevLett.117.060505","journal-title":"Phys. Rev. Lett."},{"key":"1_CR45","doi-asserted-by":"publisher","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. STOC \u201909, New York, NY, USA, pp. 169\u2013178. Association for Computing Machinery (2009). https:\/\/doi.org\/10.1145\/1536414.1536440","DOI":"10.1145\/1536414.1536440"},{"key":"1_CR46","doi-asserted-by":"publisher","first-page":"74","DOI":"10.22331\/q-2018-06-18-74","volume":"2","author":"C Gidney","year":"2018","unstructured":"Gidney, C.: Halving the cost of quantum addition. Quantum 2, 74 (2018). https:\/\/doi.org\/10.22331\/q-2018-06-18-74","journal-title":"Quantum"},{"key":"1_CR47","doi-asserted-by":"publisher","unstructured":"Gidney, C.: How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv preprint arXiv:2505.15917 (2025). https:\/\/doi.org\/10.48550\/arXiv.2505.15917","DOI":"10.48550\/arXiv.2505.15917"},{"key":"1_CR48","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). https:\/\/doi.org\/10.22331\/q-2021-04-15-433","journal-title":"Quantum"},{"key":"1_CR49","doi-asserted-by":"publisher","unstructured":"Gidney, C., Fowler, A.G.: Efficient magic state factories with a catalyzed $$|CCZ\\rangle $$ to $$2|T\\rangle $$ transformation. Quantum 3, 135 (2019). https:\/\/doi.org\/10.22331\/q-2019-04-30-135","DOI":"10.22331\/q-2019-04-30-135"},{"key":"1_CR50","doi-asserted-by":"publisher","unstructured":"Gidney, C., Shutty, N., Jones, C.: Magic state cultivation: growing T states as cheap as CNOT gates. arXiv preprint arXiv:2409.17595 (2024). https:\/\/doi.org\/10.48550\/arXiv.2409.17595","DOI":"10.48550\/arXiv.2409.17595"},{"key":"1_CR51","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.052310","volume":"78","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Architectures for a quantum random access memory. Phys. Rev. A 78, 052310 (2008). https:\/\/doi.org\/10.1103\/PhysRevA.78.052310","journal-title":"Phys. Rev. A"},{"key":"1_CR52","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100, 160501 (2008). https:\/\/doi.org\/10.1103\/PhysRevLett.100.160501","journal-title":"Phys. Rev. Lett."},{"key":"1_CR53","doi-asserted-by":"publisher","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC \u201996, New York, NY, USA, pp. 212\u2013219. Association for Computing Machinery (1996). https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"key":"1_CR54","doi-asserted-by":"publisher","first-page":"71","DOI":"10.22331\/q-2018-06-07-71","volume":"2","author":"J Haah","year":"2018","unstructured":"Haah, J., Hastings, M.B.: Codes and Protocols for Distilling $$T$$, controlled-$$S$$, and Toffoli Gates. Quantum 2, 71 (2018). https:\/\/doi.org\/10.22331\/q-2018-06-07-71","journal-title":"Quantum"},{"key":"1_CR55","unstructured":"Hann, C.T.: Practicality of Quantum Random Access Memory. Ph.D. thesis, Yale University (2021)"},{"key":"1_CR56","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.020311","volume":"2","author":"CT Hann","year":"2021","unstructured":"Hann, C.T., Lee, G., Girvin, S., Jiang, L.: Resilience of quantum random access memory to generic noise. PRX Quantum 2, 020311 (2021). https:\/\/doi.org\/10.1103\/PRXQuantum.2.020311","journal-title":"PRX Quantum"},{"key":"1_CR57","doi-asserted-by":"publisher","unstructured":"Hanrot, G., Pujol, X., Stehl\u00e9, D.: Algorithms for the shortest and closest lattice vector problems. In: Chee, Y.M., et al. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 159\u2013190. Springer, Heidelberg, (2011). https:\/\/doi.org\/10.1007\/978-3-642-20901-7_10","DOI":"10.1007\/978-3-642-20901-7_10"},{"key":"1_CR58","doi-asserted-by":"publisher","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267\u2013288. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054868","DOI":"10.1007\/BFb0054868"},{"key":"1_CR59","doi-asserted-by":"publisher","unstructured":"Horsman, D., Fowler, A.G., Devitt, S., Meter, R.V.: Surface code quantum computing by lattice surgery. New J. Phys. 14(12), 123011 (2012). https:\/\/doi.org\/10.1088\/1367-2630\/14\/12\/123011","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"1_CR60","unstructured":"Inc., S.I.: NTRU challenge parameter sets and public keys. https:\/\/web.archive.org\/web\/20160310141551\/https:\/\/www.securityinnovation.com\/uploads\/ntru-challenge-parameter-sets-and-public-keys-new.pdf"},{"key":"1_CR61","doi-asserted-by":"publisher","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC \u201998, New York, NY, USA, pp. 604\u2013613. Association for Computing Machinery (1998). https:\/\/doi.org\/10.1145\/276698.276876","DOI":"10.1145\/276698.276876"},{"key":"1_CR62","doi-asserted-by":"publisher","unstructured":"Jaques, S., Rattew, A.G.: QRAM: a survey and critique. Quantum 9, 1922 (2025). https:\/\/doi.org\/10.22331\/q-2025-12-02-1922","DOI":"10.22331\/q-2025-12-02-1922"},{"key":"1_CR63","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.022328","volume":"87","author":"C Jones","year":"2013","unstructured":"Jones, C.: Low-overhead constructions for the fault-tolerant Toffoli gate. Phys. Rev. A 87, 022328 (2013). https:\/\/doi.org\/10.1103\/PhysRevA.87.022328","journal-title":"Phys. Rev. A"},{"key":"1_CR64","doi-asserted-by":"publisher","unstructured":"Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC \u201983, New York, NY, USA, pp. 193\u2013206. Association for Computing Machinery (1983). https:\/\/doi.org\/10.1145\/800061.808749","DOI":"10.1145\/800061.808749"},{"key":"1_CR65","doi-asserted-by":"publisher","unstructured":"Kim, H., et al.: Finding shortest vector using quantum NV sieve on Grover. In: Seo, H., Kim, S. (eds.) ICISC 2023. LNCS, vol. 14561. pp. 97\u2013118. Springer, Singapore (2024). https:\/\/doi.org\/10.1007\/978-981-97-1235-9_6","DOI":"10.1007\/978-981-97-1235-9_6"},{"key":"1_CR66","unstructured":"Kim, H., Jang, K., Kim, H., Baksi, A., Chakraborty, S., Seo, H.: Quantum NV sieve on Grover for solving shortest vector problem. Cryptology ePrint Archive (2024)"},{"key":"1_CR67","doi-asserted-by":"publisher","unstructured":"Kirshanova, E., May, A., Nowakowski, J.: New NTRU records with improved lattice bases. In: Johansson, T., Smith-Tone, D. (eds.) PQCrypto 2023. LNCS, vol. 14154, pp. 167\u2013195. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-40003-2_7","DOI":"10.1007\/978-3-031-40003-2_7"},{"issue":"6","key":"1_CR68","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1070\/RM1997v052n06ABEH002155","volume":"52","author":"AY Kitaev","year":"1997","unstructured":"Kitaev, A.Y.: Quantum computations: algorithms and error correction. Russ. Math. Surv. 52(6), 1191 (1997). https:\/\/doi.org\/10.1070\/RM1997v052n06ABEH002155","journal-title":"Russ. Math. Surv."},{"issue":"1","key":"1_CR69","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0003-4916(02)00018-0","volume":"303","author":"A Kitaev","year":"2003","unstructured":"Kitaev, A.: Fault-tolerant quantum computation by Anyons. Ann. Phys. 303(1), 2\u201330 (2003). https:\/\/doi.org\/10.1016\/S0003-4916(02)00018-0","journal-title":"Ann. Phys."},{"issue":"5349","key":"1_CR70","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1126\/science.279.5349.342","volume":"279","author":"E Knill","year":"1998","unstructured":"Knill, E., Laflamme, R., Zurek, W.H.: Resilient quantum computation. Science 279(5349), 342\u2013345 (1998). https:\/\/doi.org\/10.1126\/science.279.5349.342","journal-title":"Science"},{"key":"1_CR71","doi-asserted-by":"publisher","unstructured":"Laarhoven, T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 3\u201322. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_1","DOI":"10.1007\/978-3-662-47989-6_1"},{"key":"1_CR72","unstructured":"Laarhoven, T.: Search problems in cryptography: from fingerprinting to lattice sieving. Ph.D. thesis, Mathematics and Computer Science (2016)"},{"issue":"2","key":"1_CR73","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10623-015-0067-5","volume":"77","author":"T Laarhoven","year":"2015","unstructured":"Laarhoven, T., Mosca, M., van de Pol, J.: Finding shortest lattice vectors faster using quantum search. Des. Codes Crypt. 77(2), 375\u2013400 (2015). https:\/\/doi.org\/10.1007\/s10623-015-0067-5","journal-title":"Des. Codes Crypt."},{"key":"1_CR74","doi-asserted-by":"publisher","unstructured":"Laarhoven, T., de\u00a0Weger, B.: Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. In: Lauter, K., Rodr\u00edguez-Henr\u00edquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 101\u2013118. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-22174-8_6","DOI":"10.1007\/978-3-319-22174-8_6"},{"issue":"6","key":"1_CR75","doi-asserted-by":"publisher","DOI":"10.1007\/s11433-021-1874-2","volume":"65","author":"HS Li","year":"2022","unstructured":"Li, H.S., Fan, P., Xia, H., Long, G.L.: The circuit design and optimization of quantum multiplier and divider. Sci. China Phys. Mech. Astron. 65(6), 260311 (2022). https:\/\/doi.org\/10.1007\/s11433-021-1874-2","journal-title":"Sci. China Phys. Mech. Astron."},{"key":"1_CR76","doi-asserted-by":"publisher","unstructured":"Li, P., Hastie, T.J., Church, K.W.: Very sparse random projections. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD \u201906, New York, NY, USA, pp. 287\u2013296. Association for Computing Machinery (2006). https:\/\/doi.org\/10.1145\/1150402.1150436","DOI":"10.1145\/1150402.1150436"},{"key":"1_CR77","doi-asserted-by":"publisher","unstructured":"Litinski, D.: A game of surface codes: large-scale quantum computing with lattice surgery. Quantum 3, 128 (2019). https:\/\/doi.org\/10.22331\/q-2019-03-05-128","DOI":"10.22331\/q-2019-03-05-128"},{"key":"1_CR78","doi-asserted-by":"publisher","unstructured":"Litinski, D.: Magic state distillation: not as costly as you think. Quantum 3, 205 (2019). https:\/\/doi.org\/10.22331\/q-2019-12-02-205","DOI":"10.22331\/q-2019-12-02-205"},{"key":"1_CR79","doi-asserted-by":"publisher","unstructured":"Litinski, D.: How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. arXiv preprint arXiv:2306.08585 (2023). https:\/\/doi.org\/10.48550\/arXiv.2306.08585","DOI":"10.48550\/arXiv.2306.08585"},{"key":"1_CR80","doi-asserted-by":"publisher","unstructured":"Litinski, D.: Quantum schoolbook multiplication with fewer Toffoli gates. arXiv preprint arXiv:2410.00899 (2024). https:\/\/doi.org\/10.48550\/arXiv.2410.00899","DOI":"10.48550\/arXiv.2410.00899"},{"key":"1_CR81","doi-asserted-by":"publisher","unstructured":"Litinski, D., Nickerson, N.: Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections. arXiv preprint arXiv:2211.15465 (2022). https:\/\/doi.org\/10.48550\/arXiv.2211.15465","DOI":"10.48550\/arXiv.2211.15465"},{"issue":"8","key":"1_CR82","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1038\/s41567-020-0903-z","volume":"16","author":"IS Madjarov","year":"2020","unstructured":"Madjarov, I.S., et al.: High-fidelity entanglement and detection of alkaline-earth Rydberg atoms. Nat. Phys. 16(8), 857\u2013861 (2020). https:\/\/doi.org\/10.1038\/s41567-020-0903-z","journal-title":"Nat. Phys."},{"key":"1_CR83","doi-asserted-by":"publisher","unstructured":"Mariano, A., Dagdelen, \u00d6., Bischof, C.: A comprehensive empirical comparison of parallel ListSieve and GaussSieve. In: Lopes, L., et al. (eds.) Euro-Par 2014. LNCS, vol. 8805, pp. 48\u201359. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-14325-5_5","DOI":"10.1007\/978-3-319-14325-5_5"},{"key":"1_CR84","doi-asserted-by":"publisher","unstructured":"Micciancio, D.: The shortest vector in a lattice is hard to approximate to within some constant. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. FOCS \u201998, USA, p.\u00a092. IEEE Computer Society (1998). https:\/\/doi.org\/10.1137\/S0097539700373039","DOI":"10.1137\/S0097539700373039"},{"key":"1_CR85","doi-asserted-by":"publisher","unstructured":"Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing. STOC \u201910, New York, NY, USA, pp. 351\u2013358. Association for Computing Machinery (2010). https:\/\/doi.org\/10.1145\/1806689.1806739","DOI":"10.1145\/1806689.1806739"},{"key":"1_CR86","doi-asserted-by":"publisher","unstructured":"Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201910, USA, pp. 1468\u20131480. Society for Industrial and Applied Mathematics (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.119","DOI":"10.1137\/1.9781611973075.119"},{"issue":"1","key":"1_CR87","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1038\/s41534-022-00644-x","volume":"8","author":"IN Moskalenko","year":"2022","unstructured":"Moskalenko, I.N., et al.: High fidelity two-qubit gates on fluxoniums using a tunable coupler. NPJ Quantum Inf. 8(1), 130 (2022). https:\/\/doi.org\/10.1038\/s41534-022-00644-x","journal-title":"NPJ Quantum Inf."},{"issue":"1","key":"1_CR88","doi-asserted-by":"publisher","first-page":"11002","DOI":"10.1038\/s41598-025-95283-5","volume":"15","author":"P Mukhopadhyay","year":"2025","unstructured":"Mukhopadhyay, P.: A quantum random access memory (QRAM) using a polynomial encoding of binary strings. Sci. Rep. 15(1), 11002 (2025). https:\/\/doi.org\/10.1038\/s41598-025-95283-5","journal-title":"Sci. Rep."},{"issue":"5","key":"1_CR89","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1109\/TC.2018.2882774","volume":"68","author":"E Mu\u00f1oz-Coreas","year":"2019","unstructured":"Mu\u00f1oz-Coreas, E., Thapliyal, H.: Quantum circuit design of a T-count optimized integer multiplier. IEEE Trans. Comput. 68(5), 729\u2013739 (2019). https:\/\/doi.org\/10.1109\/TC.2018.2882774","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"1_CR90","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1515\/JMC.2008.009","volume":"2","author":"PQ Nguyen","year":"2008","unstructured":"Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol. 2(2), 181\u2013207 (2008). https:\/\/doi.org\/10.1515\/JMC.2008.009","journal-title":"J. Math. Cryptol."},{"key":"1_CR91","unstructured":"NIST: Post-quantum cryptography: Call for proposals. https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography\/Post-Quantum-Cryptography-Standardization\/Call-for-Proposals. Accessed 05 Feb 2024"},{"key":"1_CR92","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2020.102810","volume":"170","author":"F Orts","year":"2020","unstructured":"Orts, F., Ortega, G., Combarro, E., Garz\u00f3n, E.: A review on reversible quantum adders. J. Netw. Comput. Appl. 170, 102810 (2020). https:\/\/doi.org\/10.1016\/j.jnca.2020.102810","journal-title":"J. Netw. Comput. Appl."},{"key":"1_CR93","doi-asserted-by":"publisher","unstructured":"Pohst, M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. SIGSAM Bull. 15(1), 37\u201344 (1981). https:\/\/doi.org\/10.1145\/1089242.1089247","DOI":"10.1145\/1089242.1089247"},{"key":"1_CR94","doi-asserted-by":"publisher","unstructured":"Preskill, J.: Reliable quantum computers. Proc. Roy. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 454(1969), 385\u2013410 (1998). https:\/\/doi.org\/10.1098\/rspa.1998.0167","DOI":"10.1098\/rspa.1998.0167"},{"key":"1_CR95","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2024.3501683","volume":"6","author":"M Prokop","year":"2025","unstructured":"Prokop, M., Wallden, P., Joseph, D.: Grover\u2019s oracle for the shortest vector problem and its application in hybrid classical\u2013quantum solvers. IEEE Trans. Quantum Eng. 6, 1\u201315 (2025). https:\/\/doi.org\/10.1109\/TQE.2024.3501683","journal-title":"IEEE Trans. Quantum Eng."},{"key":"1_CR96","unstructured":"Pujol, X., Stehle, D.: Solving the shortest lattice vector problem in time $$2^{2.465n}$$. Cryptology ePrint Archive, Paper 2009\/605 (2009)"},{"key":"1_CR97","doi-asserted-by":"publisher","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. STOC \u201905, New York, NY, USA, pp. 84\u201393. Association for Computing Machinery (2005). https:\/\/doi.org\/10.1145\/1060590.1060603","DOI":"10.1145\/1060590.1060603"},{"key":"1_CR98","doi-asserted-by":"publisher","unstructured":"Regev, O.: Lattice-based cryptography. In: Dwork, C. (eds.) CRYPTO 2006. LNCS, vol. 4117, pp. 131\u2013141. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11818175_8","DOI":"10.1007\/11818175_8"},{"issue":"3","key":"1_CR99","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s11128-005-7654-8","volume":"4","author":"BW Reichardt","year":"2005","unstructured":"Reichardt, B.W.: Quantum universality from magic states distillation applied to CSS codes. Quantum Inf. Process. 4(3), 251\u2013264 (2005). https:\/\/doi.org\/10.1007\/s11128-005-7654-8","journal-title":"Quantum Inf. Process."},{"key":"1_CR100","doi-asserted-by":"publisher","unstructured":"Schneider, M.: Analysis of gauss-sieve for solving the shortest vector problem in lattices. In: Katoh, N., Kumar, A. (eds.) WALCOM 2011. LNCS, vol. 6552, pp. 89\u201397. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19094-0_11","DOI":"10.1007\/978-3-642-19094-0_11"},{"key":"1_CR101","doi-asserted-by":"publisher","unstructured":"Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134 (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365700","DOI":"10.1109\/SFCS.1994.365700"},{"key":"1_CR102","doi-asserted-by":"publisher","unstructured":"Wang, X., Liu, M., Tian, C., Bi, J.: Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. In: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security. ASIACCS \u201911, New York, NY, USA, pp. 1\u20139. Association for Computing Machinery (2011). https:\/\/doi.org\/10.1145\/1966913.1966915","DOI":"10.1145\/1966913.1966915"},{"issue":"11","key":"1_CR103","doi-asserted-by":"publisher","first-page":"1842","DOI":"10.1038\/s41567-025-03026-0","volume":"21","author":"A Wills","year":"2025","unstructured":"Wills, A., Hsieh, M.H., Yamasaki, H.: Constant-overhead magic state distillation. Nat. Phys. 21(11), 1842\u20131846 (2025). https:\/\/doi.org\/10.1038\/s41567-025-03026-0","journal-title":"Nat. Phys."},{"key":"1_CR104","doi-asserted-by":"publisher","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","volume":"60","author":"C Zalka","year":"1999","unstructured":"Zalka, C.: Grover\u2019s quantum searching algorithm is optimal. Phys. Rev. A 60, 2746\u20132751 (1999). https:\/\/doi.org\/10.1103\/PhysRevA.60.2746","journal-title":"Phys. Rev. A"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22695-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T16:29:20Z","timestamp":1775752160000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22695-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032226945","9783032226952"],"references-count":104,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22695-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"10 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Saint-Malo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}