Quantum computing · Theory (AI-assisted)
A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus
arXiv:2611.18857v1 ↗PDF ↗Submitted 13 November 2026
- Question
- The vector dihedral coset problem asks for a secret \(\mathbf s\in\mathbb Z_q^n\) given states \(\tfrac1{\sqrt2}(\ket{0,\mathbf x}+\ket{1,\mathbf x+\mathbf s})\) with random unknown \(\mathbf x\). It bounds the hardness of lattice and group-action cryptography; Kuperberg's general algorithm takes time \(2^{O(\sqrt{n\log q})}\), and quasipolynomial algorithms were known only when \(q\) is a power of two (or a fixed prime). For which moduli can one do much better than Kuperberg?
- Result
- For every \(B\)-smooth modulus \(q\) (all prime factors at most \(B\)), a quantum algorithm recovers \(\mathbf s\) with time and samples \(n^{O(B^{1+o(1)}\log q)}B^{O(B^{2+o(1)}\log q)}\), which is quasipolynomial when \(B\) is polylogarithmic and \(q\) polynomial in \(n\). It removes one prime factor of the modulus at a time, clearing the nonlinear part of each sample's phase modulo that prime with an algorithm for diagonal equations over \(\mathbb F_p^n\). It also solves the extrapolated problem EDCP, but gives no attack on LWE.
The paper in detail
The dihedral coset problem arises from the standard quantum approach to the hidden shift problem: querying two shifted functions in superposition and measuring the output leaves \(\tfrac1{\sqrt2}(\ket0\ket{\mathbf x}+\ket1\ket{\mathbf x+\mathbf s})\) for a random unknown offset \(\mathbf x\). A polynomial algorithm would break lattice cryptography through Regev's reduction, and Kuperberg-style sieves give the best attacks on group-action schemes. Brakerski, Kirshanova, Stehlé and Wen showed that an extrapolated version (EDCP) is equivalent to LWE when only polynomially many samples are available. Over \(\mathbb Z_q^n\), Kuperberg's sieve costs \(2^{O(\sqrt{n\log q})}\); special moduli allow more.
The fast algorithms for \(q=2^k\) work as follows. Measuring the second register in the Fourier basis leaves a phase qubit \(\tfrac1{\sqrt2}(\ket0+\omega_q^{\langle\mathbf a,\mathbf s\rangle}\ket1)\) with a known random label \(\mathbf a\). Take \(n+1\) of them; their labels are linearly dependent modulo 2, and measuring which coset of the dependency the joint basis state lies in leaves one qubit whose label is even, which is a sample for modulus \(q/2\). Repeating \(k\) times costs \(n^{O(k)}\) samples per final equation, and a Hadamard measurement then yields one linear equation for the lowest bit of \(\mathbf s\).
For an odd prime \(p\) this breaks in two places. A qubit has two branches while dividing by \(p\) needs \(p\) of them, which the paper fixes by projecting pairs or tuples of qubits onto \(p\)-level states; two qubits give a qutrit with probability 3/4. More seriously, the qutrit's phase is a function of its basis label that is generally quadratic modulo 3, and the coset trick works only for linear phase functions. Restricted to a line \(\mathbf z+t\mathbf u\), the quadratic coefficient becomes \(\sum_iu_i^2\mathbf b_i\), and since \(u_i^2=1\) for nonzero \(u_i\) in \(\mathbb F_3\), choosing \(\mathbf u\) is a subset-sum problem over \(\mathbb F_3^n\), solvable in polynomial time from \(O(n^2)\) samples.
For general \(p\) the phase function has degree up to \(p-1\), and the algorithm clears it from the top degree down. At degree \(d\) it needs a nonzero \(\mathbf u\) with \(\sum_iu_i^d\mathbf a_i^{(d)}=0\), which the Ivanyos–Santha algorithm finds deterministically from a number of inputs governed by \(\gcd(d,p-1)\). Once the phase is linear modulo \(p\), the power-of-two step reduces the modulus by \(p\); this repeats for each prime factor of \(q\), and a final Fourier measurement plus linear algebra recovers \(\mathbf s\) digit by digit. The costs multiply to the stated bound.
The result applies to EDCP, but it does not threaten LWE: reductions from LWE give polynomially many clean samples, and this algorithm needs quasipolynomially many. Whether a polynomial-sample version exists, and whether moduli with large prime factors admit anything better than Kuperberg's sieve, are the questions left open.
Transferable methods
Coset measurement along a kernel line
The aim is to keep only the branches whose combined label is divisible by the prime, but that set is far too small to postselect on. Any coset of a line spanned by a kernel vector works just as well, and measuring which coset the state lies in is a measurement that always succeeds.
Collect \(n+1\) phase qubits with labels as the rows of \(A\in\mathbb Z_q^{(n+1)\times n}\): \[\bigotimes_{i=1}^{n+1}\tfrac1{\sqrt2}\bigl(\ket0+\omega_q^{\langle\mathbf a_i,\mathbf s\rangle}\ket1\bigr)=2^{-(n+1)/2}\sum_{\mathbf x\in\{0,1\}^{n+1}}\omega_q^{\langle A^{\mathsf T}\mathbf x,\mathbf s\rangle}\ket{\mathbf x}.\] Since \(n+1\) vectors in \(\mathbb F_2^n\) are dependent, there is \(\mathbf u\neq0\) with \(A^{\mathsf T}\mathbf u\equiv0\pmod2\).
Write \(\mathbf x=\mathbf z+t\mathbf u\) with \(\mathbf z\) a coset representative and \(t\in\{0,1\}\), and measure \(\mathbf z\). The two surviving branches differ in phase by a label that is even, so the remaining qubit is a sample for modulus \(q/2\) with known label \[\mathbf a'=\tfrac12A^{\mathsf T}\bigl(((\mathbf z+\mathbf u)\bmod2)-\mathbf z\bigr)\in\mathbb Z_{q/2}^n.\]
Each level consumes \(n+1\) samples per output sample, so \(k\) levels cost \(n^{O(k)}\), quasipolynomial for \(q=2^k=\mathrm{poly}(n)\). For a prime \(p\) the same step needs \(p\)-level states whose phase is a linear function of the level modulo \(p\); then the surviving \(p\) branches along \(\mathbf z+t\mathbf u\) carry phases linear in \(t\) with a label divisible by \(p\).
How to reuse it
In hidden-structure problems where postselecting on a subspace is too rare, measure the coset index of a one-dimensional subspace instead: every coset carries the same relative phase, so the measurement always succeeds and still extracts the structure.
Clearing nonlinear phase degrees with diagonal equations
For odd \(p\), a \(p\)-level sample's phase is a polynomial of degree up to \(p-1\) in its basis label, and only the linear part allows the modulus to drop. Restricting a product of samples to a line multiplies the top coefficient by \(u_i^d\), so choosing the line to solve a diagonal equation kills that coefficient without creating higher ones.
Every map \(g:\mathbb Z_p\to\mathbb Z_p^n\) with \(g(0)=0\) has a unique expansion in the binomial basis, \[g(x)=\sum_{d=1}^{p-1}\binom xd\mathbf a^{(d)},\qquad\mathbf a^{(d)}=\sum_{x=0}^{d}(-1)^{d-x}\binom dx g(x),\] and the change of coordinates is triangular with unit diagonal, so uniform values give uniform, independent coefficients.
For a product of samples with label maps of degree at most \(d\), restricting \(\sum_ig_i(x_i)\) to \(\mathbf x=\mathbf z+t\mathbf u\) gives a polynomial in \(t\) of degree at most \(d\) whose degree-\(d\) coefficient is \(\sum_iu_i^d\mathbf a_i^{(d)}\), because \(\binom xd\) has leading coefficient \(1/d!\) and substituting \(z+tu\) multiplies it by \(u^d\). For \(p=3\), \(d=2\) the condition is a subset sum over \(\mathbb F_3^n\). Editorial check: for \(p\in\{3,5,7,11\}\) and 800 random maps and lines, finite differences confirm both statements.
Ivanyos and Santha find a nonzero \(\mathbf u\in\mathbb F_p^\ell\) with \(\sum_iu_i^d\mathbf a_i=0\) in time \(\mathrm{poly}(\ell,p)\) once \[\ell\ge(n+1)^{g\lceil\log_2(g+1)\rceil}g^{\frac{g(g-1)}2\lceil\log_2(g+1)\rceil},\qquad g=\gcd(d,p-1).\] At most \((p-1)/g\) degrees share a given \(g\), so each divisor of \(p-1\) adds \(O(p\log p)\) to the exponent of \(n\); with \(p^{o(1)}\) divisors this gives \(n^{O(p^{1+o(1)})}\) per modulus reduction, better than the \(n^{O(p^2\log p)}\) of using subset sum at every degree.
How to reuse it
Whenever a combination step works only for linear phase or label functions over a finite field, expand in the binomial (Newton) basis and remove nonlinear coefficients from the top degree down, using relations among the samples' labels; each step must not reintroduce higher degrees, which the binomial basis guarantees.
Context & limitations
Why it matters. It shows that smoothness of the modulus, not the special arithmetic of powers of two, is what makes the vector problem easier, and it identifies the obstacle at odd primes (phases that are not linear modulo \(p\)) together with a general way around it. This sharpens the map of where coset-state attacks on post-quantum assumptions can and cannot reach.
Limitations. The exponent grows with the largest prime factor, so moduli with a large prime factor gain nothing over Kuperberg. The algorithm needs quasipolynomially many clean samples, whereas the known reduction from LWE supplies only polynomially many, so there is no consequence for lattice cryptography, as the author stresses. Concurrent work by Boucher, Fouque and Shen covers prime powers by different means. The paper states that the main algorithm was found by ChatGPT-5.6 Sol in a conversation with the author in July 2026, that an improvement using the Ivanyos–Santha solver came from ChatGPT-6 Astra in September, and that the author verified and simplified the algorithm and is responsible for its correctness; AI tools also helped expand later sections. No formal verification is reported.