Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
Open Access
- 17 September 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-25
Abstract
Shor's algorithm is one of the most prominent quantum algorithms, yet finding efficient implementations remains an active research challenge. While many approaches focus on low-level modular arithmetic optimizations, a broader perspective can provide additional opportunities for improvement. By adopting a mid-level abstraction, we analyze the algorithm as a sequence of computational tasks, enabling systematic identification of idle time and optimization of execution flow. Building on this perspective, we first introduce an alternating design approach to minimize idle time while preserving qubit efficiency in Shor's algorithm. By strategically reordering tasks for simultaneous execution, we achieve a substantial reduction in overall execution time. Extending this approach to distributed implementations, we demonstrate how task rearrangement enhances execution efficiency in the presence of multiple distribution channels. Furthermore, to effectively evaluate the impact of design choices, we employ static timing analysis (STA)—a technique from classical circuit design—to analyze circuit delays while accounting for hardware-specific execution characteristics, such as measurement and reset delays in monolithic architectures and ebit generation time in distributed settings. Finally, we validate our approach by integrating modular exponentiation circuits from QRISP and constructing circuits for factoring numbers up to 64 bits. Through an extensive study across neutral atom, superconducting, and ion trap quantum computing platforms, we analyze circuit delays, highlighting trade-offs between qubit efficiency and execution time. Our findings provide a structured framework for optimizing compiled quantum circuits for Shor's algorithm, tailored to specific hardware constraints.Keywords
All Related Versions
Funding Information
- German Ministry for Economic affairs and Climate action (50RA2208A)
- Deutsches Forschungszentrum für Künstliche Intelligenz (50RA2208B)
- Universität Bremen
This publication has 85 references indexed in Scilit:
- Reducing the Number of Qubits in Quantum Factoring2025
- Distributed quantum computing: A surveyComputer Networks, 2024
- Imperfect Distributed Quantum Phase Estimation2020
- Post-quantum cryptographyNature, 2017
- Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers2017
- Post-Quantum Cryptography: State of the Art2016
- An integrated quantum repeater at telecom wavelength with single atoms in optical fiber cavitiesApplied Physics B, 2016
- Quantum Computation and Quantum Information2012
- The quantum internetNature, 2008
- The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer1999