pith. sign in

arxiv: 2510.06097 · v2 · submitted 2025-10-07 · 🪐 quant-ph · cs.CR

On the Quantum Equivalence between S|LWErangle and ISIS

Andr\'e Chailloux , Paul Hermouet This is my paper

Pith reviewed 2026-05-18 09:07 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords S|LWEISISquantum reductionslearning with errorsshort integer solutionquantum algorithmscryptographyrecoverability
0
0 comments X

The pith

A generic reduction shows ISIS reduces to S|LWE> even when algorithms have errors.

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

This paper maps the relationship between the quantum problem S|LWE> and the inhomogeneous short integer solution problem ISIS by building reductions in both directions. A sympathetic reader cares because these problems support constructions of quantum algorithms for lattice cryptography, so their equivalence determines whether progress on one immediately yields progress on the other. The authors give the first fully generic reduction proving that an oracle for S|LWE> solves ISIS instances, and the reduction remains valid even if the underlying algorithms are imperfect. They introduce an intermediate inhomogeneous variant IC|LWE> that reduces to S|LWE>, then show a conditional reverse reduction that works only when ISIS solutions meet recoverability conditions, and they use it to recover prior quantum algorithms for small power-of-two alphabets.

Core claim

We present the first fully generic reduction from ISIS to S|LWE⟩, valid even in the presence of errors in the underlying algorithms. We then explore the reverse direction, introducing an inhomogeneous variant of C|LWE⟩, denoted IC|LWE⟩, and show that IC|LWE⟩ reduces to S|LWE⟩. Finally, we prove that, under certain recoverability conditions, an algorithm for ISIS can be transformed into one for S|LWE⟩. We instantiate this reverse reduction by tweaking a known algorithm for (I)SIS_∞ in order to construct quantum algorithm for S|LWE⟩ when the alphabet size q is a small power of 2.

What carries the argument

The generic reduction that converts ISIS instances to S|LWE> instances while preserving correctness despite errors in the solver.

Load-bearing premise

The reverse reduction from ISIS algorithms to S|LWE> algorithms requires that the produced solutions satisfy recoverability conditions.

What would settle it

An explicit family of ISIS instances together with a solver that succeeds on them but whose outputs cannot be recovered to solve the corresponding S|LWE> instances would falsify the unconditional reverse direction.

read the original abstract

Chen, Liu, and Zhandry [CLZ22] introduced the problems $S|LWE\rangle$ and $C|LWE\rangle$ as quantum analogues of the Learning with Errors problem, designed to construct quantum algorithms for the Inhomogeneous Short Integer Solution ($ISIS$) problem. Several later works have used this framework for constructing new quantum algorithms in specific cases. However, the general relation between all these problems is still unknown. In this paper, we investigate the equivalence between $S|LWE\rangle$ and $ISIS$. We present the first fully generic reduction from $ISIS$ to $S|LWE\rangle$, valid even in the presence of errors in the underlying algorithms. We then explore the reverse direction, introducing an inhomogeneous variant of $C|LWE\rangle$, denoted $IC|LWE\rangle$, and show that $IC|LWE\rangle$ reduces to $S|LWE\rangle$. Finally, we prove that, under certain recoverability conditions, an algorithm for $ISIS$ can be transformed into one for $S|LWE\rangle$. We instantiate this reverse reduction by tweaking a known algorithm for $(I)SIS_\infty$ in order to construct quantum algorithm for $S|LWE\rangle$ when the alphabet size q is a small power of 2, recovering some results of Bai et al. [BJK+ 25]. Our results thus clarify the landscape of reductions between $S|LWE\rangle$ and $ISIS$, and we show both their strong connection as well as the remaining barriers for showing full equivalence.

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 / 2 minor

Summary. The paper investigates the relationship between the quantum problem S|LWE⟩ and the inhomogeneous short integer solution (ISIS) problem. It claims the first fully generic reduction from ISIS to S|LWE⟩ that remains valid even when the underlying ISIS algorithm has errors. It introduces an inhomogeneous variant IC|LWE⟩ and proves that IC|LWE⟩ reduces to S|LWE⟩. Under certain recoverability conditions on solutions, it shows how an ISIS algorithm can be transformed into an S|LWE⟩ algorithm. The reverse direction is instantiated by modifying a known (I)SIS_∞ algorithm to yield a quantum algorithm for S|LWE⟩ when q is a small power of two, recovering results from prior work.

Significance. If the reductions hold with the stated error tolerance, the work clarifies the landscape of quantum-classical connections for lattice problems and provides a generic tool for converting ISIS solvers into S|LWE⟩ solvers. The explicit instantiation for small-power-of-two q that recovers Bai et al. results is a concrete strength, as is the introduction of IC|LWE⟩. The conditional nature of the reverse reduction is appropriately highlighted as a remaining barrier.

