Quantum Hardness of Approximate Lattice Problems

Quantum Hardness of Approximate Lattice Problems

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.

A lattice generated by independent vectors $b_1,\ldots,b_d$ is $L=\{\sum_i z_i b_i:z_i\in\mathbb Z\}$. SVP seeks a shortest nonzero lattice vector; SIVP seeks $d$ independent short vectors, with approximation measured against the relevant successive minimum.

An $n$-qubit pure state is a unit vector in $(\mathbb C^2)^{\otimes n}$, considered up to global phase. A quantum algorithm applies permitted quantum operations and measurements; complexity depends on the gate and input-access model.

Statement recorded in the supplied source.

Is it impossible for a quantum polynomial-time algorithm to approximate SVP or SIVP within any polynomial factor? [S2]

Scope qualification.

The approximation factor, dimension range, norm, promise-problem encoding, and quantification over all polynomial factors are retained as written; no hardness assumption is added.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Determine whether quantum polynomial-time algorithms fail to approximate the stated lattice problems within every polynomial factor.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000236 (OWR-831-008). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Complexity Theory $2006$, Oberwolfach Reports, DOI 10.4171/owr/2005/26, pp. 1431--1504 https://doi.org/10.4171/owr/2005/26.
• S3 Aaronson quantum states paper https://arxiv.org/abs/quant-ph/0507242. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30000236 and source code OWR-831-008 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Research attempt

Literature, source context and scope

The full original catalogue body and source qualifications are preserved above. The relevant primary workshop passages were read in the cached publisher report. Historical claims and subsequent attributed results are distinguished from the mathematical work below. A restricted example, standard lemma or known theorem is not counted as new progress on the entire original target. Missing assumptions and repeated or rhetorical extracts are not silently turned into different solved problems.

Why a small coefficient box does not solve the lattice problem

The source asks about quantum hardness of lattice problems in the context of learning with errors and reductions. We test a basic proposed search route: enumerate short integer coefficient vectors in the supplied basis and use them to find linearly independent short lattice vectors. This is a route for the independent-vectors task, not a quantum lower bound or a shortest-vector impossibility theorem. Taking $M=2^b$ uses only $O(b)$ input bits. Every fixed polynomial coefficient cutoff $B(b)$ is eventually much smaller than $M$, so this box search can miss every short independent pair even in dimension two. However the elementary basis replacement $b_2\leftarrow b_2-Mb_1$ immediately repairs this example, with a coefficient representable in $O(b)$ bits. Consequently the example obstructs the box restriction itself and supplies no hardness result for basis reduction, classical algorithms or quantum algorithms. The shortest input vector already is a shortest lattice vector, another reason not to claim a shortest-vector lower bound from this example.

Literature qualification and verification

Recent primary preprints illustrate why current claims need care: ePrint 2026/1591 claims quantum lattice consequences via a dihedral-coset algorithm, while ePrint 2026/1693 presents a contrary analysis of that proposed procedure. Their abstracts and revision information were inspected; the competing proofs and formalization were not independently checked here. This disagreement is not used as a theorem, an established resolution, or a conclusion about every quantum algorithm. For $M=1024$ and $B=10$, exhaustive coefficient enumeration confirms that every enumerated vector off the horizontal axis has norm at least $\sqrt{1014^2+1}$, while $(0,1)$ requires coefficients $(-1024,1)$. The intended lattice problem, approximation regime and reduction still matter; no general quantum upper or lower bound is obtained. The failed step is equating coordinate size in an arbitrary basis with geometric shortness.

References and source attribution

Primary workshop report: https://doi.org/10.4171/owr/2005/26. Relevant passages read: 2005/26 pp. 1452--1453, quantum lattice reductions and the hardness question.

https://eprint.iacr.org/2026/1591. Read primary abstract and revision information for the claimed quantum dihedral-coset/lattice algorithm; disputed claim, not accepted here as an established result.

https://eprint.iacr.org/2026/1693. Read primary abstract of the contrary analysis of that proposed dihedral-coset algorithm; did not independently check its proof or linked formalization.

All retrievals were checked on 11 October 2026. Original question attribution remains in the preserved Sources section. External theorems are attributed and not claimed as new discoveries or fully verified merely by citation.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% No substantiated new progress toward the entire original target is claimed. The worked results and failed route are delimited above; a known result, illustrative model, or auxiliary obstruction is not counted as original-target completion.

Final status and attribution

Attempt status: unresolved. This describes this research attempt, not a new ruling on the source catalogue's status or on external literature claims. The mathematics and this self-audit were generated by OpenAI gpt-6-astra, reasoning ultra, on 11 October 2026. Codex (GPT-6; exact serving revision not exposed) orchestrated the batch and contributed formatting/repository review. No human mathematical authorship, independent human proof checking, or formal verification is claimed. The historical preparation paragraphs in the reproduced catalogue body concern that body only.

Contribution prompt A was applied to the complete definition and supplied source record, followed by the adversarial checks of prompt B. Local reproduction files are batch016/checks.py, computations.json, and the per-ID audit JSON. They were not public links at preparation time. Numerical checks are finite and do not prove unrestricted results. No LaTeX engine was found locally; compilation was not performed by this research agent.