Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm

• URL: http://arxiv.org/abs/2511.18198v1
• Date: Sat, 22 Nov 2025 21:57:22 GMT
• Title: Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm
• Authors: Wentao Yang, Bao Yan, Muxi Zheng, Quanfeng Lu, Shijie Wei, Gui-Lu Long,
• Abstract summary: integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm.<n>We propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm.
• Score: 4.0106855695925585
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from \( O(n^{3/2}) \) to \( O(n^{5/4}) \), and refined strategies achieve \( O(n \log n) \)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor \( N = 35 \), verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.

Related papers

• Quantum circuit design from a retraction-based Riemannian optimization framework [4.049905580196947]
  Design of quantum circuits for ground state preparation is a fundamental task in quantum information science.<n>We adopt a geometric perspective, formulating the problem as the minimization of an energy cost function directly over the unitary group.<n>We propose a scalable second-order algorithm that constructs a Newton system from measurement data.
  arXiv  Detail & Related papers  (2026-02-24T06:54:32Z)
• 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)
• Implementation and Analysis of Regev's Quantum Factorization Algorithm [0.2874893537471256]
  We present our implementation of Regev's algorithm for factoring composite numbers.<n>Despite Regev's theoretical advantage, our implementation exhibited execution times longer than Shor's algorithm for small integer factorization.
  arXiv  Detail & Related papers  (2025-02-13T21:02:15Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Forward and Backward Constrained Bisimulations for Quantum Circuits using Decision Diagrams [3.788308836856851]
  We develop efficient methods for the simulation of quantum circuits on classic computers. In particular, we show that constrained bisimulation can boost decision-diagram-based quantum circuit simulation by several orders of magnitude.
  arXiv  Detail & Related papers  (2023-08-18T12:40:47Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm. We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights. We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
  arXiv  Detail & Related papers  (2020-10-13T08:02:38Z)
• ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach [1.4873907857806357]
  We present a quantum circuit for estimating algorithmic complexity using the coding theorem method. As a use-case, an application framework for protein-protein interaction based on algorithmic complexity is proposed.
  arXiv  Detail & Related papers  (2020-09-18T14:41:41Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  Activation Relaxation (AR) is motivated by constructing the backpropagation gradient as the equilibrium point of a dynamical system. Our algorithm converges rapidly and robustly to the correct backpropagation gradients, requires only a single type of computational unit, and can operate on arbitrary computation graphs.
  arXiv  Detail & Related papers  (2020-09-11T11:56:34Z)

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.