Simulations of Shor's Algorithm using Matrix Product States

2015/01/30 by David S. Wang, Wang, David S., Charles D. Hill +3 · 2 citations
Chemistry · Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Chemistry #Computer science #Error Correcting Code Techniques #FOS: Physical sciences #Formalism (music) #Mathematics #Matrix (chemical analysis) #Matrix multiplication #Parallel computing #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum mechanics #Qubit #quant-ph

paper · pdf · doi:10.48550/arxiv.1501.07644

published in arXiv (Cornell University) (Cornell University) · 7 pages, 4 tables, 4 figures

arxiv created 2015/01/30 · openalex publication_date 2015/01/30 · arxiv updated 2015/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We show that under the matrix product state formalism the states produced in Shor's algorithm can be represented using O(max(4lr², 2^2l)) space, where l is the number of bits in the number to factorise, and r is the order and the solution to the related order-finding problem. The reduction in space compared to an amplitude formalism approach is significant, allowing simulations as large as 42 qubits to be run on a single processor with 32GB RAM. This approach is readily adapted to a distributed memory environment, and we have simulated a 45 qubit case using 8 cores with 16GB RAM in approximately one hour.

Cited by

• Quantum State Preparation by Improved MPS Method
• Tensor-Parallel Emulation of Quantum Circuits with Block-Cyclic Distributed Matrix Product States

Related

• Distributed Shor's algorithm
• Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
• A Refinement of Shor's Algorithm
• Shor's algorithm with fewer (pure) qubits
• Implementation of Shor Algorithm: Factoring a 4096-Bit Integer Under Specific Constraints