Reducing the number of qubits in quantum factoring
summary
Claims factoring reduces to a discrete‑log instance so the quantum input register is n/2 + o(n) qubits (2048‑bit RSA → 1024‑bit DL), implements modular exponentiation using a truncated hash (22 LSBs) and RNS arithmetic with Barrett shifts and a log n truncation window, and yields time complexity about n^3 gates. Concrete estimate gives one exponentiation ≈2^35 Toffoli (~34 billion) and ~40 runs; later work cuts qubits to ~1,400 and total physical qubits to ~10^6.
AI-written summary · about
chapters (10)
- 0:00Introduction to factoring
- 2:44Shor's algorithm review
- 6:17Adapting to discrete logarithms
- 8:33Reducing RSA to discrete log
- 10:54Output compression technique
- 16:34Integer arithmetic implementation
- 24:50Arithmetic circuit optimization
- 33:47Refinements and improvements
- 38:53Summary and future outlook
- 44:15Q&A session
