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 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.
The execution cost of quantum algorithms is typically quantified through asymptotic gate counts and qubit register sizes, yet these metrics do not directly capture which genuinely quantum resources, and in what amount, must be created and maintained for the computation to succeed. The systematic quantification of such information-theoretic requirements in quantum computing protocols remains an extremely challenging open problem, despite their direct role in establishing quantum advantage. To address this gap, we investigate the generation of non-stabilizerness (or magic), one of the key resources, in the paradigmatic Shor's factoring algorithm, revealing a deep connection between intrinsic quantum complexity and the computational hardness of the underlying number-theoretic problem. By developing an explicit analytic theory, we demonstrate the fundamental role of magic in the successful execution of the algorithm, and show that Shor's routine maximally exploits the quantum resource in practically relevant regimes. Our findings create a concise conceptual link between the classical algorithmic difficulty of a task and the non-stabilizer price to solve it on quantum hardware, complementing standard circuit-cost analyses with a resource-based metric that is naturally aligned with the real bottlenecks of fault-tolerant quantum computing.
Quantum physics currently provides our deepest description of nature. To understand precisely how it differs from classical physics is not only of foundational interest, but also important to advance technology: the advent of quantum information has led to the insight that certain quantum phenomena, e.g., entanglement and coherence, are resources which enable us to solve practical tasks that are unsolvable within the realm of classical physics. But how can we quantify quantum resources and how do we decide which resource is relevant for a specific operational advantage in quantum cryptography, quantum computation, or quantum metrology? How can we employ these resources optimally? Addressing these questions is the motivation for the development of quantum resource theories, a mathematically rigorous framework that allows us to investigate a specific quantum phenomenon as a resource. Formally, such theories emerge from restrictions which are imposed in addition to the laws of quantum mechanics. A prominent example is the restriction to local operations and classical communication, which singles out entanglement as a resource. Typically, such theories describe the value of quantum states, i.e., static resources. An important question in such theories concerns their structure as determined by the restriction under consideration, which is analyzed for coherence theory on qubits in this thesis. Only recently, so-called dynamical resource theories that quantify the value of operations were proposed, which are advantageous for several reasons: they include resource theories of states as special cases, allow us to quantify additional quantum properties such as the detection or usage of static resources, which will be a main topic of this thesis, and are more natural from an operational perspective. But are different types of dynamical resources present in quantum operations related? For the case of dynamical coherence and entanglement, it will be shown that there is not only a quantitative, but also a qualitative connection.
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.
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 .
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.
Quantum information science has transformed from a theoretical curiosity to a fundamental concept of associ ated with modern computational complexity theory, primarily because of the recognition that quantum mechanical principles permit the solving of particular issues at an exponentially quicker rate than any conventional classical technique. Shor’s algorithm, which speeds up integer factorization and discrete logarithms by a superpolynomial value, is the best example of this advantage [1]. This poses a direct threat the security of current public-key cryp tographic protocols, such as RSA and Elliptic Curve Cryptography (ECC) [3]. But the world of quantum speedups is not the identical all the time. It consists of everything from Grover’s search algorithm’s quadratic advantages to quantum walks on structured graphs’ exponential hitting times [6]. This report appears at the math behind these speedup paradigms, the hardware they need, and the security problems they might cause, bringing together what we know so far and what we think will happen in the future with quantum-resistant security.