Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups

Abstract

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 which to explore the power of Regev's framework. We first extend the Cheng-Wan reduction to the discrete logarithm problem in finite abelian groups, assuming access to embeddings of their cyclic factors. We also establish NP-hardness of Reed-Solomon bounded-distance decoding at asymptotically vanishing rate, reaching the rate regime relevant to Cheng-Wan, while the radius at which we establish hardness remains beyond the Cheng-Wan radius. We then instantiate Regev's reduction at the Cheng-Wan parameters and, under a conjecture on the performance of the induced BDD algorithm on the structured Cheng-Wan instances, characterize the noise threshold for the quantum decoding problem(QDP) sufficient to solve DLOG. We evaluate known decoders in this regime and show that a quantum decoder based on unambiguous state discrimination(USD) enables Regev's reduction to reach a strictly stronger decoding regime than the standard classical Reed-Solomon decoders we consider. Nevertheless, the QDP noise threshold required by the Cheng-Wan reduction is asymptotically 4/3 times that achieved by USD. Going beyond the USD framework, we show that every Cheng-Wan instance can be solved through Regev's reduction using a suitable Pretty Good Measurement and its inverse, although no efficient implementation of it is known.

Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
Han Luo, Ziyi Yang, Jingquan Luo +5
arXiv5 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Measurement-dependent reduction of open dynamics in the quantum phase estimation algorithm: the visible subspace and the damped Fejér kernel
Marina O. Gordeichuk, Oleg M. Kiselev
arXiv26 Oct 2026PreprintarXiv licenceFull textMathematical physics Numerical analysis & scientific computingarXiv
pcNN-SN: a physics-enhanced predictor-corrector neural network algorithm coupled with the discrete ordinates method for neutron transport equations
Cong Liu, Junxia Wei, Shuai Wang +1
arXiv1 Oct 2026PreprintarXiv licenceFull textComputational physicsarXiv
Effective discrete-modulated continuous variable QKD under general attacks using dimension reduction
Mariana Navarro, Mateus Araújo, Antonio Acín +1
arXiv9 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Several results on the almost good reduction property to the q-discrete Painlevé equations over the field of p-adic numbers
Masataka Kanki
arXiv27 Sep 2026PreprintCC BY 4.0Full textStatistical & nonlinear physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{garrido2026regevs,
  title = {{Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups}},
  author = {M. Isabel Franco Garrido and André Chailloux},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.03972},
  eprint = {2605.03972},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.03972},
}

RIS

TY  - UNPB
TI  - Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
AU  - M. Isabel Franco Garrido
AU  - André Chailloux
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2605.03972
UR  - https://arxiv.org/abs/2605.03972
AB  - 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 which to explore the power of Regev's framework. We first extend the Cheng-Wan reduction to the discrete logarithm problem in finite abelian groups, assuming access to embeddings of their cyclic factors. We also establish NP-hardness of Reed-Solomon bounded-distance decoding at asymptotically vanishing rate, reaching the rate regime relevant to Cheng-Wan, while the radius at which we establish hardness remains beyond the Cheng-Wan radius. We then instantiate Regev's reduction at the Cheng-Wan parameters and, under a conjecture on the performance of the induced BDD algorithm on the structured Cheng-Wan instances, characterize the noise threshold for the quantum decoding problem(QDP) sufficient to solve DLOG. We evaluate known decoders in this regime and show that a quantum decoder based on unambiguous state discrimination(USD) enables Regev's reduction to reach a strictly stronger decoding regime than the standard classical Reed-Solomon decoders we consider. Nevertheless, the QDP noise threshold required by the Cheng-Wan reduction is asymptotically 4/3 times that achieved by USD. Going beyond the USD framework, we show that every Cheng-Wan instance can be solved through Regev's reduction using a suitable Pretty Good Measurement and its inverse, although no efficient implementation of it is known.
ER  -

Abstract

Related

Cite