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•67 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•0 citations

Bounds on positive operator-valued measure based coherence of superposition

Meng‐Li Guo, Jin‐Min Liang, Bo Li +2 more

Quantum coherence is a fundamental feature of quantum physics and plays a significant role in quantum information processing. By generalizing the resource theory of coherence from von Neumann measurements to positive operator-valued measures (POVMs), POVM-based coherence measures have been proposed with respect to the relative entropy of coherence, the l 1 norm of coherence, the robustness of coherence and the Tsallis relative entropy of coherence. We derive analytically the lower and upper bounds on these POVM-based coherence of an arbitrary given superposed pure state in terms of the POVM-based coherence of the states in superposition. Our results can be used to estimate range of quantum coherence of superposed states. Detailed examples are presented to verify our analytical bounds.

arXiv:2305.06705•Chinese Physics B•Feb 8, 2023•1 citation

Quantifying computational advantage of Grover’s algorithm with the trace speed

Valentin Gebhart, Luca Pezzè, Augusto Smerzi

Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.

arXiv:2001.04486•Scientific Reports•Jan 14, 2021•11 citations

Imaginarity as a resource in Shor's algorithm

Linlin Ye, Chuanfa Wu, Zhaoqi Wu +1 more

We investigate the sequential version of Shor's order-finding algorithm from the perspective of the imaginarity of quantum channels. By fixing an eigenbranch of the modular multiplication unitary and a target output path, the process is effectively decomposed into a real diagonal factor and a residual phase channel. We find that for the ideal residual phase channel, the three trace-norm induced imaginarity measures are all equal. On good output paths, a smaller residual imaginarity corresponds to a higher single-block success probability. By combining the branch-wise probabilities, we obtain the exact ideal success probability of the sequential order-finding protocol and derive lower and upper bounds in terms of residual phase-channel imaginarity. We further extend the analysis to noisy residual phase channels, and obtain the lower and upper bounds on the noisy success probability. These results clarify the role of imaginarity of channels in Shor's algorithm and provide a refined perspective on quantum-resource behavior in ideal and noisy sequential quantum algorithms.

quant-pharXiv:2610.04443•Oct 6, 2026•0 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.
Quantum coherence is a fundamental feature of quantum physics and plays a significant role in quantum information processing. By generalizing the resource theory of coherence from von Neumann measurements to positive operator-valued measures (POVMs), POVM-based coherence measures have been proposed with respect to the relative entropy of coherence, the l 1 norm of coherence, the robustness of coherence and the Tsallis relative entropy of coherence. We derive analytically the lower and upper bounds on these POVM-based coherence of an arbitrary given superposed pure state in terms of the POVM-based coherence of the states in superposition. Our results can be used to estimate range of quantum coherence of superposed states. Detailed examples are presented to verify our analytical bounds.
Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.
We investigate the sequential version of Shor's order-finding algorithm from the perspective of the imaginarity of quantum channels. By fixing an eigenbranch of the modular multiplication unitary and a target output path, the process is effectively decomposed into a real diagonal factor and a residual phase channel. We find that for the ideal residual phase channel, the three trace-norm induced imaginarity measures are all equal. On good output paths, a smaller residual imaginarity corresponds to a higher single-block success probability. By combining the branch-wise probabilities, we obtain the exact ideal success probability of the sequential order-finding protocol and derive lower and upper bounds in terms of residual phase-channel imaginarity. We further extend the analysis to noisy residual phase channels, and obtain the lower and upper bounds on the noisy success probability. These results clarify the role of imaginarity of channels in Shor's algorithm and provide a refined perspective on quantum-resource behavior in ideal and noisy sequential quantum algorithms.