Algorithms · Lattice problems
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.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Exponential
- Primary source on the speedupStated by the primary source: "Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider."
- Reported costPolynomial 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/η²).
- Papers1
A part this method uses, worked through
This page says together with a quantum Fourier transform step
— here is a concrete, runnable instance of it.
QFT then its inverse, on |0101⟩
4 qubits, starting at |0101⟩, applying the QFT then immediately undoing it.
Where it ends up
- 0101100%
The register reads 0101 again, exactly: the QFT and its inverse cancel, the way any unitary and its adjoint do.
Open this part in StudioGive 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.
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 →
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/η²)..
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 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Exponential
- Primary source on the speedup
- 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/η²).
- Speedup class
- Exponential (checked against the record's own primary paper, which states it)
- Complexity 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.
- Circuit
- Not supplied
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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.
Related entries
- Shor period finding
Algorithms
- Discrete logarithm on a quantum computer
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering
Yilei Chen, Qipeng Liu, Mark Zhandry · 2021
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.