Id: arxiv/2611.18857 Url: https://arxiv.org/abs/2611.18857 Tags: quant-ph, cs.CR Score: 0 Title: A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus Domain: quant-ph Source: arxiv Authors: Aparna Gupte Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-13 Page: https://delphi.science/r/arxiv/2611.18857 We give a quantum algorithm for the vector dihedral coset problem over $\mathbb{Z}_q^n$, in which the goal is to recover $\mathbf{s} \in \mathbb{Z}_q^n$ given independent samples of the form $\frac{1}{\sqrt{2}}\bigl(|{0,\mathbf{x}}\rangle+|{1,\mathbf{x}+\mathbf{s}}\rangle\bigr)$, for $\mathbf{x}\sim \mathbb{Z}_q^n$. When the modulus $q$ is $B$-smooth, the algorithm uses $n^{O(B^{1+o(1)}\log q)}B^{O(B^{2+o(1)}\log q)}$ samples and time. For $B = \mathrm{polylog}(n)$ and $q=\mathrm{poly}(n)$, this gives a quasipolynomial time- and sample-complexity. This extends the previously known…