Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
Authors:
Preprint
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 minimizes 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
This publication has 64 references indexed in Scilit:
- Distributed quantum computing across an optical network linkNature, 2025
- Distributed quantum computing: A surveyComputer Networks, 2024
- High-fidelity parallel entangling gates on a neutral-atom quantum computerNature, 2023
- Ultrafast energy exchange between two single Rydberg atoms on a nanosecond timescaleNature Photonics, 2022
- A quantum processor based on coherent transport of entangled atom arraysNature, 2022
- Creating heralded hyper-entangled photons using Rydberg atomsLight: Science & Applications, 2021
- Demonstration of the trapped-ion quantum CCD computer architectureNature, 2021
- Deterministic quantum state transfer and remote entanglement using microwave photonsNature, 2018
- An integrated quantum repeater at telecom wavelength with single atoms in optical fiber cavitiesApplied Physics B, 2016
- Experimental realization of Shor's quantum factoring algorithm using qubit recyclingNature Photonics, 2012