pith. sign in

arxiv: 2410.13759 · v2 · submitted 2024-10-17 · 🪐 quant-ph · cs.CR

On the practicality of quantum sieving algorithms for the shortest vector problem

Joao F. Doriguello , George Giapitzakis , Alessandro Luongo , Aditya Morolia This is my paper

Pith reviewed 2026-05-23 18:32 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords shortest vector problemquantum sievingGrover searchpost-quantum cryptographyresource estimationquantum error correctionlattice cryptography
0
0 comments X

The pith

Even under optimistic assumptions, quantum sieving for the shortest vector problem in dimension 400 requires about 10^13 physical qubits and 10^31 years.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper performs a detailed resource estimation for quantum sieving algorithms that incorporate Grover's search to solve the shortest vector problem. It factors in the costs of quantum arithmetic, non-asymptotic search, QRAM, and error correction across different architectures. The analysis concludes that for lattice dimensions around 400, which are relevant to current post-quantum cryptography proposals, these quantum approaches provide little to no advantage over classical computation. This matters because the hardness of SVP under quantum attacks underpins the security of lattice-based cryptographic schemes.

Core claim

Under very optimistic assumptions including circuit-level noise of 10^{-5}, 100 ns code cycles, 1 μs reaction time, state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms still require approximately 10^{13} physical qubits and 10^{31} years to solve SVP on a lattice of dimension 400. A 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time. The authors conclude there is currently little to no quantum speedup in the dimensions of cryptographic interest.

What carries the argument

Resource estimation model for quantum sieving that includes fixed-point quantum arithmetic, non-asymptotic Grover search, QRAM costs, and quantum error correction.

Load-bearing premise

The assumed performance of quantum error correction, arithmetic circuits, QRAM, and non-asymptotic Grover search costs under the given noise and timing parameters holds at the scales required.

What would settle it

An experiment or simulation showing that the total runtime or qubit overhead for quantum sieving on dimension 100 or similar scales much better than the extrapolated model, or hardware achieving the noise rate with fewer qubits.

Figures

Figures reproduced from arXiv: 2410.13759 by Aditya Morolia, Alessandro Luongo, George Giapitzakis, Joao F. Doriguello.

