IFP / Quantum · polynomial-time expressions

Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms

Cédric Pilatte

Forum of Mathematics, Pi 2026

PublishedSource checked

Time bound: Improved Regev-type quantum factoring circuit bounds with unconditional correctness
Space bound: Not extracted from the source

Source / version date: 25 Apr 2024
Comparison variant: Quantum · polynomial-time expressions
Cost scale: Expression only

Assumptions and source notes

Proves an appropriate variant of the number-theoretic conjecture needed for Regev-type algorithms. This is a correctness improvement, not a new exponential time coefficient.

Source location

Abstract; theorem statements
Version: arXiv:2404.16450; first submitted 2024-04-25, latest inspected v3 2026-08-24

Primary source ↗

BibTeXDownload .bib

@misc{pilatte24,
  author = {Cédric Pilatte},
  title = {{Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms}},
  journal = {Forum of Mathematics, Pi 14, e5},
  year = {2026},
  doi = {10.1017/fmp.2025.10023},
  url = {https://arxiv.org/abs/2404.16450},
  keywords = {quantum, factoring, discrete logarithms, unconditional},
  cr_date = {2024-04-25},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Forum of Mathematics, Pi 14, e5},
  cr_author_ids = {cedric-pilatte}
}