⚛️ quantum physics

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

This paper demonstrates that under current and near-future technological assumptions, quantum sieving algorithms aided by Grover's search offer no practical speedup over classical computing for solving the Shortest Vector Problem in dimensions relevant to post-quantum cryptography, as they would require prohibitively large resources and time.

Original authors: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Quantum Sieve: A Reality Check on Breaking Future Codes

Imagine you are trying to find the single shortest thread in a giant, tangled ball of yarn that is the size of a galaxy. This is essentially what the Shortest Vector Problem (SVP) is. In the world of cryptography, this "yarn ball" is a mathematical structure called a lattice, and finding that shortest thread is the key to breaking the most secure digital locks we have today.

For decades, scientists have been asking: "Can a quantum computer find this thread much faster than a regular computer?"

This paper, written by a team of researchers, says: "Probably not, at least not anytime soon."

Here is the breakdown of their findings using simple analogies.

1. The Setup: The Quantum Race

To break modern encryption (the kind that will protect our data after quantum computers arrive), hackers would need to solve the SVP on a lattice with a dimension of about 400. Think of this as a 400-dimensional maze.

Researchers have known for a while that Grover's Algorithm (a famous quantum search trick) can theoretically speed up this search. It's like having a magic flashlight that lets you check two rooms at once instead of one. Theoretically, this should make the search much faster.

However, this paper asks a very practical question: "What is the actual cost of building that magic flashlight?"

2. The Hidden Costs: The "Magic" isn't Free

The authors realized that previous studies were like estimating the cost of a road trip by only counting the price of gas, ignoring the car, the driver, the tolls, and the fact that the car might break down.

They decided to calculate the full bill, including:

The Car (Hardware): Building a quantum computer requires millions of tiny parts.
The Driver (Error Correction): Quantum bits (qubits) are incredibly fragile, like glass marbles on a bumpy road. To keep them from shattering, you need to wrap every single "useful" marble in a protective bubble made of thousands of other marbles. This is called Quantum Error Correction.
The Memory (QRAM): To search the yarn ball, the computer needs to remember where every thread is. The paper calculates the cost of building a massive "Quantum Library" (QRAM) that can be accessed instantly.
The Fuel (Time): How long does the engine take to run?

3. The Big Reveal: The Numbers are Shocking

When the authors crunched the numbers for a lattice of dimension 400 (the size needed to break current "post-quantum" security standards), the results were humbling:

The Qubit Count: To run this algorithm, you would need roughly 10 trillion (10¹³) physical qubits.
- Analogy: If every atom in a human body is a qubit, you would need the atoms of billions of humans stacked together to build this computer.
The Time: Even with this massive machine, it would take roughly 10³¹ years to solve the problem.
- Analogy: The universe is only about 13.8 billion years old (10¹⁰). This computer would take a time span 1,000,000,000,000,000,000,000,000,000,000 times longer than the age of the universe.

4. The "Classical" Surprise

Here is the twist: The authors also calculated how long a regular, single-core classical computer (like the one in your laptop, but running at a very fast speed) would take to do the same job.

It would take roughly the same amount of time: 10³¹ years.

This means that for the specific problem of breaking these lattice codes, the "quantum speedup" (the magic flashlight) is so expensive to build and run that it offers no real advantage over a regular computer. The overhead of keeping the quantum computer stable eats up all the speed gains.

5. Why is it so hard? (The "QRAM" Bottleneck)

The biggest culprit for this massive cost is the QRAM (Quantum Random Access Memory).

Analogy: Imagine you are looking for a needle in a haystack. A quantum computer wants to look at the whole haystack at once. But to do that, it needs a library card for every single piece of hay. Building a library card system for a haystack the size of a galaxy requires more resources than the haystack itself!
The paper shows that the memory required to hold the data for the search is so huge that it swallows up all the benefits of the quantum speedup.

6. The Conclusion: Don't Panic (Yet)

The authors conclude that:

Current Standards are Safe: The lattice-based cryptography being standardized by NIST (like Kyber and Dilithium) is safe from quantum attacks for the foreseeable future.
No Magic Bullet: Simply adding a quantum computer to the mix doesn't automatically break these codes. The hardware requirements are currently impossible.
Future Hope? For quantum computers to actually break these codes, we would need massive breakthroughs in two areas:
- Hardware: Building quantum computers that don't need millions of protective "bubbles" for every qubit.
- Memory: Finding a way to build quantum memory (QRAM) that doesn't require a galaxy-sized amount of space.

Summary

Think of this paper as a reality check for the "Quantum Apocalypse." While quantum computers are amazing and will eventually solve many problems, they are not a magic wand that instantly breaks all encryption.

To break the specific "lattice" locks used for future security, we would need to build a machine so large and complex that it would take longer to build and run than the entire history of the universe. Until we make a giant leap in how we build quantum computers, our digital secrets remain safe.

1. Problem Statement

The security of post-quantum cryptography (PQC), particularly lattice-based schemes like those standardized by NIST (e.g., Kyber, Dilithium), relies on the computational hardness of the Shortest Vector Problem (SVP). SVP asks for the shortest non-zero vector in an integer lattice. While classical algorithms (enumeration and sieving) are known to be exponential in the lattice dimension $D$ , it is widely believed that quantum computers could offer a speedup, primarily through Grover's search algorithm, which provides a quadratic speedup ( $O(\sqrt{N})$ vs $O(N)$ ) for unstructured search.

