⚛️ quantum physics

A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles

This paper proposes a scalable, QAOA-based heuristic approach with fixed angles and a pre-training scheme to solve the Closest Vector Problem, demonstrating a potential fifth-order quantum speed-up for specific lattice structures and suggesting a need to re-evaluate the dimensions required for quantum-secure cryptosystems.

Original authors: Ben Priestley, Petros Wallden

Published 2026-03-09

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben Priestley, Petros Wallden

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 Big Picture: Cracking the Unbreakable Lock

Imagine the security of your bank account, your emails, and the internet relies on a giant, complex lock. This lock is based on a mathematical puzzle called Integer Factorization (breaking a big number down into its prime building blocks). Currently, even the world's fastest supercomputers would take billions of years to crack these locks.

However, scientists have been worried about Quantum Computers. These are futuristic machines that don't just count faster; they can look at many possibilities at once. If they get good enough, they could break these locks, rendering our current internet security useless.

This paper asks a specific question: Can a new type of quantum algorithm, called QAOA, help break these locks faster than we thought?

The Analogy: The "Prime Lattice" as a Giant Maze

To understand the problem, imagine a giant, multi-dimensional maze.

The Goal: You are standing at a specific point (a target) and you need to find the closest "floor tile" (a lattice point) to you. This is called the Closest Vector Problem (CVP).
The Difficulty: In a normal maze, you can just look around. But in this mathematical maze, the dimensions are so high (thousands of directions) that looking around is impossible. The "floor tiles" are packed so tightly that finding the right one is like finding a specific grain of sand on a beach, but the beach is infinite and shifting.

