Paper 2024/2034
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Abstract
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. Our circuit completely factors any number
Note: Minor changes.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- factoringquantumShor's algorithmsquarefree decomposition
- Contact author(s)
-
gkm @ mit edu
sragavan @ mit edu
vinodv @ mit edu
kvankirk @ g harvard edu - History
- 2024-12-27: last of 2 revisions
- 2024-12-17: received
- See all versions
- Short URL
- https://ia.cr/2024/2034
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2034, author = {Gregory D. Kahanamoku-Meyer and Seyoon Ragavan and Vinod Vaikuntanathan and Katherine Van Kirk}, title = {The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/2034}, year = {2024}, url = {https://eprint.iacr.org/2024/2034} }