{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-13","reactions":{}}