Streaming Regev's Quantum Factoring Algorithm
A major practical obstacle to Regev's factoring algorithm is its large space usage. In particular, the algorithm was believed to be incompatible with "qubit recycling," which streams the control qubits in phase estimation rather than storing them all simultaneously. We show how to fix this streaming problem. We build on the construction of Ragavan and Vaikuntanathan, which used Fibonacci accumulators to reduce the qubit count from $O(n^{1.5})$ to $11.32n$. We make two key improvements. First, we use superposition masking to prevent unwanted information from entering the accumulators,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.06733
curl -X POST /api/v1/records/arxiv/2610.06733/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.06733/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'