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:2604.06639 · Communications in Theoretical Physics

Coherence and entanglement dynamics in Shor's algorithm

Linlin Ye, Zhaoqi Wu, Shao-Ming Fei

quant-phSubmitted Apr 8, 2026• Announced Apr 9, 2026• 3 citations
arXivHTMLPDF

Abstract

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.

Journal reference
Commun. Theor. Phys. 78 (2026) 015102
DOI
10.1088/1572-9494/adf8cc
Comments
19 pages, 3 figures

Related papers

Analyze Shor Algorithm Optimization Trends and Suggest Optimization Directions

Jaehan Cho, Dawit Shin, Yeonjeong Hwang +1 more

Quantum computers leverage the principles of quantum mechanics to solve complex problems beyond the capabilities of classical computers, such as prime factorization, which poses a significant threat to cryptographic algorithms like RSA and ECC. Although current quantum resources are insufficient for effective decryption, ongoing research focuses on optimizing Shor's algorithm to overcome these limitations. Shor's algorithm, a quantum algorithm designed for efficient integer factorization, exploits quantum parallelism and entanglement to perform prime factorization exponentially faster than classical algorithms. This paper reviews recent trends in Shor algorithm optimization, particularly in enhancing the efficiency of ripple-carry operators and the Karatsuba algorithm in multiplication and proposes a multiplication method that applies the Strassen algorithm to constant adders

International Conference on Platform Technology and Service•Aug 26, 2024•1 citation

Coherence as a Resource for Shor’s Algorithm

Felix Ahnefeld, Thomas Theurer, Dario Egloff +2 more

Shor's factoring algorithm provides a superpolynomial speedup over all known classical factoring algorithms. Here, we address the question of which quantum properties fuel this advantage. We investigate a sequential variant of Shor's algorithm with a fixed overall structure and identify the role of coherence for this algorithm quantitatively. We analyze this protocol in the framework of dynamical resource theories, which capture the resource character of operations that can create and detect coherence. This allows us to derive a lower and an upper bound on the success probability of the protocol, which depend on rigorously defined measures of coherence as a dynamical resource. We compare these bounds with the classical limit of the protocol and conclude that within the fixed structure that we consider, coherence is the quantum resource that determines its performance by bounding the success probability from below and above. Therefore, we shine new light on the fundamental role of coherence in quantum computation.

arXiv:2203.10632•Physical Review Letters•Sep 13, 2022•67 citations

Coherence dynamics in Simon's quantum algorithm

Linlin Ye, Zhaoqi Wu, Shao-Ming Fei

Quantum coherence plays a pivotal role in quantum algorithms. We study the coherence dynamics of the evolved states in Simon's quantum algorithm based on Tsallis relative $α$ entropy and $l_{1,p}$ norm. We prove that the coherences of the first register and the second register both rely on the dimension $N$ of the state spaces of the $n$ qubit systems, and increase with the increase of $N$. We show that the oracle operator $O$ does not change the coherence. Moreover, we study the coherence dynamics in the Simon's quantum algorithm and prove that in overall the coherence is in production when $N>4$ and in depletion when $N<4$.

quant-pharXiv:2604.16190•Europhysics Letters (EPL)•Apr 20, 2026•6 citations

Simulation of a Quantum Prime Factoring Algorithm

Elizabeth Ellen Parsons

The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.

•Jan 1, 2016•0 citations

Entanglement in Shor's Factoring Algorithm

Jianing Tan, Zhihao Liu, Hanwu Chen

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.

•Mar 28, 2020•0 citations

Coherence Depletion in Quantum Algorithms

Ye-Chao Liu, Jiangwei Shang, Xiangdong Zhang

Besides the superior efficiency compared to their classical counterparts, quantum algorithms known so far are basically task-dependent, and scarcely any common features are shared between them. In this work, however, we show that the depletion of quantum coherence turns out to be a common phenomenon in these algorithms. For all the quantum algorithms that we investigated, including Grover's algorithm, Deutsch-Jozsa algorithm, and Shor's algorithm, quantum coherence of the system states reduces to the minimum along with the successful execution of the respective processes. Notably, a similar conclusion cannot be drawn using other quantitative measures such as quantum entanglement. Thus, we expect that coherence depletion as a common feature can be useful for devising new quantum algorithms in the future.

arXiv:1808.02222•Entropy•Mar 7, 2019•22 citations
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.
Quantum computers leverage the principles of quantum mechanics to solve complex problems beyond the capabilities of classical computers, such as prime factorization, which poses a significant threat to cryptographic algorithms like RSA and ECC. Although current quantum resources are insufficient for effective decryption, ongoing research focuses on optimizing Shor's algorithm to overcome these limitations. Shor's algorithm, a quantum algorithm designed for efficient integer factorization, exploits quantum parallelism and entanglement to perform prime factorization exponentially faster than classical algorithms. This paper reviews recent trends in Shor algorithm optimization, particularly in enhancing the efficiency of ripple-carry operators and the Karatsuba algorithm in multiplication and proposes a multiplication method that applies the Strassen algorithm to constant adders
Shor's factoring algorithm provides a superpolynomial speedup over all known classical factoring algorithms. Here, we address the question of which quantum properties fuel this advantage. We investigate a sequential variant of Shor's algorithm with a fixed overall structure and identify the role of coherence for this algorithm quantitatively. We analyze this protocol in the framework of dynamical resource theories, which capture the resource character of operations that can create and detect coherence. This allows us to derive a lower and an upper bound on the success probability of the protocol, which depend on rigorously defined measures of coherence as a dynamical resource. We compare these bounds with the classical limit of the protocol and conclude that within the fixed structure that we consider, coherence is the quantum resource that determines its performance by bounding the success probability from below and above. Therefore, we shine new light on the fundamental role of coherence in quantum computation.
Quantum coherence plays a pivotal role in quantum algorithms. We study the coherence dynamics of the evolved states in Simon's quantum algorithm based on Tsallis relative ααα entropy and l1,pl_{1,p}l1,p​ norm. We prove that the coherences of the first register and the second register both rely on the dimension NNN of the state spaces of the nnn qubit systems, and increase with the increase of NNN. We show that the oracle operator OOO does not change the coherence. Moreover, we study the coherence dynamics in the Simon's quantum algorithm and prove that in overall the coherence is in production when N>4N>4N>4 and in depletion when N<4N<4N<4.
The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.
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.
Besides the superior efficiency compared to their classical counterparts, quantum algorithms known so far are basically task-dependent, and scarcely any common features are shared between them. In this work, however, we show that the depletion of quantum coherence turns out to be a common phenomenon in these algorithms. For all the quantum algorithms that we investigated, including Grover's algorithm, Deutsch-Jozsa algorithm, and Shor's algorithm, quantum coherence of the system states reduces to the minimum along with the successful execution of the respective processes. Notably, a similar conclusion cannot be drawn using other quantitative measures such as quantum entanglement. Thus, we expect that coherence depletion as a common feature can be useful for devising new quantum algorithms in the future.