major comments (2)
  1. [ISIS to S|LWE reduction section] The section on the ISIS-to-S|LWE⟩ reduction (the forward direction claimed to be fully generic): the error-tolerance argument appears to proceed by using the ISIS oracle to prepare or measure quantum states, but it is unclear whether the analysis controls failure probability without assuming solution-norm bounds such as ||x|| < q/2 (common in ISIS_∞ settings). If such a bound is implicit, the reduction is not fully generic for arbitrary q or adversarial errors, directly affecting the central claim.
  2. [section describing the conditional transformation] The section describing the conditional transformation (reverse direction): the recoverability conditions on solutions are stated but not shown to be automatically satisfied by the forward reduction's output; this creates an asymmetry where one direction is claimed fully generic while the other remains conditional, which should be reconciled for the equivalence landscape to be fully clarified.
minor comments (2)
  1. [Introduction] Notation for S|LWE⟩ and C|LWE⟩ should be defined at first use with explicit reference to Chen-Liu-Zhandry [CLZ22] to improve readability.
  2. [Instantiation section] The instantiation for small power-of-two q would benefit from an explicit comparison table showing which prior results of Bai et al. are recovered and which parameters match exactly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We address each of the major comments below and have updated the paper accordingly to improve clarity on the generality of the reductions and the conditions involved.

read point-by-point responses

  1. Referee: [ISIS to S|LWE reduction section] The section on the ISIS-to-S|LWE⟩ reduction (the forward direction claimed to be fully generic): the error-tolerance argument appears to proceed by using the ISIS oracle to prepare or measure quantum states, but it is unclear whether the analysis controls failure probability without assuming solution-norm bounds such as ||x|| < q/2 (common in ISIS_∞ settings). If such a bound is implicit, the reduction is not fully generic for arbitrary q or adversarial errors, directly affecting the central claim.

    Authors: We thank the referee for highlighting this potential ambiguity. Our error-tolerance analysis does not implicitly assume any solution-norm bounds like ||x|| < q/2. The reduction is designed to work with the ISIS algorithm as a black-box oracle that may output erroneous solutions with some probability. The failure probability of the overall reduction is bounded using the success probability of the oracle and the properties of the quantum state, without requiring bounded norms. This ensures validity for arbitrary q and adversarial errors. We have added a clarifying paragraph in the revised manuscript to explicitly address this and confirm the generic nature of the reduction. revision: yes

  2. Referee: [section describing the conditional transformation] The section describing the conditional transformation (reverse direction): the recoverability conditions on solutions are stated but not shown to be automatically satisfied by the forward reduction's output; this creates an asymmetry where one direction is claimed fully generic while the other remains conditional, which should be reconciled for the equivalence landscape to be fully clarified.

    Authors: We appreciate this point regarding the asymmetry. The recoverability conditions are indeed required for the reverse reduction to hold in general, and we do not claim that the solutions produced by the forward ISIS-to-S|LWE⟩ reduction automatically satisfy them in all cases. This conditional aspect is intentional and reflects the current barriers to proving full equivalence. In the revised version, we have expanded the discussion to include examples where the conditions are satisfied (such as in the instantiation for small powers of two) and to better articulate why full equivalence is not yet established. This maintains the accuracy of our claims while clarifying the landscape. revision: partial

Circularity Check

0 steps flagged

No circularity: reductions are explicit proof transformations between independent problem instances

full rationale

The paper establishes a generic reduction from ISIS to S|LWE⟩ by direct algorithmic transformation that maps oracles and handles errors without defining one problem in terms of the other or fitting parameters to subsets of the target. The reverse direction is conditional on recoverability and instantiated by tweaking an external algorithm from Bai et al., with citations to CLZ22 and BJK+25 providing independent support rather than self-referential load-bearing. No equations reduce the claimed equivalence to a fitted input renamed as prediction, no uniqueness theorem is imported from the authors' own prior work, and the derivations remain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard hardness assumptions for lattice problems and on the existence of quantum algorithms that satisfy the stated recoverability conditions; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption ISIS and LWE variants remain hard under quantum reductions when parameters satisfy standard lattice conditions
    Invoked throughout the reduction statements as the background setting for which the equivalences are claimed

pith-pipeline@v0.9.0 · 5808 in / 1301 out tokens · 26924 ms · 2026-05-18T09:07:06.680866+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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

  1. Quantum Decoding Algorithms: Quantum Speedups in Optimization

    quant-ph 2026-05 unverdicted novelty 1.0

    A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.