Amazon Researcher Claims Polynomial-Time Quantum Algorithm for 20-Year Dihedral Problem
Updated
Updated · The Quantum Insider · Aug 6
Amazon Researcher Claims Polynomial-Time Quantum Algorithm for 20-Year Dihedral Problem
3 articles · Updated · The Quantum Insider · Aug 6
Summary
Daniel R. Simon of Amazon Web Services posted a preliminary paper claiming a polynomial-time quantum algorithm for the Dihedral Coset Problem, a long-standing target in quantum computing theory.
The result matters because earlier reductions linked that problem to lattice tasks underlying post-quantum cryptography, including roughly square-root-of-n polylogarithmic approximations to the Shortest Vector Problem and some Learning With Errors instances.
Simon says the method removes a key limitation in prior work by avoiding Regev’s idealized subset-sum oracle and can still handle faulty samples at about 1/log n.
The paper does not show a practical break of NIST-backed post-quantum schemes, map the math to deployed parameters, or estimate qubits and gates needed at cryptographic scale.
Because the work is a preprint, specialists are expected to scrutinize its proof, probability bounds and circuit complexity before drawing conclusions about real-world lattice cryptography.