1 · The essentials
Factoring a whole number means breaking it into prime numbers that multiply back to the original number. This manuscript presents a quantum computing method that returns the complete prime factorization of every integer at least two. It returns the correct answer with probability one, rather than merely with a high chance of success. The method uses the same fixed, finite collection of allowed operations for every input size. Both the number of operations and the number of quantum bits are bounded by polynomials in the length of the input, even in the worst case. The circuits can also be generated within a polynomial time bound. The main result has a Lean formalization, although the supplied material does not specify its detailed coverage.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine a workshop that breaks each number into its prime building blocks using only a fixed toolbox. Larger inputs require larger work plans, but not new types of tools; the manuscript also places polynomial bounds on the plan size and the workspace.
Why it matters
The result combines exact output with explicit limits on computational resources. Its fixed finite collection of operations makes clear that the construction does not depend on introducing new kinds of gates as inputs grow. The worst-case bounds cover both the operations performed and the quantum bits needed.
2 · Going further
The precise task is to output the complete prime factorization of every integer . The manuscript states that a polynomial-time uniform family of quantum circuits accomplishes this with probability one. Here, uniformity means that the circuits themselves can be generated in polynomial time, rather than merely being asserted to exist separately for each input size.
A single fixed finite set of bounded-arity gates suffices: there are finitely many allowed gate types, and each acts on a bounded number of qubits. Both the gate count and the qubit count have polynomial worst-case bounds in the input length. These are bounds in the length of the input, not in the numerical value of .
The supplied abstract states the result but does not describe the main idea of its argument or give a circuit construction. Only one manuscript is supplied, so there is no stated relationship to companion manuscripts and no historical comparison to reconstruct. The main result has a Lean formalization; the supplied material does not identify which additional implementation details or supporting claims it covers.
Useful notions
- Prime numbers and factorization
- Input length
- Polynomial resource bounds
- Quantum circuits and qubits
- Probability-one correctness
What was known before / what is new
Before
The supplied text does not describe earlier factoring results or an existing open problem. It therefore does not provide a basis for comparing this construction with previous methods.
New
The manuscript presents a polynomial-time uniform quantum circuit family for complete prime factorization with probability-one correctness. The stated construction simultaneously uses a fixed finite bounded-arity gate set and has polynomial worst-case bounds on gate and qubit counts.
Limits and assumptions
The stated domain is integers , and the resource bounds are measured in input length. The abstract does not list the gates, give the bounding polynomials, or describe the construction and its argument. The main result has a Lean formalization, but the supplied material does not specify its detailed scope, so verification of every associated claim cannot be inferred. No remaining open questions are identified in the supplied text.
Mini glossary
- Complete prime factorization —
- An expression of an integer as a product of prime numbers, including all repetitions needed to recover the integer.
- Polynomial-time uniform —
- Describes a circuit family whose circuits can be generated in time bounded by a polynomial in the input length.
- Bounded-arity gate —
- An allowed circuit operation that acts on a bounded number of qubits.
- Qubit —
- A quantum bit, used here as the unit for counting a circuit's quantum storage.
- Polynomial worst-case bound —
- A resource limit given by a polynomial in input length that holds even for the most demanding inputs of that length.
- Probability-one correctness —
- The requirement that the circuit output the correct complete prime factorization with probability one.
Keywords : Exact quantum factoring · Finite gate set · Uniform quantum circuits
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Gives a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer with probability one. Both gate count and qubit count are polynomial in the input length, and one fixed finite gate set suffices.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Exact quantum factoring over a fixed finite gate set
25/09/2026We give a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N ≥ 2 with probability one. A fixed finite set of bounded-arity gates suffices, and both the gate count and the number of qubits have polynomial worst-case bounds in the input length.