A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.18857
curl -X POST /api/v1/records/arxiv/2611.18857/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18857/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'