Figure 1
Figure 1. Figure 1: Number of physical qubits and execution time of all Grover’s searches in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 10
Figure 10. Figure 10: ]). A similar procedure can be used to perform a [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗
Figure 2
Figure 2. Figure 2: Gidney’s out-of-place quantum adder (modulo [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Circuit for Grover’s search algorithm (top) and the Grover oracle [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The bucket-brigade QRAM circuit from Arunachalam et al. [23]. In every layer, before the parallel layer of Toffoli gates, a log-depth linear-size gadget copy the index register so the Toffoli gates can be executed in parallel. 7 The shortest vector problem and sieving algorithms The most important problem on lattices and that underlies many lattice-based cryptography func￾tions [10, 175, 177, 156] is the s… view at source ↗
Figure 5
Figure 5. Figure 5: Number of physical qubits of all Grover’s searches in [PITH_FULL_IMAGE:figures/full_fig_p043_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Reaction limit of all Grover’s searches in [PITH_FULL_IMAGE:figures/full_fig_p044_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Number of physical qubits and reaction limit of [PITH_FULL_IMAGE:figures/full_fig_p045_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Number of physical qubits and reaction limit of [PITH_FULL_IMAGE:figures/full_fig_p046_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Comparison between quantum resources of GaussSieve obtained through heuristic assump￾tions and through numerical data. (a) Comparison between physical qubits under baseline and active￾volume architectures. (b) Comparison between reaction limit and circuit time under baseline and active-volume architectures. The heuristic data is obtained through the assumptions from Section 8.2, while the numerical data is… view at source ↗
Figure 10
Figure 10. Figure 10: Number of physical qubits and circuit times in [PITH_FULL_IMAGE:figures/full_fig_p063_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Number of physical qubits and circuit times in [PITH_FULL_IMAGE:figures/full_fig_p064_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Number of physical qubits and circuit times in [PITH_FULL_IMAGE:figures/full_fig_p065_12.png] view at source ↗
read the original abstract

One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of lattice problems like the shortest vector problem (SVP), which asks to find the shortest non-zero vector in an integer lattice. Asymptotic quantum speedups for solving SVP are known and rely on Grover's search. However, to assess the security of lattice-based cryptography against these Grover-like quantum speedups, it is necessary to carry out a precise resource estimation beyond asymptotic scalings. In this work, we perform a careful analysis on the resources required to implement several sieving algorithms aided by Grover's search for dimensions of cryptographic interests. For such, we take into account fixed-point quantum arithmetic operations, non-asymptotic Grover's search, the cost of using quantum random access memory (QRAM), different physical architectures, and quantum error correction. We find that even under very optimistic assumptions like circuit-level noise of $10^{-5}$, code cycles of 100 ns, reaction time of 1 $\mu$s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require $\approx 10^{13}$ physical qubits and $\approx 10^{31}$ years to solve SVP on a lattice of dimension 400, which is roughly the dimension for minimally secure post-quantum cryptographic standards currently being proposed by NIST. We estimate that a 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time to solve the same problem. We conclude that there is currently little to no quantum speedup in the dimensions of cryptographic interest and the possibility of realising a considerable quantum speedup using quantum sieving algorithms would require significant breakthroughs in theoretical protocols and hardware development.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper conducts a detailed resource estimation for quantum sieving algorithms (aided by Grover search) applied to the shortest vector problem (SVP) in dimensions of cryptographic interest (~400). It incorporates models for fixed-point arithmetic, non-asymptotic Grover costs, QRAM overhead, physical architectures, and quantum error correction under optimistic parameters (10^{-5} circuit noise, 100 ns code cycles, 1 μs reaction time). The central conclusion is that the best variants still require ~10^{13} physical qubits and ~10^{31} years, comparable to a 6 GHz classical single-core machine, implying negligible quantum speedup at these scales.

Significance. If the estimates hold, the work supplies concrete, dimension-specific evidence that current quantum sieving approaches do not undermine lattice-based post-quantum cryptography at NIST-relevant dimensions. Explicit documentation of all modeling choices for arithmetic circuits, Grover search, QRAM, and QEC performance constitutes a strength, enabling future sensitivity analyses. The comparison to classical runtime further grounds the practicality assessment.

major comments (2)
  1. [§4] §4 (resource estimation for sieving), the non-asymptotic Grover iteration count: the overhead for amplitude amplification to reach the target success probability is stated but the propagation of this factor through the total physical-qubit and wall-clock-time budgets (Tables 5–7) should be shown explicitly, as it directly scales the headline 10^{31}-year figure.
  2. [§3.2 and §5] §3.2 (QRAM model) and §5 (QEC overhead): the assumed O(log N) depth per access and the surface-code patch size under 10^{-5} noise are load-bearing for the 10^{13}-qubit count; a sensitivity table varying the QRAM depth assumption by ±50% would strengthen the claim that hardware breakthroughs are required.
minor comments (3)
  1. [Figure 2] Figure 2 caption: the legend for the different sieving variants is too small for readability; enlarge or move to a table.
  2. [§2 and §4] Notation: the symbol T for both classical and quantum wall-clock time is overloaded; introduce subscripts (T_class, T_quant) in §2 and §4.
  3. [References] Reference list: the 2023–2024 QEC papers on reaction-time assumptions are cited but the exact parameter values taken from each should be tabulated for traceability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback on our resource estimation for quantum sieving algorithms. The suggestions for greater explicitness in our calculations will improve the manuscript's clarity without altering its central conclusions. We address each major comment below.

read point-by-point responses

  1. Referee: [§4] §4 (resource estimation for sieving), the non-asymptotic Grover iteration count: the overhead for amplitude amplification to reach the target success probability is stated but the propagation of this factor through the total physical-qubit and wall-clock-time budgets (Tables 5–7) should be shown explicitly, as it directly scales the headline 10^{31}-year figure.

    Authors: We agree that explicit propagation of the amplitude amplification overhead would enhance transparency. This factor is already included in the headline estimates and all intermediate calculations, but we will revise Tables 5–7 (and associated text in §4) to include a dedicated column or footnote tracing its contribution to physical qubit counts and wall-clock time. This change will be made in the next version. revision: yes

  2. Referee: [§3.2 and §5] §3.2 (QRAM model) and §5 (QEC overhead): the assumed O(log N) depth per access and the surface-code patch size under 10^{-5} noise are load-bearing for the 10^{13}-qubit count; a sensitivity table varying the QRAM depth assumption by ±50% would strengthen the claim that hardware breakthroughs are required.

    Authors: The O(log N) QRAM depth and surface-code parameters are indeed central assumptions, chosen as optimistic baselines consistent with the literature. We will add a sensitivity table (new Table in §3.2 or §5) showing the effect of varying QRAM depth by ±50% on total resources. This will demonstrate that the prohibitive scaling persists across the range, reinforcing the need for hardware and theoretical advances. The table will be included in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity in resource estimation derivations

full rationale

The paper performs resource estimation for quantum sieving algorithms using explicitly stated external models for fixed-point arithmetic, non-asymptotic Grover search, QRAM overhead, and QEC performance under given noise and timing parameters. No load-bearing step reduces a claimed runtime or qubit count to a fitted parameter or self-citation defined by the same analysis; all quantitative results are built from documented assumptions and standard circuit costs independent of the target SVP dimension conclusions. The central claim of negligible quantum advantage at cryptographic dimensions therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

3 free parameters · 2 axioms · 0 invented entities

The central claim rests on several optimistic hardware parameters and quantum operation models that are assumed rather than derived from first principles or measured data.

free parameters (3)
  • circuit-level noise = 10^{-5}
    Optimistic assumption stated as 10^{-5}
  • code cycle time = 100 ns
    Optimistic assumption stated as 100 ns
  • reaction time = 1 μs
    Optimistic assumption stated as 1 μs
axioms (2)
  • domain assumption Fixed-point quantum arithmetic, non-asymptotic Grover search, and QRAM cost models are accurate at the scales considered
    Invoked to produce the resource counts
  • domain assumption State-of-the-art error-correction protocols achieve the stated performance under the given noise
    Required for the physical-qubit estimate

pith-pipeline@v0.9.0 · 5865 in / 1339 out tokens · 31711 ms · 2026-05-23T18:32:23.950245+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Efficient Quantum State Preparation with Bucket Brigade QRAM

    quant-ph 2025-10 unverdicted novelty 6.0

    Encodes M by N matrix into quantum state using Θ(log(MN)) qubits in O(log²(MN)) time via segment tree embedded in bucket brigade QRAM with constant ancillas and O(MN) memory cells.

Reference graph

Works this paper leans on

207 extracted references · 207 canonical work pages · cited by 1 Pith paper · 7 internal anchors

  1. [1]

    https://github.com/TheCharmingSociopath/qsieve. 8

    work page

  2. [2]

    Database-friendly random projections

    Dimitris Achlioptas. Database-friendly random projections. In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’01, page 274–281, New York, NY, USA, 2001. Association for Computing Machinery. 28

    work page 2001

  3. [3]

    Database-friendly random projections: Johnson-Lindenstrauss with binary coins

    Dimitris Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671–687, 2003. Special Issue on PODS

    work page 2003

  4. [4]

    Improved classical and quan- tum algorithms for the shortest vector problem via bounded distance decoding.arXiv preprint arXiv:2002.07955, 2020

    Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved classical and quan- tum algorithms for the shortest vector problem via bounded distance decoding.arXiv preprint arXiv:2002.07955, 2020. 4

    work page arXiv 2002

  5. [5]

    Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract

    Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 733–742, New York, NY, USA, 2015. Association for Computing Machinery. 3, 4, 24

    work page 2015

  6. [6]

    Agrell, T

    E. Agrell, T. Eriksson, A. Vardy, and K. Zeger. Closest point search in lattices.IEEE Transac- tions on Information Theory, 48(8):2201–2214, 2002. 3, 24

    work page 2002

  7. [7]

    Aharonov and M

    D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, page 176–188, New York, NY, USA, 1997. Association for Computing Machinery. 14

    work page 1997

  8. [8]

    M. Ajtai. Generating hard instances of lattice problems (extended abstract). InProceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 99–108, New York, NY, USA, 1996. Association for Computing Machinery. 2

    work page 1996

  9. [9]

    The shortest vector problem inL2 is NP-hard for randomized reductions (extended abstract)

    Miklós Ajtai. The shortest vector problem inL2 is NP-hard for randomized reductions (extended abstract). In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 10–19, New York, NY, USA, 1998. Association for Computing Machinery. 23

    work page 1998

  10. [10]

    A public-key cryptosystem with worst-case/average-case equiv- alence

    Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equiv- alence. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, page 284–293, New York, NY, USA, 1997. Association for Computing Machinery. 23

    work page 1997

  11. [11]

    An overview of the sieve algorithm for the shortest lattice vector problem

    Miklós Ajtai, Ravi Kumar, and Dandapani Sivakumar. An overview of the sieve algorithm for the shortest lattice vector problem. In Joseph H. Silverman, editor,Cryptography and Lattices, pages 1–3, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. 3, 24

    work page 2001

  12. [12]

    A sieve algorithm for the shortest lattice vector problem

    Miklós Ajtai, Ravi Kumar, and Dandapani Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC ’01, page 601–610, New York, NY, USA, 2001. Association for Computing Machinery. 3, 24

    work page 2001

  13. [13]

    Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W

    Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 717–746, Cham, 2019. Springer International Publishing. 4

    work page 2019

  14. [14]

    Albrecht, Vlad Gheorghiu, Eamonn W

    Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite, and John M. Schanck. Estimat- ing quantum speedups for lattice sieves. In Shiho Moriai and Huaxiong Wang, editors,Advances in Cryptology – ASIACRYPT 2020, pages 583–613, Cham, 2020. Springer International Publish- ing. 3, 4, 6, 7, 43, 47 48

    work page 2020

  15. [15]

    Albrecht, Miloš Prokop, Yixin Shen, and Petros Wallden

    Martin R. Albrecht, Miloš Prokop, Yixin Shen, and Petros Wallden. Variational quantum solu- tions to the Shortest Vector Problem.Quantum, 7:933, March 2023. 4

    work page 2023

  16. [16]

    Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits.arXiv preprint arXiv:2308.08539, 2023

    Jonathan Allcock, Jinge Bao, João F Doriguello, Alessandro Luongo, and Miklos Santha. Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits.arXiv preprint arXiv:2308.08539, 2023. 22

    work page arXiv 2023

  17. [17]

    Mishal Almazrooie, Azman Samsudin, Rosni Abdullah, and Kussay N. Mutter. Quantum re- versible circuit of AES-128.Quantum Information Processing, 17(5):112, Mar 2018. 4

    work page 2018

  18. [18]

    Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3

    Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, and John Schanck. Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In Roberto Avanzi and Howard Heys, editors,Selected Areas in Cryptography – SAC 2016, pages 317–337, Cham, 2017. Springer International Publishing. 4

    work page 2016

  19. [19]

    Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits.IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 32(6):818–830, 2013. 17

    work page 2013

  20. [20]

    Nguyen, and Ilya Razenshteyn

    Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA ’14, page 1018–1028, USA, 2014. Society for Industrial and Applied Mathematics. 3, 12

    work page 2014

  21. [21]

    Optimal data-dependent hashing for approximate near neighbors

    Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. InProceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 793–801, New York, NY, USA, 2015. Association for Computing Machinery. 3, 12

    work page 2015

  22. [22]

    Optimal Data-Dependent Hashing for Approximate Near Neighbors

    Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. arXiv preprint arXiv:1501.01062, 2015. 12

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  23. [23]

    On the robustness of bucket brigade quantum RAM.New Journal of Physics, 17(12):123010, 2015

    Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. On the robustness of bucket brigade quantum RAM.New Journal of Physics, 17(12):123010, 2015. 5, 22, 23

    work page 2015

  24. [24]

    Bardin, Rami Barends, Ru- pak Biswas, Sergio Boixo, Fernando G

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Ru- pak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, ...

    work page 2019

  25. [25]

    Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé

    Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber (version 3.02) – submission to round 3 of the NIST post-quantum project.https://pq-crystals.org/ kyber/data/kyber-specification-round3-20210131.pdf, 2021. 35 49

    work page 2021

  26. [26]

    Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven

    Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity.Phys. Rev. X, 8:041015, Oct 2018. 5, 22

    work page 2018

  27. [27]

    Hasan Babu

    Hafiz Md. Hasan Babu. Cost-efficient design of a quantum multiplier–accumulator unit.Quantum Information Processing, 16(1):30, Dec 2016. 18

    work page 2016

  28. [28]

    CRYSTALS-Dilithium: Algorithm specifications and supporting documentation (version 3.1)

    Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: Algorithm specifications and supporting documentation (version 3.1). https://pq-crystals.org/dilithium/data/ dilithium-specification-round3-20210208.pdf, 2021. 4, 7, 35

    work page 2021

  29. [29]

    Johnson, Tanja Lange, and Tran Ngo

    Shi Bai, Maya-Iggy van Hoof, Floyd B. Johnson, Tanja Lange, and Tran Ngo. Concrete analysis of quantum lattice enumeration. In Jian Guo and Ron Steinfeld, editors,Advances in Cryptology – ASIACRYPT 2023, pages 131–166, Singapore, 2023. Springer Nature Singapore. 3, 4

    work page 2023

  30. [30]

    C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas. High-fidelity quantum logic gates using trapped-ion hyperfine qubits.Phys. Rev. Lett., 117:060504, Aug 2016. 6, 14

    work page 2016

  31. [31]

    Real-time decoding for fault-tolerant quantum computing: progress, challenges and outlook

    F Battistel, C Chamberland, K Johar, R W J Overwater, F Sebastiano, L Skoric, Y Ueno, and M Usman. Real-time decoding for fault-tolerant quantum computing: progress, challenges and outlook. Nano Futures, 7(3):032003, aug 2023. 6, 14

    work page 2023

  32. [32]

    Quantum lower bounds by polynomials.J

    Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials.J. ACM, 48(4):778–797, jul 2001. 20

    work page 2001

  33. [33]

    New directions in nearest neighbor searching with applications to lattice sieving

    Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. 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 ’16, page 10–24, USA, 2016. Society for Industrial and Applied Mathematics. 3, 4, 10, 12, 13, 29, 30, 35

    work page 2016

  34. [34]

    Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search.Cryptology ePrint Archive, 2015

    Anja Becker, Nicolas Gama, and Antoine Joux. Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search.Cryptology ePrint Archive, 2015. 3, 4

    work page 2015

  35. [35]

    Efficient (ideal) lattice sieving using cross-polytope LSH

    Anja Becker and Thijs Laarhoven. Efficient (ideal) lattice sieving using cross-polytope LSH. In David Pointcheval, Abderrahmane Nitaj, and Tajjeeddine Rachidi, editors,Progress in Cryptol- ogy – AFRICACRYPT 2016, pages 3–23, Cham, 2016. Springer International Publishing. 3

    work page 2016

  36. [36]

    Chari, Srikrishna Devabhaktuni, and John Preskill

    David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill. Efficient networks for quantum factoring.Phys. Rev. A, 54:1034–1063, Aug 1996. 17

    work page 1996

  37. [37]

    Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani

    Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing.SIAM Journal on Computing, 26(5):1510–1523, 1997. 20

    work page 1997

  38. [38]

    Bennett, David P

    Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed- state entanglement and quantum error correction.Phys. Rev. A, 54:3824–3851, Nov 1996. 13

    work page 1996

  39. [39]

    Bernstein and Tanja Lange

    Daniel J. Bernstein and Tanja Lange. Post-quantum cryptography.Nature, 549(7671):188–194, Sep 2017. 3

    work page 2017

  40. [40]

    Quantum lattice enumer- ation in limited depth

    Nina Bindel, Xavier Bonnetain, Marcel Tiepelt, and Fernando Virdia. Quantum lattice enumer- ation in limited depth. In Leonid Reyzin and Douglas Stebila, editors,Advances in Cryptology – CRYPTO 2024, pages 72–106, Cham, 2024. Springer Nature Switzerland. 3, 4

    work page 2024

  41. [41]

    H. Bombin. Topological order with a twist: Ising anyons from an Abelian model.Phys. Rev. Lett., 105:030403, Jul 2010. 14 50

    work page 2010

  42. [42]

    Interleaving: Modular architectures for fault-tolerant photonic quantum computing

    HectorBombin, IsaacHKim, DanielLitinski, NaomiNickerson, MihirPant, FernandoPastawski, Sam Roberts, and Terry Rudolph. Interleaving: Modular architectures for fault-tolerant photonic quantum computing.arXiv preprint arXiv:2103.08612, 2021. 5, 15

    work page arXiv 2021

  43. [43]

    Finding many col- lisions via reusable quantum walks

    Xavier Bonnetain, André Chailloux, André Schrottenloher, and Yixin Shen. Finding many col- lisions via reusable quantum walks. In Carmit Hazay and Martijn Stam, editors,Advances in Cryptology – EUROCRYPT 2023, pages 221–251, Cham, 2023. Springer Nature Switzerland. 4, 7, 47

    work page 2023

  44. [44]

    Quantum Security Analysis of AES

    Xavier Bonnetain, María Naya-Plasencia, and André Schrottenloher. Quantum Security Analysis of AES. IACR Transactions on Symmetric Cryptology, 2019(2):55–93, June 2019. 4

    work page 2019

  45. [45]

    Tightboundsonquantumsearching

    MichelBoyer, GillesBrassard, PeterHøyer, andAlainTapp. Tightboundsonquantumsearching. Fortschritte der Physik, 46(4-5):493–505, 1998. 5, 20, 21

    work page 1998

  46. [46]

    Boykin, T

    P.O. Boykin, T. Mor, M.Pulver, V. Roychowdhury, and F.Vatan. On universal and fault-tolerant quantum computing: a novel basis and a new constructive proof of universality for Shor’s basis. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 486–494, 1999. 9

    work page 1999

  47. [47]

    (Leveled) fully homomorphic en- cryption without bootstrapping.ACM Trans

    Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic en- cryption without bootstrapping.ACM Trans. Comput. Theory, 6(3), July 2014. 3

    work page 2014

  48. [48]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. 4, 20, 21, 47

    work page 2002

  49. [49]

    Magic-state distillation with low overhead.Phys

    Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead.Phys. Rev. A, 86:052329, Nov 2012. 16

    work page 2012

  50. [50]

    Universal quantum computation with ideal Clifford gates and noisy ancillas

    Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71:022316, Feb 2005. 5, 16

    work page 2005

  51. [51]

    Brown, Katharina Laubscher, Markus S

    Benjamin J. Brown, Katharina Laubscher, Markus S. Kesselring, and James R. Wootton. Poking holes and cutting corners to achieve Clifford gates with the surface code.Phys. Rev. X, 7:021029, May 2017. 14

    work page 2017

  52. [52]

    Quantifying Grover speed- ups beyond asymptotic analysis.Quantum, 7:1133, October 2023

    Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. Quantifying Grover speed- ups beyond asymptotic analysis.Quantum, 7:1133, October 2023. 5, 21, 47

    work page 2023

  53. [53]

    A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist.Phys. Rev. A, 54:1098–1105, Aug 1996. 13

    work page 1996

  54. [54]

    Campbell and Mark Howard

    Earl T. Campbell and Mark Howard. Unified framework for magic state distillation and multi- qubit gate synthesis with reduced resource cost.Phys. Rev. A, 95:022316, Feb 2017. 16

    work page 2017

  55. [55]

    Campbell and Mark Howard

    Earl T. Campbell and Mark Howard. Magic state parity-checker with pre-distilled components. Quantum, 2:56, March 2018. 16

    work page 2018

  56. [56]

    Lattice sieving via quantum random walks

    André Chailloux and Johanna Loyer. Lattice sieving via quantum random walks. In Mehdi Tibouchi and Huaxiong Wang, editors,Advances in Cryptology – ASIACRYPT 2021, pages 63– 91, Cham, 2021. Springer International Publishing. 4, 7, 47

    work page 2021

  57. [57]

    Campbell

    Christopher Chamberland and Earl T. Campbell. Universal quantum computing with twist-free and temporally encoded lattice surgery.PRX Quantum, 3:010331, Feb 2022. 5, 15 51

    work page 2022

  58. [58]

    Campbell, Con- nor T

    Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Con- nor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão. Building a fault-tolerant quantum computer using concate...

    work page 2022

  59. [59]

    Charikar

    Moses S. Charikar. Similarity estimation techniques from rounding algorithms. InProceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC ’02, page 380–388, New York, NY, USA, 2002. Association for Computing Machinery. 3, 4, 11

    work page 2002

  60. [60]

    Satzinger, Juan Atalaya, Alexander N

    Zijun Chen, Kevin J. Satzinger, Juan Atalaya, Alexander N. Korotkov, Andrew Dunsworth, Daniel Sank, Chris Quintana, Matt McEwen, Rami Barends, Paul V. Klimov, Sabrina Hong, Cody Jones, Andre Petukhov, Dvir Kafri, Sean Demura, Brian Burkett, Craig Gidney, Austin G. Fowler, Alexandru Paler, Harald Putterman, Igor Aleiner, Frank Arute, Kunal Arya, Ryan Bab- ...

    work page 2021

  61. [61]

    Clark, Holly N

    Craig R. Clark, Holly N. Tinkey, Brian C. Sawyer, Adam M. Meier, Karl A. Burkhardt, Christo- pher M. Seck, Christopher M. Shappert, Nicholas D. Guise, Curtis E. Volin, Spencer D. Fallek, Harley T. Hayden, Wade G. Rellergert, and Kenton R. Brown. High-fidelity Bell-state prepara- tion with 40Ca+ optical qubits. Phys. Rev. Lett., 127:130505, Sep 2021. 6, 14

    work page 2021

  62. [62]

    Andrew N. Cleland. An introduction to the surface code.SciPost Phys. Lect. Notes, page 49,

    work page

  63. [63]

    Springer Science & Business Media, 2013

    John Horton Conway and Neil James Alexander Sloane.Sphere packings, lattices and groups, volume 290. Springer Science & Business Media, 2013. 31

    work page 2013

  64. [64]

    A new quantum ripple-carry addition circuit

    Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit.arXiv preprint quant-ph/0410184, 2004. 17

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  65. [65]

    Nickerson

    Nicolas Delfosse and Naomi H. Nickerson. Almost-linear time decoding algorithm for topological codes. Quantum, 5:595, December 2021. 5, 15

    work page 2021

  66. [66]

    Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel.Phys

    Nicolas Delfosse and Gilles Zémor. Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel.Phys. Rev. Res., 2:033042, Jul 2020. 5, 15

    work page 2020

  67. [67]

    Topological quantum memory

    Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 09 2002. 5, 14, 15

    work page 2002

  68. [68]

    Fault-tolerant resource estimation of quantum random-access memories.IEEE Transactions on Quantum Engineering, 1:1–13, 2020

    Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. Fault-tolerant resource estimation of quantum random-access memories.IEEE Transactions on Quantum Engineering, 1:1–13, 2020. 5, 22 52

    work page 2020

  69. [69]

    DiVincenzo

    David P. DiVincenzo. Two-bit gates are universal for quantum computation. Phys. Rev. A, 51:1015–1022, Feb 1995. 9

    work page 1995

  70. [70]

    Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, and Miklos Santha

    João F. Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, and Miklos Santha. Quantum algorithm for stochastic optimal stopping problems with applications in finance. In François Le Gall and Tomoyuki Morimae, editors,17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), volume 232 ofLeibniz Interna- ti...

    work page 2022

  71. [71]

    Draper, S.A

    T.G. Draper, S.A. Kutin, E.M. Rains, and K.M. Svore. A logarithmic-depth quantum carry- lookahead adder.Quantum Information and Computation, 6(4&5):351–369, 07 2006. 17

    work page 2006

  72. [72]

    Addition on a Quantum Computer

    Thomas G Draper. Addition on a quantum computer.arXiv preprint quant-ph/0008033, 2000. 17

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  73. [73]

    Reducing the quantum-computing overhead with complex gate distillation.Phys

    Guillaume Duclos-Cianci and David Poulin. Reducing the quantum-computing overhead with complex gate distillation.Phys. Rev. A, 91:042315, Apr 2015. 16

    work page 2015

  74. [74]

    Guillaume Duclos-Cianci and Krysta M. Svore. Distillation of nonstabilizer states for universal quantum computation.Phys. Rev. A, 88:042325, Oct 2013. 16

    work page 2013

  75. [75]

    Restrictions on transversal encoded quantum gate sets.Phys

    Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets.Phys. Rev. Lett., 102:110502, Mar 2009. 16

    work page 2009

  76. [76]

    Paths, trees, and flowers.Canadian Journal of Mathematics, 17:449–467, 1965

    Jack Edmonds. Paths, trees, and flowers.Canadian Journal of Mathematics, 17:449–467, 1965. 5, 15

    work page 1965

  77. [77]

    New lower bounds on kissing numbers and spherical codes in high dimensions.arXiv preprint arXiv:2111.01255, 2021

    Irene Gil Fernández, Jaehoon Kim, Hong Liu, and Oleg Pikhurko. New lower bounds on kissing numbers and spherical codes in high dimensions.arXiv preprint arXiv:2111.01255, 2021. 31

    work page arXiv 2021

  78. [78]

    Fincke and M

    U. Fincke and M. Pohst. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis.Mathematics of Computation, 44(170):463–471, 1985. 3, 24

    work page 1985

  79. [79]

    Fowler, Simon J

    Austin G. Fowler, Simon J. Devitt, and Cody Jones. Surface code implementation of block code state distillation. Scientific Reports, 3(1):1939, Jun 2013. 16

    work page 1939

  80. [80]

    Low overhead quantum computation using lattice surgery,

    Austin G Fowler and Craig Gidney. Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709, 2018. 5, 14, 15, 16

    work page arXiv 2018

Showing first 80 references.