Classically, we have a "best guess" method (Babai's algorithm) that gets us close to the right tile, but it's often a few steps off. To get the exact right tile, we have to check every possible step around that guess.

The Quantum Solution: The "Super-Searcher"

The authors are testing a tool called QAOA (Quantum Approximate Optimization Algorithm).

The Old Way (Classical): Imagine you are trying to find the best route through a maze. You have to try one path, see if it's good, then try another. If you have to check 1,000 paths, you do it 1,000 times.
The Quantum Way: A quantum computer is like a "Super-Searcher" that can walk down all 1,000 paths simultaneously. It doesn't just check them one by one; it checks them all at once and tells you which one is the best.

The Problem: Tuning the Radio

Here is the catch. The Quantum Super-Searcher (QAOA) needs to be "tuned" to work correctly. It has knobs (called angles) that control how it searches.

The Old Approach: For every new maze (every new number to factor), you have to spend hours or days tuning the knobs to find the perfect setting. This is slow and defeats the purpose of being fast.
The Paper's Innovation: The authors realized that these mazes are all built from the same "blueprint" (they are all Prime Lattices). So, instead of tuning the radio for every single station, they decided to pre-train the radio.

The "Pre-Training" Analogy:
Imagine you are a chef trying to cook the perfect soup.

Without Pre-training: You taste the soup, adjust the salt, taste again, adjust again, for every single pot you make.
With Pre-training: You cook 100 small pots of soup, figure out the perfect recipe (the fixed angles), and write it down. Now, when you make a giant pot for a banquet, you just use that recipe immediately. You don't need to taste and adjust; you just cook.

The authors developed a method to "taste" many small problems, find the perfect "recipe" (fixed angles), and then apply that recipe to huge, difficult problems instantly.

The Results: A Speed Boost (But Not a Magic Wand)

The authors ran simulations to see how well this "pre-trained" quantum search worked compared to the best classical computers.

The Good News: They found that for certain types of these mathematical mazes, the quantum method is significantly faster than the classical method. Specifically, they found a speed-up that is better than the standard "square root" speed-up (Grover's algorithm) usually expected from quantum computers. It was almost like a "fifth-order" advantage.
The Bad News (The Reality Check): While the quantum method is faster, it is not fast enough to break current encryption yet.
- The authors point out that the "search space" they used in their experiment was a bit too small (like searching a small room instead of the whole city).
- If you expand the search to the full size needed to break real-world encryption, the difficulty grows exponentially. Even with the quantum speed-up, it might still take too long.

The "Prime" Twist

The paper focuses on a very specific, "constrained" type of maze (the Prime Lattice). It's like testing a race car on a perfectly smooth, straight track. The car goes incredibly fast. But real-world encryption might be like driving on a bumpy, winding mountain road. The authors admit their results are a "best-case scenario" and that generalizing this to all types of encryption is still an open question.

Conclusion: What Does This Mean for Us?

1. Don't Panic Yet: This paper does not say "RSA encryption is broken today." The quantum computers needed to run this at the scale required for real-world hacking don't exist yet, and the math suggests we might still be safe for a while.

2. A Warning Sign: However, it is a warning. It shows that quantum algorithms are getting smarter. The "pre-training" trick they discovered is a powerful new tool. It suggests that in the future, we might need to make our encryption locks even bigger and more complex to stay safe.

3. The Takeaway: The authors have shown that by "teaching" the quantum computer a general rule (fixed angles) rather than making it learn from scratch every time, we can make it much more efficient. This is a crucial step toward understanding just how much of a threat quantum computers will eventually pose to our digital security.

In short: They taught a quantum robot a trick to find needles in haystacks faster than before. It's not fast enough to steal your bank password today, but it's fast enough to make the bank nervous about tomorrow.

1. Problem Statement

The paper addresses the Closest Vector Problem (CVP) within the context of integer factorization, specifically focusing on lattice sieving methods proposed by Schnorr.

Context: Integer factorization (e.g., RSA) relies on the difficulty of finding "smooth relation pairs" (sr-pairs). Schnorr's method reduces this to finding a CVP solution on a specific "prime lattice."
The Challenge: Recent claims (e.g., Yan et al. [1]) suggested that Quantum Approximate Optimization Algorithm (QAOA) could solve this CVP with sublinear resources, potentially breaking RSA. However, these claims faced skepticism regarding:
1. Scalability: Whether the algorithm scales to larger lattice dimensions.
2. Parameter Optimization: The computational cost of finding optimal QAOA angles for every new instance.
3. Search Space: Whether the proposed search space ( $O(n)$ qubits) is sufficient to find the true closest vector (critics argue $O(n \log n)$ is needed).
Goal: The authors aim to evaluate the practical scalability and time complexity of using QAOA with fixed angles (pre-trained parameters) to refine classical CVP approximations, independent of the ultimate claim of breaking RSA.

2. Methodology

The authors propose a framework combining classical lattice reduction with a variational quantum approach using Fixed-Angle QAOA.

A. Problem Formulation

Prime Lattice Construction: They construct a lattice $L(B_{n,c})$ based on the logarithms of prime numbers, where the target vector $t$ corresponds to $\log N$ .
Classical Pre-processing:
1. Apply LLL-reduction to the basis.
2. Use Babai's Nearest Plane Algorithm to find an approximate solution $b_{op}$ .
Quantum Refinement (The Core):
- Instead of searching the entire lattice, the QAOA searches the unit neighborhood of $b_{op}$ .
- The problem is mapped to a Minimum Eigenstate problem (QUBO) where the cost function is the Euclidean distance between a candidate vector $v_{new}$ and the target $t$ .
- The search space size is $2^n$ (linear in lattice dimension $n$ ), encoded into $n$ qubits.

B. Fixed-Angle QAOA & Pre-training

To address the scalability bottleneck of optimizing QAOA parameters ( $\gamma, \beta$ ) for every instance, the authors introduce a pre-training scheme:

Training Distribution: Generate random CVP instances of varying sizes.
Optimization: For a set of instances, optimize the QAOA angles to maximize the probability of finding a better solution than $b_{op}$ .
Validation & Generalization: Evaluate these angle sets on a separate validation distribution. The goal is to find a set of angles that generalizes well to larger lattice dimensions (minimizing the decay of success probability as $n$ increases).
Fixed Angles: Once a robust set of angles is found, it is "fixed" and applied to all subsequent instances without further optimization, effectively removing the outer optimization loop.

3. Key Contributions

Robust Pre-training Scheme: A novel algorithm (Algorithm 1) that trains QAOA angles on small/medium instances to find a parameter set that scales to larger problems, avoiding overfitting to specific small instances.
Time-Complexity Analysis: A rigorous empirical analysis of the scaling behavior of QAOA for CVP refinement. They move beyond theoretical bounds to provide numerical evidence of performance.
Fixed-Angle Application: One of the first applications of fixed-angle QAOA to a cryptographically significant problem (CVP), demonstrating that pre-training can drastically reduce computational overhead.
Quantum Advantage Demonstration: They demonstrate a quantum speed-up that exceeds the standard Grover-type quadratic speed-up ( $O(\sqrt{N})$ ) for specific lattice structures.

4. Results

The authors conducted extensive numerical simulations for lattice dimensions $n$ up to 18 (corresponding to integers $N$ with bit-lengths up to 128) and QAOA depths $p$ from 1 to 10.

Scaling of Success Probability:
- The probability $q(n)$ of refining the solution decays exponentially with lattice dimension: $q(n) \approx 1/2^{\alpha n}$ .
- Classical Brute Force: $\alpha \approx 1$ (implied).
- Grover's Algorithm: $\alpha = 0.5$ (Quadratic speed-up).
- Fixed-Angle QAOA ( $p=10$ ): Achieved $\alpha \approx 0.225$ .
- Implication: This represents a fifth-order advantage ( $O(2^{0.225n})$ ) compared to brute force, significantly outperforming Grover's algorithm.
Convergence:
- The pre-trained angles converged stably as the bit-length of the training instances increased.
- Angles found on small instances (e.g., bit-length < 20) failed to generalize, confirming the necessity of the authors' specific pre-training strategy over simple single-instance training.
Refinement Quality:
- While the probability of finding a refinement decreases with dimension, the quality of the refinement (how much closer the vector gets to the target) also decays sub-exponentially.
- The authors note that for the specific "prime lattice" structure used, the method shows promise, though they acknowledge that for general CVPs or larger search spaces ( $O(n \log n)$ ), the advantage might diminish.

5. Significance and Limitations

Significance

Re-evaluating Quantum Security: The results suggest that variational quantum algorithms with fixed angles could pose a threat to lattice-based cryptosystems faster than previously thought, potentially requiring larger lattice dimensions for security than currently standard.
Practicality: By eliminating the need for per-instance parameter optimization, the approach becomes computationally feasible for near-term (NISQ) devices, provided the angles generalize.
Beyond Grover: The paper provides evidence that QAOA can achieve super-quadratic speed-ups for structured problems, challenging the notion that Grover's limit is the ceiling for quantum search in this context.

Limitations & Scope

Restricted Search Space: The study uses a search space of $O(n)$ qubits (linear), whereas theoretical requirements for guaranteed CVP solutions often suggest $O(n \log n)$ . The authors acknowledge this may limit the solution quality for general lattices.
Specific Lattice Structure: The results are specific to the "prime lattice" used in Schnorr's factorization method. It is unclear if these fixed angles generalize to arbitrary CVP instances or other lattice-based cryptosystems.
Noise: The simulations are noiseless. The authors note that noise could confound the pre-training process, though they argue shallow-depth circuits might still be viable on early fault-tolerant hardware.
Factoring Claims: The paper does not claim to break RSA. It isolates the CVP subroutine to analyze its efficiency. The authors remain skeptical of the "sublinear factoring" claims due to the exponential decay of smooth numbers in large dimensions (Appendix B).

Conclusion

The paper demonstrates that fixed-angle QAOA, when supported by a robust pre-training scheme, offers a practically scalable approach to refining CVP solutions. It achieves a significant quantum speed-up (approaching $O(2^{0.1n})$ for higher depths) that surpasses Grover's algorithm. While the method relies on specific lattice structures and search space constraints, it highlights a potential vulnerability in lattice-based cryptography and motivates a re-evaluation of security parameters for post-quantum systems.