Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1501.07644

Simulations of Shor's Algorithm using Matrix Product States

Wang, David S., Charles D. Hill, Lloyd C. L. Hollenberg

Published Jan 30, 2015• 2 citations
arXivHTMLPDF

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$, $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.

DOI
10.48550/arxiv.1501.07644

Related papers

Optimising Matrix Product State Simulations of Shor's Algorithm

Aidan Dang, Charles D. Hill, Lloyd C. L. Hollenberg

We detail techniques to optimise high-level classical simulations of Shor's quantum factoring algorithm. Chief among these is to examine the entangling properties of the circuit and to effectively map it across the one-dimensional structure of a matrix product state. Compared to previous approaches whose space requirements depend on r , the solution to the underlying order-finding problem of Shor's algorithm, our approach depends on its factors. We performed a matrix product state simulation of a 60-qubit instance of Shor's algorithm that would otherwise be infeasible to complete without an optimised entanglement mapping.

arXiv:1712.07311•Quantum•Jan 25, 2019•39 citations

Reduction and Decomposition Optimizations in Quantum Computing Simulation Applied to the Shor’s Algorithm

Anderson Ávila, Renata Reiser, Mauricio Lima Pilla

Due to the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is important in order to develop and test new quantum algorithms. This work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are implemented by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Shor’s algorithm considering 2n+3 qubits in the order-finding quantum algorithm was simulated up to 25 qubits over CPU, sequentially and in parallel, and over GPU. Results confirm that temporal complexity is reduced. When comparing our implementations running on the same hardware with LIQUi|i, academic release version, our new simulator was faster and allowed for the simulation of more qubits.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Apr 14, 2017•0 citations

Distributed Phase Estimation Algorithm and Distributed Shor's Algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

Shor's algorithm is one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain success probability in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, in this paper we first propose a new distributed phase estimation algorithm. Our distributed phase estimation algorithm does not require quantum communication and it reduces the number of qubits of a single node compared to the traditional phase estimation algorithm (non-iterative version). Then we apply our distributed phase estimation algorithm to form a distributed order-finding algorithm for Shor's algorithm. Compared with the traditional Shor's algorithm (non-iterative version), the maximum number of qubits required by a single node of our dristributed order-finding algorithm is reduced by $(2-\dfrac{2}{k})L-\log_2k-O(1)$ when factoring an $L$-bit integer ($k$ is the number of compute nodes). The communication complexity of our distributed order-finding algorithm is $O(kL)$.

arXiv:2304.12100•Apr 24, 2023•5 citations

Distributed Shor's algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate $s/r$, where $r$ is the ``order" and $s$ is some natural number that less than $r$. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of $s/r$.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly $L/2$ qubits for factoring an $L$-bit integer and reduces the circuit depth of each computer.

arXiv:2207.05976•Quantum Information and Computation•Jan 1, 2023•24 citations

Parallel simulation of Shor's and Grover's algorithms in the distributed geometric machine

Anderson Ávila, Renata Reiser, Adenauer Yamin +1 more

The exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial complexity and memory access patterns are major performance hazards. A new methodology employs reduction and decomposition optimizations, exploring properties such as the sparsity of the Id-Operator and the partiality of dense unitary transformations to improve storage and distribution of quantum states. In this work, Shor's and Grover's algorithms are simulated in both CPU and GPU in the Distributed Geometric Machine environment. Additionally, they are compared to LIQUi|〉's results. In all cases, our simulation was faster and allowed for an improved number of qubits when compared to the academic release version of LIQUi|〉, with relative speedups up to 118×.

International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)•Jul 1, 2017•7 citations

Entanglement Simulations of Shor's Algorithm

Parker, S, Martin Bodo Plenio

