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

Entanglement in Shor's Factoring Algorithm

Jianing Tan, Zhihao Liu, Hanwu Chen

Published Mar 28, 2020• 0 citations
Publisher

Abstract

Quantum algorithms are well known for their higher efficiency compared to their classical counterparts.However, the origin of the speed-up offered by quantum algorithms is a debatable question.Using entanglement measure based on coefficient matrix, we investigate the entanglement features of the quantum states used in Shor's factoring algorithm.The results show that if and only if the order r is 1, the algorithm generates no entanglement.Finally, compare with published studies results (Proceedings: Mathematical, Physical and Engineering Sciences, 459(2036): 2011-2032, 2003, Physical Review A, 72(6): 062308, 2005), we give counter examples to show that previous researches neglect partially entanglement.

DOI
10.5121/csit.2020.100307

Related papers

Coherence and entanglement dynamics in Shor's algorithm

Linlin Ye, Zhaoqi Wu, Shao-Ming Fei

Shor's algorithm outperforms its classical counterpart in efficient prime factorization. We explore the coherence and entanglement dynamics of the evolved states within Shor's algorithm, showing that the coherence in each step relies on the dimension of register or the order, and discuss the relations between geometric coherence and geometric entanglement. We investigate how unitary operators induce variations in coherence and entanglement, and analyze the variations of coherence and entanglement within the entire algorithm, demonstrating that the overall effect of Shor's algorithm tends to deplete coherence and produce entanglement. Our research not only deepens the understanding of this algorithm but also provides methodological references for studying resource dynamics in other quantum algorithms.

quant-pharXiv:2604.06639•Communications in Theoretical Physics•Apr 9, 2026•3 citations

Entangled quantum states generated by Shor’s factoring algorithm

Yishai Shimoni, Daniel Shapira, Ofer Biham

The intermediate quantum states of multiple qubits, generated during the operation of Shor's factoring algorithm are analyzed. Their entanglement is evaluated using the Groverian measure. It is found that the entanglement is generated during the preprocessing stage of the algorithm and remains nearly constant during the quantum Fourier transform stage. The entanglement is found to be correlated with the speedup achieved by the quantum algorithm compared to classical algorithms.

arXiv:quant-ph/0510042•Physical Review A•Dec 6, 2005•41 citations

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•43 citations

On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers

Zhengjun Cao, Zhenfu Cao

Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has $r$ possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.

arXiv:1409.7352•Sep 10, 2014•8 citations

Entanglement simulations of Shor's algorithm

S. Parker, 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 initially maximally mixed qubits (Parker, S. and Plenio, M. B., 2000, Phys. Rev. Lett., 85, 3049). 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 to 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 its efficiency.

arXiv:quant-ph/0102136•Journal of Modern Optics•Jul 1, 2002•33 citations

Shor’s Factorization Algorithm

Mikio Nakahara

Shor’s factorization algorithm is one of the prime examples in which a quantum computer demonstrates enormous power surpassing its classical counterpart [1, 2]. Although the factorization algorithm may be carried out with a classical computer, it takes an exponentially longer time (i.e., practically impossible) compared to Shor’s quantum algorithm. Shor’s algorithm is almost identical with the classical one; it consists of a sequence of classical steps with one exception, which is replaced by a quantum algorithm. Our presentation here closely follows [3] and [4].

CRC Press eBooks•Mar 11, 2008•0 citations
Quantum algorithms are well known for their higher efficiency compared to their classical counterparts.However, the origin of the speed-up offered by quantum algorithms is a debatable question.Using entanglement measure based on coefficient matrix, we investigate the entanglement features of the quantum states used in Shor's factoring algorithm.The results show that if and only if the order r is 1, the algorithm generates no entanglement.Finally, compare with published studies results (Proceedings: Mathematical, Physical and Engineering Sciences, 459(2036): 2011-2032, 2003, Physical Review A, 72(6): 062308, 2005), we give counter examples to show that previous researches neglect partially entanglement.
Shor's algorithm outperforms its classical counterpart in efficient prime factorization. We explore the coherence and entanglement dynamics of the evolved states within Shor's algorithm, showing that the coherence in each step relies on the dimension of register or the order, and discuss the relations between geometric coherence and geometric entanglement. We investigate how unitary operators induce variations in coherence and entanglement, and analyze the variations of coherence and entanglement within the entire algorithm, demonstrating that the overall effect of Shor's algorithm tends to deplete coherence and produce entanglement. Our research not only deepens the understanding of this algorithm but also provides methodological references for studying resource dynamics in other quantum algorithms.
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.
Shor's factoring algorithm uses two quantum registers. By introducing more registers we show that the measured numbers in these registers which are of the same pre-measurement state, should be equal if the original Shor's complexity argument is sound. This contradicts the argument that the second register has rrr possible measured values. There is an anonymous comment which argues that the states in these registers are entangled. If so, the entanglement involving many quantum registers can not be interpreted by the mechanism of EPR pairs and the like. In view of this peculiar entanglement has not yet been mentioned and investigated, we think the claim that the Shor's algorithm runs in polynomial time needs more physical verifications. We also discuss the problem to certify quantum computers.
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 initially maximally mixed qubits (Parker, S. and Plenio, M. B., 2000, Phys. Rev. Lett., 85, 3049). 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 to 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 its efficiency.
Shor’s factorization algorithm is one of the prime examples in which a quantum computer demonstrates enormous power surpassing its classical counterpart [1, 2]. Although the factorization algorithm may be carried out with a classical computer, it takes an exponentially longer time (i.e., practically impossible) compared to Shor’s quantum algorithm. Shor’s algorithm is almost identical with the classical one; it consists of a sequence of classical steps with one exception, which is replaced by a quantum algorithm. Our presentation here closely follows [3] and [4].