Integer factorization
Find the prime factorization of a composite integer N; distinguish input length log N from the integer N itself.
Quantum · polynomial-time expressions
Logical circuits plus classical post-processing; conditional and unconditional claims labelled separately
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing 1997SourceBibTeX / details | 30 Aug 1995 | poly(log N) quantum and classical work | Not extracted from the source | PublishedSource checked |
| — | An Efficient Quantum Factoring AlgorithmJournal of the ACM 2025SourceBibTeX / detailsnumber-theoretic heuristic multiple quantum runs | 12 Aug 2023 | sqrt(n)+4 runs of a quantum circuit with O~(n3/2) gates, plus polynomial classical post-processing | Not extracted; circuit width must be specified by implementation | PublishedSource checked |
| — | Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithmsForum of Mathematics, Pi 2026SourceBibTeX / detailsunconditional correctness | 25 Apr 2024 | Improved Regev-type quantum factoring circuit bounds with unconditional correctness | Not extracted from the source | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Logical circuits plus classical post-processing; conditional and unconditional claims labelled separately
- Computation
- Quantum
- Rigor
- source dependent
- Instances
- general composite integers
- Cost scale
- Expression only
- Parameter
- n = ceil(log₂ N)
- Description
- Quantum factoring is polynomial in input length. Circuit size per run, number of runs, classical cost and correctness assumptions must remain explicit.
- Comparison rules
- Quantum factoring is polynomial in input length. Circuit size per run, number of runs, classical cost and correctness assumptions must remain explicit. Only compare entries with this cost scale, input domain and computational model. Polynomial and quasi-polynomial expressions without an extracted scalar are not ranked.
- Tags
- quantum, logical circuits, polynomial time