Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
In this article, we investigate whether combining Regev's reduction with the Cheng-Wan reduction can yield an alternative quantum algorithm for the discrete logarithm problem (DLOG) in finite abelian groups. Cheng and Wan reduce DLOG over finite fields to bounded-distance decoding of low-rate Reed-Solomon codes at a large decoding radius. Regev's reduction, in turn, exploits a decoder for the high-rate dual code with a lower noise level to obtain a quantum algorithm for decoding the original low-rate code at a larger radius. The Cheng-Wan instances therefore provide a natural setting in…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.03972
curl -X POST /api/v1/records/arxiv/2605.03972/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.03972/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'