Assume the flagged polygonal-transform and exact-factoring interfaces specified in the paper. We construct a polynomial-time uniform quantum circuit family over one fixed finite gate set that computes discrete logarithms in prime fields with probability one and polynomial worst-case resources. For prime-order inputs, each verified Fourier-bin label has probability at least 1/(81q). Given its verified logarithm, that probability is computable exactly by a bounded number of lattice-point counts in dimension at most thirteen. Dyadic completion produces success probability exactly one quarter, followed by one exact amplification step. All sampled probabilities are dyadic; no input-dependent rotation or postselection is used.
Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.
The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of
O(n1+ε) for any
ε>0; with practical choices of parameters, we expect scalings as low as
O(n1.3). Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with
O(n2+ε) gates and only
2n+O(logn) qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is
O(n1.5+ε). Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.
For squarefree $f\in\F_q[x]$, Berlekamp's fixed-point algebra is $B\cong\F_q^r$, where
r is the number of irreducible factors. We give an exact quantum splitting procedure in a circuit model permitting efficiently computable, input-dependent single-qubit rotations. For a block with
s≥2 factors, a quadratic-character test (odd
q) or absolute-trace test (characteristic
2) is nonconstant with an exactly known probability
pq,s≥1/2. Its value depends only on
q,s, not on the hidden factors. An auxiliary-qubit reduction to success probability
1/4 makes one Grover iteration exact. Thus factorization takes exactly
r−1 splitting rounds and
O(n3logq) quantum $\F_q$-operations, with deterministic polynomial classical preprocessing and bookkeeping. The method also extracts primitive idempotents of arbitrary finite-dimensional commutative unital algebras given by structure constants in
O(n4logq) quantum $\F_q$-operations, staying over $\F_q$ throughout. Computing the radical and passing to the center extends it to the decomposition of $A/\Rad(A)$ into simple two-sided ideals, for an arbitrary finite-dimensional associative $\F_q$-algebra
A.
Abstract We show that given the order of a single element selected uniformly at random from
ZN∗ Z N ∗ , we can with very high probability, and for any integer N, efficiently find the complete factorization of N in polynomial time. This implies that a single run of the quantum part of Shor’s factoring algorithm is usually sufficient. All prime factors of N can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.
Exact synthesis is a tool used in algorithms for approximating an arbitrary qubit unitary with a sequence of quantum gates from some finite set. These approximation algorithms find asymptotically optimal approximations in probabilistic polynomial time, in some cases even finding the optimal solution in probabilistic polynomial time given access to an oracle for factoring integers. In this paper, we present a common mathematical structure underlying all results related to the exact synthesis of qubit unitaries known to date, including Clifford+T, Clifford-cyclotomic and V-basis gate sets, as well as gates sets induced by the braiding of Fibonacci anyons in topological quantum computing. The framework presented here also provides a means to answer questions related to the exact synthesis of unitaries for wide classes of other gate sets, such as Clifford+T+V and SU(2) level k anyons.