Welcome to the resource topic for 2024/222
Title:
Reducing the Number of Qubits in Quantum Factoring
Authors: Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher
Abstract:This paper focuses on the optimization of the number of logical qubits in Shor’s quantum factoring algorithm. As in previous works, we target the implementation of the modular exponentiation, which is the most costly component of the algorithm, both in qubits and operations.
In this paper, we show that using only o(n) work qubits, one can obtain the first bit of the modular exponentiation output. We combine this result with May and Schlieper’s truncation technique (ToSC 2022) and the Ekerå-Håstad variant of Shor’s algorithm (PQCrypto 2017) to obtain a quantum factoring algorithm requiring only n/2 + o(n) qubits in the case of an n-bit RSA modulus, while current envisioned implementations require about 2n qubits.
Our algorithm uses a Residue Number System and succeeds with a parametrizable probability. Being completely classical, we have implemented and tested it. Among possible trade-offs, we can reach a gate count \mathcal{O}(n^3) for a depth \mathcal{O}(n^2 \log^3 n), which then has to be multiplied by \mathcal{O}(\log n) (the number of measurement results required by Ekerå-Håstad). Preliminary logical resource estimates suggest that this circuit could be engineered to use less than 1700 qubits and 2^{36} Toffoli gates, and require 60 independent runs to factor an RSA-2048 instance.
ePrint: https://eprint.iacr.org/2024/222
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .