Average-case lattice problem variants by filtering
Give polynomial-time quantum algorithms for three average-case lattice problems in parameter regimes where none was known: the short integer solution problem under the infinity norm, the learning-with-errors problem when the input is supplied as LWE-like quantum states rather than classical samples, and the extrapolated dihedral coset problem.
lattice problemslearning with errorsshort integer solutionfilteringpost-quantum cryptography
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Give polynomial-time quantum algorithms for three average-case lattice problems in parameter regimes where none was known: the short integer solution problem under the infinity norm, the learning-with-errors problem when the input is supplied as LWE-like quantum states rather than classical samples, and the extrapolated dihedral coset problem. The technique the paper calls filtering solves two quantum-state problems — constructing an LWE-like quantum state, and solving LWE given such a state — for noise distributions whose Fourier transform is non-negligible. The construction rests on Gram-Schmidt orthogonalization of circulant matrices together with a quantum Fourier transform step. The results for the short integer solution problem and for the extrapolated dihedral coset problem are then obtained not by new machinery but by composing this filtering algorithm with quantum reductions that already existed in the literature: a reduction from SIS to the LWE-state problem implicit in earlier work, and a reduction from the coset problem to the same place.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
How it works
The technique the paper calls filtering solves two quantum-state problems — constructing an LWE-like quantum state, and solving LWE given such a state — for noise distributions whose Fourier transform is non-negligible. The construction rests on Gram-Schmidt orthogonalization of circulant matrices together with a quantum Fourier transform step. The results for the short integer solution problem and for the extrapolated dihedral coset problem are then obtained not by new machinery but by composing this filtering algorithm with quantum reductions that already existed in the literature: a reduction from SIS to the LWE-state problem implicit in earlier work, and a reduction from the coset problem to the same place. This record's speedup class, "Exponential", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Stated by the primary source: "Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider.". Reported cost: Polynomial time in the lattice dimension n, for each of the three problems, in the stated parameter regimes. The paper gives the regimes rather than an exponent: the short integer solution result holds for a number of samples m in Ω((q−c)³ · n^(c+1) · q · log q), and the two quantum-state problems for m in Ω(n · q/η²)..
Implementation
Unsupported
average-case-lattice-problems-by-filtering.txt
ALGORITHM: Average-case lattice problem variants by filtering
PROBLEM: Give polynomial-time quantum algorithms for three average-case lattice problems in parameter regimes where none was known: the short integer solution problem under the infinity norm, the learning-with-errors problem when the input is supplied as LWE-like quantum states rather than classical samples, and the extrapolated dihedral coset problem.
IDEA: The technique the paper calls filtering solves two quantum-state problems — constructing an LWE-like quantum state, and solving LWE given such a state — for noise distributions whose Fourier transform is non-negligible. The construction rests on Gram-Schmidt orthogonalization of circulant matrices together with a quantum Fourier transform step. The results for the short integer solution problem and for the extrapolated dihedral coset problem are then obtained not by new machinery but by composing this filtering algorithm with quantum reductions that already existed in the literature: a reduction from SIS to the LWE-state problem implicit in earlier work, and a reduction from the coset problem to the same place.
REPORTED COST: Polynomial time in the lattice dimension n, for each of the three problems, in the stated parameter regimes. The paper gives the regimes rather than an exponent: the short integer solution result holds for a number of samples m in Ω((q−c)³ · n^(c+1) · q · log q), and the two quantum-state problems for m in Ω(n · q/η²).
BASIS: abstract of arXiv:2108.11015: "We show polynomial-time quantum algorithms for the following problems: 1. Short integer solution (SIS) problem under the infinity norm… 2. Learning with errors (LWE) problem given LWE-like quantum states… 3. Extrapolated dihedral coset problem (EDCP) with certain parameters."; section 1.1.1, Theorem 2, for the SIS regime; section 1.1.2, Theorem 8: "there exist polynomial-time quantum algorithms that solve C|LWE⟩n,m,q,f and S|LWE⟩n,m,q,f". Read for this record: the abstract, the whole of section 1 including the future-directions discussion, section 2, the theorem statements, and the references. The technical proofs in sections 4 through 7 were not retrieved and were not read, so the record covers what the paper claims and under what conditions, not how the claims are established.
PRIMARY SOURCE: Yilei Chen, Qipeng Liu, Mark Zhandry (2021), Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering — https://arxiv.org/abs/2108.11015
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Lattice problems with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering2021 · Yilei Chen, Qipeng Liu, Mark Zhandry
Primary source, and the source of this record's cost claim. Consult it above all for the boundary of the result: the abstract's statement that the variants solved are not in the parameter regimes known to be as hard as worst-case lattice problems, the remark after Theorem 8 that Gaussian noise is not covered, and the future-directions section where the authors state the work does not appear to affect the security of any lattice-based cryptosystem in use. The proofs in sections 4 through 7 were not read for this record.