No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore

This paper presents efficient classical algorithms for the $\mathrm{SIS}^\infty$ and Constrained Integer Solution problems previously solved by an efficient quantum algorithm, thereby demonstrating that no exponential quantum speedup exists for these tasks.

The Gist

Here is an explanation of the paper "No exponential quantum speedup for SIS∞ anymore," translated into simple language with creative analogies.

The Big Picture: The Quantum "Magic Trick" That Wasn't

Imagine a group of magicians (quantum computer researchers) who recently discovered a new trick. They claimed they could solve a very difficult puzzle called SIS∞ (Short Integer Solution) much faster than any regular computer could.

The puzzle is like this: You have a giant, messy grid of numbers (a matrix). Your goal is to find a specific combination of these numbers that adds up to zero, but with a catch: the numbers you pick must be "small" (they can't be huge).

In 2021, researchers Chen, Liu, and Zhandry (let's call them the "Quantum Trio") said, "We have a quantum algorithm that solves this puzzle in seconds, while a classical computer would take billions of years!" This was exciting because it suggested quantum computers might break certain future encryption codes.

The Plot Twist:
The authors of this new paper (Robin Kothari, Ryan O'Donnell, and Kewen Wu) looked at the Quantum Trio's puzzle and said, "Wait a minute. We don't need a quantum computer for this. We just need a really clever way of thinking."

They built a classical algorithm (a program for a regular laptop) that solves the same puzzle just as fast, or even faster, than the quantum one. They effectively "de-quantized" the problem, proving that for this specific type of puzzle, quantum computers don't have a magical super-speed advantage after all.

---

The Core Concept: The "Halving Trick"

To understand how they did it, let's use an analogy involving weights.

Imagine you are trying to balance a scale. You have a bunch of heavy weights (numbers), and you need to find a group of them that balances perfectly to zero. But there's a rule: you can only use weights that are lighter than a certain limit.

The Quantum Trio's Approach:
They had a fancy quantum trick that could find a solution, but it only worked well if the weights were allowed to be very heavy (close to the limit). If you wanted to find a solution with lighter weights, their method got slow and clunky.

The Authors' Approach (The "Halving Trick"):
The authors realized they could use a simple, logical strategy they call the "Halving Trick."

1. The First Cut: Imagine you have a huge pile of weights. You find any combination that balances to zero, even if the weights are heavy.
2. The Magic Split: Once you have that heavy balance, you can mathematically "split" it. You take that heavy solution and break it down into two smaller solutions.
3. Repeat: You take those smaller solutions and split them again.

It's like taking a giant, heavy cake and cutting it in half, then cutting those halves in half again. With every cut, the "weight" (or size) of the numbers you are dealing with gets smaller and smaller.

The Quantum Trio had to do this splitting process many times, and their quantum method got messy when the numbers got too small. The authors, however, found a way to do this splitting so efficiently that they could shrink the numbers down to be very small very quickly, using a regular computer.

The "Reduction" Analogy: From a Forest to a Single Tree

The paper uses a technique called reduction. Think of the problem as a dense, dark forest where you are looking for a specific rare flower (the solution).

• The Quantum Trio said: "We have a drone (quantum computer) that can fly over the forest and spot the flower instantly, but only if the forest isn't too dense."
• The Authors said: "We don't need a drone. We can just build a ladder."

Their "ladder" works like this:

1. They look at a small section of the forest and find a path.
2. They use that path to "project" the rest of the forest onto a smaller, simpler map.
3. They repeat this, shrinking the forest down until it's just a single tree.
4. Finding the flower in a single tree is easy.

By shrinking the problem down step-by-step, they turned a "hard" problem into an "easy" one without needing any quantum magic.

Why Does This Matter?

1. The "Magic" is Gone:
For a while, people thought this specific puzzle (SIS∞) was a "killer app" for quantum computers—a problem where they would leave classical computers in the dust. This paper shows that for this puzzle, the dust is just regular dust. Classical computers can keep up.

2. Encryption Safety (For Now):
Many future encryption systems (like the ones being standardized by NIST) rely on the idea that these puzzles are hard to solve.

• Good News: The authors' algorithm only works when the puzzle is "big" (has a lot of numbers). Most real-world encryption uses "small" puzzles. So, current encryption is still safe.
• Bad News (for the Quantum Hype): It shows that the specific "quantum advantage" claimed for this problem was an illusion. It forces us to look harder for problems where quantum computers actually win.

3. The "Halving" is a New Tool:
The "Halving Trick" and the "Reducible Vector" concepts the authors invented are like new tools in a mechanic's toolbox. Even if they don't break this specific encryption, these tools might help solve other hard math problems in the future.

Summary in One Sentence

The paper proves that a puzzle thought to require a super-powerful quantum computer to solve can actually be solved just as fast by a regular computer using a clever "cut-the-cake-in-half" strategy, meaning there is no exponential speedup for this specific problem after all.

Technical Summary

Here is a detailed technical summary of the paper "No exponential quantum speedup for SIS∞ anymore" by Robin Kothari, Ryan O'Donnell, and Kewen Wu.

1. Problem Definition and Context

The paper addresses the Short Integer Solution (SIS) problem in the $\ell_\infty$ norm, denoted as SIS$\infty$, and its generalization, the Constrained Integer Solution (CIS) problem.

• SIS$\infty$ Problem: Given a matrix $H \in \mathbb{F}_q^{n \times m}$ and a bound $s$, find a non-zero vector $x \in \mathbb{F}_q^m$ such that $Hx = 0$ and $\|x\|_\infty \le s$.
• CIS Problem: A generalization where the coefficients of $x$ must belong to a specific allowed set $A \subseteq \mathbb{F}_q$ (rather than just an interval).
• Context: In 2021, Chen, Liu, and Zhandry (CLZ) presented an efficient quantum algorithm for average-case SIS$\infty$ and CIS in parameter regimes where no efficient classical algorithm was known. Their algorithm utilized a novel quantum primitive based on Regev's reduction, distinct from standard quantum speedups like Shor's algorithm. This suggested a potential exponential quantum advantage for these problems, which are foundational to post-quantum cryptography (e.g., Dilithium, Wave).

2. Methodology

The authors present a series of deterministic classical algorithms that solve these problems efficiently, effectively "dequantizing" the CLZ results. Their approach relies on three main technical pillars:

A. The "Halving Trick" (Section 3)

Inspired by prior work (Imran & Ivanyos), the authors refine a technique to reduce the weight (norm) of a solution.

• Mechanism: If an algorithm can find a non-trivial zero-sum with coefficients in a range $\pm h$, the authors show how to construct an algorithm that finds a zero-sum with coefficients in $\pm \lfloor h/2 \rfloor$.
• Improvement: They generalize this to remove a dependence on the field size $q$ found in previous classical attempts. This allows them to handle cases where $q$ is exponentially large in $n$, a regime where previous classical methods failed.
• Application: By iterating this trick, they can reduce the solution norm from $\lfloor q/2 \rfloor$ down to $\lfloor q/(2k) \rfloor$ with polynomial overhead.

B. Dimension Reduction and Sparsity (Sections 2 & 3)

The authors employ dimension reduction strategies to find sparse linear dependencies.

• Technique: Instead of finding a dependency in the full space, they project vectors onto subspaces orthogonal to previously found solutions.
• Result: This reduces the number of vectors required to guarantee a solution. For example, for $\mathbb{F}_3$-Subset-Sum, they improve the required number of vectors $m$ from $O(n^2)$ to roughly $n^2/3$.

C. Generalized Reducible Vectors and Tree Constructions (Section 4)

To overcome the limitations of the simple "halving" approach (which incurs a quadratic cost per reduction step), the authors develop a more sophisticated framework using reducible vectors.

• Reducible Vector: A vector $u$ is $(H \to H')$-reducible if $u$ is a non-trivial sum, and for any $c \in H$, the vector $c \cdot u$ can be expressed as a sum with coefficients in $H'$.
• Tree Construction: They construct a "forest" of trees where nodes represent partial zero-sums. By applying a permutation-based cancellation (similar to a determinant expansion) across the branches of the tree, they can combine solutions to achieve a target coefficient set $H'$ in a single "shot" rather than iterating.
• Arithmetic Combinatorics: They utilize results on arithmetic progressions (APs) and zero-sum theory (e.g., Szemerédi's theorem variants) to ensure that arbitrary sets $A$ (in the CIS problem) contain the necessary structures (like APs or symmetric pairs) to apply these reductions.

3. Key Contributions and Results

The paper provides deterministic classical algorithms that outperform the CLZ quantum algorithms in terms of sample complexity ($m$) and runtime dependence on parameters ($n, q$).

A. $\mathbb{F}_3$-Subset-Sum

• Previous: CLZ quantum algorithm required $m \ge Cn^2$ (average case).
• New Result: Deterministic classical algorithm solves worst-case instances with $m \ge n^2/3 + O(n \log n)$.
• Significance: This is a strict improvement over both the quantum bound and previous classical bounds.

B. General SIS$\infty$

• Previous: CLZ quantum algorithm required $m \ge C q^4 \log q \cdot n^k$ for a solution with norm $s \approx q/2^k$.
• New Result: Deterministic classical algorithm solves worst-case instances with $m \ge C n^k$ for the same $s$.
• Significance: The dependence on $q$ is eliminated entirely (the algorithm is polylogarithmic in $q$), and the dependence on $n$ is significantly improved. This holds even when $q$ is exponentially large in $n$.

C. Constrained Integer Solution (CIS)

• Previous: CLZ quantum algorithm required $m \ge C q^4 \log q \cdot n^k$ for a set $A$ of size $q-k+1$.
• New Result: Deterministic classical algorithm requires $m \ge C \log q \cdot n^k$ (or $n^{k-1}$ in some regimes).
• Significance: The classical algorithm matches or improves the quantum bound in all parameter regimes, removing the exponential advantage.

D. Runtime Complexity

The classical algorithms run in polynomial time (specifically $\text{poly}(m, \log q)$ or $\text{poly}(m, q)$ depending on the specific variant), whereas the CLZ quantum algorithm was $\text{poly}(m, q)$. Crucially, for large $q$, the classical runtime is often faster because it depends on $\log q$ rather than $q$.

4. Significance and Implications

1. Elimination of Exponential Quantum Speedup: The paper conclusively demonstrates that the specific algorithmic primitive used by Chen, Liu, and Zhandry does not yield an exponential quantum speedup for SIS$\infty$ or CIS. The problems can be solved efficiently by classical computers in the parameter ranges previously thought to be quantum-advantageous.
2. Cryptographic Impact:
   • Wave Signature Scheme: The security of the Wave signature scheme relies on the hardness of average-case CIS over $\mathbb{F}_3$. The authors show that for parameters where $m \approx n^2/3$, the problem becomes easy classically. However, for the standard cryptographic parameters where $m \approx 2n$, the problem remains hard (as $m < n^2/3$).
   • Dilithium: Similarly, the paper clarifies the boundary between polynomial-time solvable and exponential-time regimes for SIS$\infty$ variants used in Dilithium.
3. Theoretical Boundaries: The work clarifies the limits of Regev's reduction framework. While it provides a powerful tool for quantum algorithms, the authors show that the underlying decoding problems can be solved classically if the number of samples ($m$) is sufficiently large ($m \ge \Omega(n^2)$).
4. Open Directions: The authors note that while they have closed the gap for $m \ge \Omega(n^2)$, the case where $m = O(n)$ (the "LWE regime") remains open. They speculate that the exponential speedup might still exist for problems where $m$ is linear in $n$, but their current techniques require quadratic samples.

Conclusion

Kothari, O'Donnell, and Wu have successfully "dequantized" a major class of lattice-based problems. By refining classical techniques involving dimension reduction, sparsity, and arithmetic combinatorics, they have shown that the apparent exponential quantum advantage for SIS$\infty$ and CIS was an artifact of specific parameter choices. Their results reinforce the robustness of post-quantum cryptography in standard parameter regimes while narrowing the search space for genuine quantum advantages to problems with linear sample complexity ($m=O(n)$).