Family 279Mathematical physicsNo LeanNot yet digested
Exact quantum factoring over a fixed finite gate set
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.
Manuscripts in this family · 1
Exact quantum factoring over a fixed finite gate set
Sep 25, 2026·main.pdf
We 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.