IFP / Quantum · polynomial-time expressions

An Efficient Quantum Factoring Algorithm

Oded Regev

Journal of the ACM 2025

PublishedSource checked

Time bound: sqrt(n)+4 runs of a quantum circuit with O~(n^3/2) gates, plus polynomial classical post-processing
Space bound: Not extracted; circuit width must be specified by implementation

Source / version date: 12 Aug 2023
Comparison variant: Quantum · polynomial-time expressions
Cost scale: Expression only

Assumptions and source notes

Original 2023 algorithm with its stated number-theoretic heuristic correctness assumption. Per-run circuit size is not the total cost. Later unconditional correctness results are separately sourced.

Source location

Abstract
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

BibTeXDownload .bib

@misc{regev23,
  author = {Oded Regev},
  title = {{An Efficient Quantum Factoring Algorithm}},
  journal = {Journal of the ACM 72(1), Article 10},
  year = {2025},
  doi = {10.1145/3708471},
  url = {https://arxiv.org/abs/2308.06572},
  keywords = {quantum, factoring, lattices},
  cr_date = {2023-08-12},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Journal of the ACM 72(1), Article 10},
  cr_author_ids = {oded-regev}
}