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:2508.11962 · Chinese Physics B

Coherence and decoherence in generalized Shor’s algorithm

Linlin 琳琳 Ye 叶, Zhaoqi Wu, Nanrun 南润 Zhou 周

Published Feb 11, 2026• 0 citations
arXivHTMLPDF

Abstract

Abstract Quantum coherence constitutes a fundamental physical mechanism essential to the study of quantum algorithms. We study coherence and decoherence in the generalized Shor’s algorithm where the register A is initialized in an arbitrary pure state, or the combined register AB is initialized in a pseudo-pure state, which encompasses the standard Shor’s algorithm as a special case. We derive both lower and upper bounds on the performance of the generalized Shor’s algorithm, and establish the relation between the probability of calculating the order r when register AB is initialized in a pseudo-pure state and that when register A is initialized in an arbitrary pure state. Moreover, we study coherence and decoherence in the noisy Shor’s algorithm and give a lower bound on the probability that we can calculate the order r .

DOI
10.1088/1674-1056/ae445e

Related papers

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

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

Exact results on Quantum search algorithm

Saptarshi Roy Chowdhury, Swarupananda Pradhan

We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.

arXiv:2207.09762•Jul 20, 2022•1 citation

Efficient factorization with a single pure qubit

Scott Parker, Martin Bodo Plenio

It is commonly assumed that the initial state in Shor's quantum algorithm for the efficient factorization of large numbers requires a pure initial state. Here we demonstrate that a single pure qubit together with a collection of qubits in an arbitrary mixed state is sufficient to implement Shor's factorization algorithm efficiently.

•Jan 18, 2000•4 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

Collective decoherence of the superpositional entangled states in the quantum Shor algorithm

G. P. Berman, D. I. Kamenev, V. I. Tsifrinovich

We consider collective decoherence for the quantum Shor algorithm. A quantum computer which interacts with its environment is modeled by a spin-$1∕2$ chain interacting with harmonic oscillators at a given temperature. We calculate the nondiagonal matrix elements of the density matrix which are important for implementation of the quantum Shor algorithm, and study the decay rate and the Lamb phase shift for these elements. It is shown that the probability of superdecoherence in the quantum Shor algorithm is extremely small. The conditions for preserving quantum entanglement are formulated.

Physical Review A•Mar 28, 2005•12 citations
Abstract Quantum coherence constitutes a fundamental physical mechanism essential to the study of quantum algorithms. We study coherence and decoherence in the generalized Shor’s algorithm where the register A is initialized in an arbitrary pure state, or the combined register AB is initialized in a pseudo-pure state, which encompasses the standard Shor’s algorithm as a special case. We derive both lower and upper bounds on the performance of the generalized Shor’s algorithm, and establish the relation between the probability of calculating the order r when register AB is initialized in a pseudo-pure state and that when register A is initialized in an arbitrary pure state. Moreover, we study coherence and decoherence in the noisy Shor’s algorithm and give a lower bound on the probability that we can calculate the order r .
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.
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 generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.
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.
We consider collective decoherence for the quantum Shor algorithm. A quantum computer which interacts with its environment is modeled by a spin-1∕21∕21∕2 chain interacting with harmonic oscillators at a given temperature. We calculate the nondiagonal matrix elements of the density matrix which are important for implementation of the quantum Shor algorithm, and study the decay rate and the Lamb phase shift for these elements. It is shown that the probability of superdecoherence in the quantum Shor algorithm is extremely small. The conditions for preserving quantum entanglement are formulated.