Implementation of Shor Algorithm: Factoring a 4096-Bit Integer Under Specific Constraints

• URL: http://arxiv.org/abs/2505.03743v2
• Date: Fri, 16 May 2025 00:26:37 GMT
• Title: Implementation of Shor Algorithm: Factoring a 4096-Bit Integer Under Specific Constraints
• Authors: Abel C. H. Chen,
• Abstract summary: This study focuses on the implementation of Shor algorithm, aiming to improve modular computation efficiency and demonstrate the factorization of a 4096-bit integer under specific constraints.<n> Experimental results, when compared with state-of-the-art (SOTA) methods, indicate a significant improvement in efficiency while enabling the factorization of longer integers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, advancements in quantum chip technology, such as Willow, have contributed to reducing quantum computation error rates, potentially accelerating the practical adoption of quantum computing. As a result, the design of quantum algorithms suitable for real-world applications has become a crucial research direction. This study focuses on the implementation of Shor algorithm, aiming to improve modular computation efficiency and demonstrate the factorization of a 4096-bit integer under specific constraints. Experimental results, when compared with state-of-the-art (SOTA) methods, indicate a significant improvement in efficiency while enabling the factorization of longer integers.

Related papers

• Improving adiabatic quantum factorization via chopped random-basis optimization [1.1409483429861258]
  We apply the chopped random-basis (CRAB) optimization technique to enhance adiabatic quantum factorization algorithms.<n>We demonstrate the effectiveness of CRAB by applying it to factor the integers ranging from 21 to 2479.<n>This performance improvement shows resilience in the presence of dephasing noise, highlighting CRAB's practical utility in noisy quantum systems.
  arXiv  Detail & Related papers  (2025-05-22T03:06:02Z)
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor [30.867632812964743]
  We experimentally demonstrate factoring of the integer with a trapped ion quantum processor using the Schnorr approach and a modified version of quantum approximate optimization algorithm (QAOA)<n>We present experimental results on factoring $1591=37times43$ using 6 qubits as well as simulation results for $746579521times7817$ with 10 qubits and $35183361263263=4194191times8388593$ with 15 qubits.
  arXiv  Detail & Related papers  (2025-03-13T17:40:07Z)
• 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)
• 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)
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping [0.4681661603096333]
  This paper presents strategies to improve the performance of digitized counterdiabatic quantum optimization algorithms. Our approach increases the approximation ratio by an average of 4.49$times$ without error mitigation. Our findings provide valuable insights into the codesign of algorithm implementation, tailored to optimize qubit mapping and algorithm parameters.
  arXiv  Detail & Related papers  (2023-11-24T17:39:08Z)
• Integer Factorization through Func-QAOA [0.0]
  No efficient classical algorithm for cryptographic-time integer factorization has been found. We present the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches.
  arXiv  Detail & Related papers  (2023-09-26T18:00:25Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• Enhanced Scalability in Assessing Quantum Integer Factorization Performance [1.0619039878979954]
  In this chapter, we aim to analyze the time required for integer factorization tasks using Shor's algorithm. We also observe the impact of parameter pre-selection in Shor's algorithm.
  arXiv  Detail & Related papers  (2023-05-09T08:14:28Z)
• 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)
• A Survey of Quantization Methods for Efficient Neural Network Inference [75.55159744950859]
  quantization is the problem of distributing continuous real-valued numbers over a fixed discrete set of numbers to minimize the number of bits required. It has come to the forefront in recent years due to the remarkable performance of Neural Network models in computer vision, natural language processing, and related areas. Moving from floating-point representations to low-precision fixed integer values represented in four bits or less holds the potential to reduce the memory footprint and latency by a factor of 16x.
  arXiv  Detail & Related papers  (2021-03-25T06:57:11Z)
• 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)
• Algorithmic Error Mitigation Scheme for Current Quantum Processors [0.0]
  We present a hardware agnostic error mitigation algorithm for near term quantum processors inspired by the classical Lanczos method. We demonstrate through numerical simulations and experiments on IBM Quantum hardware that the proposed scheme significantly increases the accuracy of cost functions evaluations.
  arXiv  Detail & Related papers  (2020-08-25T09:48:20Z)

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.