Description
Quantum factoring is one of the most promising applications of quantum computing with practical real-world implications. Since its discovery by Peter Shor, researchers have reduced the memory requirements and optimised the gate counts of arithmetic subroutines for its implementation. Several notable advancements over the past year have brought the the memory cost of factoring a 2048 bit RSA integer below a million physical qubits. These resource estimates have since been used to predict the future risk quantum computers pose to classical cryptosystems.
While these quantum resource estimates are end-to-end, they still contain approximations and assumptions pertaining to the compatibility of algorithmic implementations and hardware capabilities. In this work, we bridge the gap between theory and practice by building an end-to-end fully-executable software package for quantum factoring. We demonstrate the power and flexibility of our design by explicitly implementing the complete Gidney-Ekerå’s 2019 algorithm decomposing down to basic gate sets. As a result, we can quantify the difference in resource costs to validate assumptions made in the original paper.
A key step used in previous resource estimates of Shor's algorithm in the literature has been a hand crafted fault-tolerant estimation, including register layout, T-state factory choices as well as bounding the cost of data packing and routing in the device. We move to a completely automated system using the Rottnest quantum compiler and cost the full execution on a fault-tolerant monolithic surface code architecture. This execution explicitly tracks every operation that must be performed including routing overheads, idling of unused memory, T-state generation and buffering. Our work assists both algorithm developers and hardware designers to diagnose bottlenecks and improve upon implementations of quantum algorithms.
| I am the presenting author | Yes |
|---|