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

• URL: http://arxiv.org/abs/2503.22564v1
• Date: Fri, 28 Mar 2025 16:07:52 GMT
• Title: Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• Authors: Moritz Schmidt, Abhoy Kole, Leon Wichette, Rolf Drechsler, Frank Kirchner, Elie Mounzer,
• Abstract summary: We introduce an alternating design approach to minimize idle time while preserving qubit efficiency in Shor's algorithm.<n>We also demonstrate how task rearrangement enhances execution efficiency in the presence of multiple distribution channels.<n>Our findings provide a structured framework for optimizing compiled quantum circuits for Shor's algorithm.
• Score: 4.430488261124667
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators.<n>This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-03T17:15:23Z)
• Compilation Techniques for Spin Qubits in a Shuttling Bus Architecture [1.7212402977075867]
  We propose and evaluate five mapping algorithms using benchmarks from quantum algorithms.<n>The Swap Return strategy emerged as the most robust solution, offering a superior balance between execution time and error minimization.
  arXiv  Detail & Related papers  (2025-02-10T08:57:52Z)
• Pattern Tree: Enhancing Efficiency in Quantum Circuit Optimization Based on Pattern-matching [3.2801774304960447]
  We propose a novel framework for quantum circuit optimization based on pattern matching to enhance its efficiency.<n>We show that pattern-tree-based pattern matching can reduce execution time by an average of 20% on a well-accepted benchmark set.
  arXiv  Detail & Related papers  (2024-12-09T07:21:11Z)
• Curriculum reinforcement learning for quantum architecture search under hardware errors [1.583327010995414]
  This work introduces a curriculum-based reinforcement learning QAS (CRLQAS) designed to tackle challenges in VQA deployment. The algorithm incorporates (i) a 3D architecture encoding and restrictions on environment dynamics to explore the search space of possible circuits efficiently. To facilitate studies, we developed an optimized simulator for our algorithm, significantly improving computational efficiency in noisy quantum circuits.
  arXiv  Detail & Related papers  (2024-02-05T20:33:00Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI is an optimistic value-based algorithm that explores the value function space via noise perturbation with posterior sampling. We show our algorithm achieves $widetildeO(sqrtd3H3 T + d2H2 E[tau]$ worst-case regret in the presence of unknown delays. We incorporate a gradient-based approximate sampling scheme via Langevin dynamics for Delayed-LPSVI.
  arXiv  Detail & Related papers  (2023-10-29T06:12:43Z)
• Hybrid discrete-continuous compilation of trapped-ion quantum circuits with deep reinforcement learning [1.7087507417780985]
  We show that we can significantly reduce the size of relevant quantum circuits for trapped-ion computing.<n>Our framework can also be applied to an experimental setup whose goal is to reproduce an unknown unitary process.
  arXiv  Detail & Related papers  (2023-07-12T14:55:28Z)
• Fast optimal structures generator for parameterized quantum circuits [4.655660925754175]
  Current structure optimization algorithms optimize the structure of quantum circuit from scratch for each new task of variational quantum algorithms (VQAs) We propose a rapid structure optimization algorithm for VQAs which automatically determines the number of quantum gates and directly generates the optimal structures for new tasks.
  arXiv  Detail & Related papers  (2022-01-10T12:19:37Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.