We demonstrate that, in the case of Shor's algorithm for factoring, highly mixed states will allow efficient quantum computation, indeed factorization can be achieved efficiently with just one initial pure qubit and a supply of initally maximally mixed qubits (S. Parker and M. B. Plenio, Phys. Rev. Lett. 85, 3049 (2000)) . This leads us to ask how this affects the entanglement in the algorithm. We thus investigate the behaviour of entanglement in Shor's algorithm for small numbers of qubits by classical computer simulation of the quantum computer at different stages of the algorithm. We find that entanglement is an intrinsic part of the algorithm and that the entanglement through the algorithm appears to be closely related the amount of mixing. Furthermore, if the computer is in a highly mixed state any attempt to remove entanglement by further mixing of the algorithm results in a significant decrease in it's efficiency.

•Feb 27, 2001•17 citations
We show that under the matrix product state formalism the states produced in Shor's algorithm can be represented using O(max(4lr24lr^24lr2, 22l2^{2l}22l)) 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.
We detail techniques to optimise high-level classical simulations of Shor's quantum factoring algorithm. Chief among these is to examine the entangling properties of the circuit and to effectively map it across the one-dimensional structure of a matrix product state. Compared to previous approaches whose space requirements depend on r , the solution to the underlying order-finding problem of Shor's algorithm, our approach depends on its factors. We performed a matrix product state simulation of a 60-qubit instance of Shor's algorithm that would otherwise be infeasible to complete without an optimised entanglement mapping.
Due to the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is important in order to develop and test new quantum algorithms. This work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are implemented by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Shor’s algorithm considering 2n+3 qubits in the order-finding quantum algorithm was simulated up to 25 qubits over CPU, sequentially and in parallel, and over GPU. Results confirm that temporal complexity is reduced. When comparing our implementations running on the same hardware with LIQUi|i, academic release version, our new simulator was faster and allowed for the simulation of more qubits.
Shor's algorithm is one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain success probability in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, in this paper we first propose a new distributed phase estimation algorithm. Our distributed phase estimation algorithm does not require quantum communication and it reduces the number of qubits of a single node compared to the traditional phase estimation algorithm (non-iterative version). Then we apply our distributed phase estimation algorithm to form a distributed order-finding algorithm for Shor's algorithm. Compared with the traditional Shor's algorithm (non-iterative version), the maximum number of qubits required by a single node of our dristributed order-finding algorithm is reduced by (2−2k)L−log⁡2k−O(1)(2-\dfrac{2}{k})L-\log_2k-O(1)(2−k2​)L−log2​k−O(1) when factoring an LLL-bit integer (kkk is the number of compute nodes). The communication complexity of our distributed order-finding algorithm is O(kL)O(kL)O(kL).
Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate s/rs/rs/r, where rrr is the ``order" and sss is some natural number that less than rrr. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of s/rs/rs/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly L/2L/2L/2 qubits for factoring an LLL-bit integer and reduces the circuit depth of each computer.
The exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial complexity and memory access patterns are major performance hazards. A new methodology employs reduction and decomposition optimizations, exploring properties such as the sparsity of the Id-Operator and the partiality of dense unitary transformations to improve storage and distribution of quantum states. In this work, Shor's and Grover's algorithms are simulated in both CPU and GPU in the Distributed Geometric Machine environment. Additionally, they are compared to LIQUi|〉's results. In all cases, our simulation was faster and allowed for an improved number of qubits when compared to the academic release version of LIQUi|〉, with relative speedups up to 118×.
We demonstrate that, in the case of Shor's algorithm for factoring, highly mixed states will allow efficient quantum computation, indeed factorization can be achieved efficiently with just one initial pure qubit and a supply of initally maximally mixed qubits (S. Parker and M. B. Plenio, Phys. Rev. Lett. 85, 3049 (2000)) . This leads us to ask how this affects the entanglement in the algorithm. We thus investigate the behaviour of entanglement in Shor's algorithm for small numbers of qubits by classical computer simulation of the quantum computer at different stages of the algorithm. We find that entanglement is an intrinsic part of the algorithm and that the entanglement through the algorithm appears to be closely related the amount of mixing. Furthermore, if the computer is in a highly mixed state any attempt to remove entanglement by further mixing of the algorithm results in a significant decrease in it's efficiency.