Previous theoretical analyses suggested that quantum sieving algorithms could solve SVP with a complexity of roughly $2^{0.267D}$ (using Grover on sieves with Locality Sensitive Hashing/Filtering), significantly lower than the best classical complexities ( $2^{0.292D}$ ). However, these asymptotic analyses often ignored critical overheads:

The cost of Quantum Random Access Memory (QRAM).
The overhead of Quantum Error Correction (QEC).
The cost of fixed-point arithmetic on quantum hardware.
Non-asymptotic constraints (e.g., unknown number of solutions).

The paper addresses the gap between asymptotic theory and practical feasibility by performing a rigorous resource estimation for solving SVP in dimensions relevant to current cryptographic standards (specifically $D=400$ ).

2. Methodology

The authors conducted a comprehensive resource estimation analysis for eight variations of sieving algorithms:

NVSieve (Nguyen-Vidick) and GaussSieve (Micciancio-Voulgaris).
Variants enhanced with Locality Sensitive Hashing (LSH): Angular LSH and Spherical LSH.
Variants enhanced with Locality Sensitive Filtering (LSF): Spherical LSF.

The analysis integrated the following components:

Quantum Arithmetic: Used state-of-the-art circuits for fixed-point arithmetic (addition, comparison, multiplication) with 32-bit precision ( $\kappa=32$ ). They utilized Gidney's out-of-place adder (lowest Toffoli count) and a schoolbook-style multiplier.
Grover's Search: Implemented non-asymptotic Grover search (using exponential search variants) because the number of solutions in sieving steps is not known a priori.
QRAM: Modeled the cost of bucket-brigade QRAM (Arunachalam et al. design) to access classical databases. This was a major focus, as QRAM requires a number of logical qubits roughly proportional to the database size.
Error Correction: Assumed a surface code architecture with a physical error rate of $p_{phy} = 10^{-5}$ . They employed multi-level magic state distillation (up to 3 levels) to achieve logical error rates below $10^{-40}$ , necessary for the massive number of Toffoli gates required.
Architectures: Evaluated two physical architectures:
- Baseline: 2D grid with nearest-neighbor interactions (e.g., Google Sycamore style).
- Active-Volume: A more efficient architecture (Litinski/Nickerson) using non-local connections and "workspace" modules to reduce idle qubit costs.
Classical Baseline: Compared quantum execution times against a single-core classical computer (6 GHz) performing sequential searches and hashing.

3. Key Contributions

First Comprehensive Resource Estimation: Unlike previous works that focused on asymptotic gate counts or ignored QRAM/QEC, this paper provides a full-stack resource estimate including physical qubits, time, and error correction overheads.
QRAM Dominance: The authors demonstrate that the cost of QRAM is the primary bottleneck. In sieving algorithms, the need to access exponentially large lists of vectors via QRAM consumes the vast majority of physical qubits.
Non-Asymptotic Analysis: They accounted for the "unknown number of solutions" problem in Grover's search, which increases the query complexity compared to the idealized $O(\sqrt{N/M})$ case.
Hardware Realism: By incorporating realistic parameters for reaction times (1 $\mu$ s), code cycles (100 ns), and multi-level magic state distillation, the study moves beyond theoretical "toy" models.

4. Key Results

The results for the critical dimension $D=400$ (required to break NIST Level 1 security standards) are stark:

Physical Qubits: Even under optimistic assumptions, the best quantum sieving algorithm (GaussSieve with Spherical LSF) requires approximately $10^{13}$ physical qubits.
- Breakdown: The majority of these qubits are dedicated to the QRAM infrastructure required to store the candidate vector lists.
Execution Time: The estimated time to solve SVP at $D=400$ $D = 400$ is approximately $10^{31}$ years.
- This duration is vastly longer than the age of the universe ( $\approx 1.38 \times 10^{10}$ years).
Comparison to Classical: A single-core classical computer (6 GHz) performing the same task (sequential search) would also take roughly $10^{31}$ years.
- Conclusion: There is no practical quantum speedup at cryptographic dimensions. The quadratic speedup from Grover's algorithm is completely negated by the overheads of QRAM, error correction, and arithmetic.
Scaling: A quantum advantage (where quantum time < classical time) only appears at dimensions far beyond $D=1000$ , where the quantum speedup factor reaches $\approx 10^5$ , but the absolute time remains astronomical and the qubit requirements remain infeasible.
Depth Constraints: When constrained by NIST's proposed depth limits (e.g., $2^{40}$ gates), the number of physical qubits drops, but the execution time increases further, reinforcing the lack of advantage.

5. Significance and Implications

Security of Lattice Cryptography: The paper provides strong evidence that lattice-based cryptography (specifically SVP-based schemes) remains secure against quantum attacks using current and near-future quantum technologies. The "quantum threat" to these standards is likely negligible compared to classical threats.
QRAM Bottleneck: The study highlights that unless there is a breakthrough in QRAM architecture (making it significantly cheaper in terms of qubits and depth), quantum algorithms relying on large database lookups (like sieving) will not be practical.
Resource Estimation Standards: The paper sets a new standard for resource estimation in quantum cryptanalysis, moving away from simple gate counts to full-stack physical resource modeling including error correction and memory costs.
Future Directions: The authors note that while their analysis is pessimistic regarding current protocols, significant theoretical breakthroughs in quantum random walks or new hardware architectures could change the landscape. However, such breakthroughs would need to be substantial to overcome the $10^{13}$ qubit barrier.

In summary, the paper concludes that Grover's search offers little to no practical advantage for solving SVP in cryptographically relevant dimensions due to the prohibitive costs of error correction and QRAM, suggesting that lattice-based cryptography is robust against foreseeable quantum attacks.