Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems

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.

25 pages, 32 figures. Accepeted for publication in IEEE Transactions on Quantum Engineering

References in corpus (53)

• The Quantum Internet
• Quantum Networks for Elementary Arithmetic Operations
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Demonstration of the trapped-ion quantum-CCD computer architecture
• Quantum repeaters: From quantum networks to the quantum internet
• High-fidelity parallel entangling gates on a neutral atom quantum computer
• Realization of a scalable Shor algorithm
• Semiclassical Fourier Transform for Quantum Computation
• Optimal local implementation of non-local quantum gates
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Deterministic Quantum State Transfer and Generation of Remote Entanglement using Microwave Photons
• High-rate, high-fidelity entanglement of qubits across an elementary quantum network
• When Entanglement meets Classical Communications: Quantum Teleportation for the Quantum Internet (Invited Paper)
• Halving the cost of quantum addition
• Efficient Networks for Quantum Factoring
• Distributed Quantum Computing: a Survey
• Entanglement of trapped-ion qubits separated by 230 meters
• Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
• Optimal Quantum Measurements of Expectation Values of Observables
• MQT Bench: Benchmarking Software and Design Automation Tools for Quantum Computing
• Scalable ion traps for quantum information processing
• Distributed Quantum Computing across an Optical Network Link
• Long-distance distribution of atom-photon entanglement at telecom wavelength
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Compiler Design for Distributed Quantum Computing
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Ultrafast energy exchange between two single Rydberg atoms on the nanosecond timescale
• Efficient Long-Range Entanglement using Dynamic Circuits
• Optically-Heralded Entanglement of Superconducting Systems in Quantum Networks
• Distributed quantum computing: A distributed Shor algorithm
• Telecom networking with a diamond quantum memory
• A Modular Quantum Compilation Framework for Distributed Quantum Computing
• Mid-circuit qubit measurement and rearrangement in a ${}^{171}$Yb atomic array
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• Mid-circuit measurements on a single species neutral alkali atom quantum processor
• Deterministic constant-depth preparation of the AKLT state on a quantum processor using fusion measurements
• Arithmetic on a Distributed-Memory Quantum Multicomputer
• Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
• Fast Preparation and Detection of a Rydberg Qubit using Atomic Ensembles
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• An integrated quantum repeater at telecom wavelength with single atoms in optical fiber cavities
• Efficient Quantum Network Communication using Optimized Entanglement-Swapping Trees
• Constant-depth preparation of matrix product states with adaptive quantum circuits
• Quantum Fourier Transform using Dynamic Circuits
• A universal neutral-atom quantum computer with individual optical addressing and non-destructive readout
• Improved analytical bounds on delivery times of long-distance entanglement
• Distributing circuits over heterogeneous, modular quantum computing network architectures
• Entanglement-efficient bipartite-distributed quantum computing
• Measurement-Based Long-Range Entangling Gates in Constant Depth
• CODAR: A Contextual Duration-Aware Qubit Mapping for Various NISQ Devices
• Characterizing Qubit Traffic of a Quantum Intranet aiming at Modular Quantum Computers