A Modular, Adaptive, and Scalable Quantum Factoring Algorithm

• URL: http://arxiv.org/abs/2509.05010v4
• Date: Tue, 28 Oct 2025 09:15:55 GMT
• Title: A Modular, Adaptive, and Scalable Quantum Factoring Algorithm
• Authors: Alok Shukla, Prakash Vedula,
• Abstract summary: Shor's algorithm for integer factorization offers an exponential speedup over classical methods.<n>It remains impractical on Noisy Intermediate Scale Quantum (NISQ) hardware due to the need for many coherent qubits and very deep circuits.<n>We have developed a modular, windowed formulation of Shor's algorithm that mitigates these limitations.
• Score: 0.5729426778193398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shor's algorithm for integer factorization offers an exponential speedup over classical methods but remains impractical on Noisy Intermediate Scale Quantum (NISQ) hardware due to the need for many coherent qubits and very deep circuits. Building on our recent work on adaptive and windowed phase-estimation methods, we have developed a modular, windowed formulation of Shor's algorithm that mitigates these limitations by restructuring phase estimation into shallow, independent circuit blocks that can be executed sequentially or in parallel, followed by lightweight classical postprocessing. This approach allows for a reduction in the size of the phase (or counting) register from a large number of qubits down to a small, fixed block size of only a few qubits (for example, three or four phase qubits were sufficient for the computational examples considered in this work), while leaving the work register requirement unchanged. The independence of the blocks allows for parallel execution and makes the approach more compatible with near-term hardware than the standard Shor's formulation. An additional feature of the framework is the overlap mechanism, which introduces redundancy between blocks and enables robust reconstruction of phase information, though zero-overlap configurations can also succeed in certain regimes. Numerical simulations verify the correctness of the modular formulation while also showing substantial reductions in counting qubits per block.

Related papers

• Constant Depth Digital-Analog Counterdiabatic Quantum Computing [1.8923689868452591]
  We introduce a digital-analog quantum computing framework that enables counterdiabatic protocols to be implemented at constant circuit depth.<n>Counterdiabatic protocols suppress diabatic excitations in finite-time adiabatic evolution.<n>We show how this structure can be efficiently realized in a digital-analog setting using commutator product formulas.
  arXiv  Detail & Related papers  (2026-01-03T10:55:08Z)
• Modular Quantum Amplitude Estimation: A Scalable and Adaptive Framework [0.0]
  We introduce the Adaptive Windowed Quantum Amplitude Estimation (AWQAE) framework.<n>It is a modular, scalable and adaptive approach that decouples estimation precision from the number of physical qubits required in a single circuit.<n>AWQAE offers a powerful and flexible solution for performing high-precision QAE on resource-constrained quantum hardware.
  arXiv  Detail & Related papers  (2025-08-07T19:19:11Z)
• Efficient LCU block encodings through Dicke states preparation [0.0]
  FOQCS-LCU is a compact LCU formulation that requires only a linear number of ancilla qubits and is explicitly decomposed into one- and two-qubit gates.<n>We construct explicit block encoding circuits for representative spin models such as the Heisenberg and spin glass Hamiltonians.
  arXiv  Detail & Related papers  (2025-07-28T14:39:16Z)
• MILP-StuDio: MILP Instance Generation via Block Structure Decomposition [55.79888361191114]
  Mixed-integer linear programming (MILP) is one of the most popular mathematical formulations with numerous applications. We propose a novel MILP generation framework, called Block Structure Decomposition (MILP-StuDio), to generate high-quality instances by preserving the block structures.
  arXiv  Detail & Related papers  (2024-10-30T08:33:27Z)
• Surrogate Constructed Scalable Circuits ADAPT-VQE in the Schwinger model [0.0]
  We develop a new approach, (SC)$2$-ADAPT-VQE, to further advance the simulation of periodic systems on quantum computers. Our approach builds an ansatz from a pool of coordinate-invariant operators defined for arbitrarily large, though not arbitrarily small, volumes. Our method uses a classically tractable Surrogate Constructed'' method to remove irrelevant operators from the pool, reducing the minimum size for which the scalable circuits are defined.
  arXiv  Detail & Related papers  (2024-08-22T18:00:00Z)
• Towards early fault tolerance on a 2$\ imes$N array of qubits equipped with shuttling [0.0]
  Two-dimensional grid of locally-interacting qubits is promising platform for fault tolerant quantum computing. In this paper, we show that such constrained architectures can also support fault tolerance. We demonstrate that error correction is possible and identify the classes of codes that are naturally suited to this platform.
  arXiv  Detail & Related papers  (2024-02-19T23:31:55Z)
• CBQ: Cross-Block Quantization for Large Language Models [66.82132832702895]
  Post-training quantization (PTQ) has played a key role in compressing large language models (LLMs) with ultra-low costs.<n>We propose CBQ, a cross-block reconstruction-based PTQ method for LLMs.<n> CBQ employs a cross-block dependency using a reconstruction scheme, establishing long-range dependencies across multiple blocks to minimize error accumulation.
  arXiv  Detail & Related papers  (2023-12-13T07:56:27Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Scalable entanglement stabilization with modular reservoir engineering [0.8057006406834467]
  We present a family of protocols which employ fixed-depth qubit-qubit interactions alongside engineered linear dissipation to stabilize an $N$-qubit W state. We find that a modular approach to dissipation engineering, with several overlapping few-qubit dissipators rather than a single $N$-qubit dissipator, is essential for our protocol to be scalable.
  arXiv  Detail & Related papers  (2023-01-13T19:03:01Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
  arXiv  Detail & Related papers  (2021-07-06T19:51:37Z)
• Efficient Micro-Structured Weight Unification and Pruning for Neural Network Compression [56.83861738731913]
  Deep Neural Network (DNN) models are essential for practical applications, especially for resource limited devices. Previous unstructured or structured weight pruning methods can hardly truly accelerate inference. We propose a generalized weight unification framework at a hardware compatible micro-structured level to achieve high amount of compression and acceleration.
  arXiv  Detail & Related papers  (2021-06-15T17:22:59Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. We present a novel activation-based branching strategy and a BaB framework, named Branch and Dual Network Bound (BaDNB) BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial properties.
  arXiv  Detail & Related papers  (2021-04-14T09:22:42Z)

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.