On the Role of Coherence in Shor's Algorithm

Abstract

Shor's factoring algorithm provides a super-polynomial speed-up 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.

5+24 pages

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Measuring Quantum Coherence with Entanglement
• The resource theory of quantum reference frames: manipulations and monotones
• Transforming quantum operations: quantum supermaps
• Measuring the quality of a quantum reference frame: the relative entropy of frameness
• All sets of incompatible measurements give an advantage in quantum state discrimination
• Dynamical Entanglement
• Coherence of operations and interferometry
• Multi-object operational tasks for convex quantum resource theories

Cited by in corpus (35)

• Quantum NETwork: from theory to practice
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Experimental certification of contextuality, coherence and dimension in a programmable universal photonic processor
• Coherence and contextuality in a Mach-Zehnder interferometer
• Lower Bounds on Quantum Annealing Times
• Thermal quantum correlations in two gravitational cat states
• Quantum-state texture and gate identification
• Using a resource theoretic perspective to witness and engineer quantum generalized contextuality for prepare-and-measure scenarios
• Tsallis relative $\alpha$ entropy of coherence dynamics in Grover's search algorithm
• Partial coherence versus entanglement
• Cohering and decohering power of massive scalar fields under instantaneous interactions
• Coherence dynamics in quantum algorithm for linear systems of equations
• Coherence Fraction in Grover Search Algorithm
• Frozen condition of quantum coherence
• One-shot manipulation of coherence in dynamic quantum resource theory
• Quantum Speed Limit for Change of Basis
• Coherence via reiterated beam splitting
• Coherence and entanglement dynamics in Shor's algorithm
• Coherence as a resource for phase estimation
• Quantum Coherence and Distinguishability as Complementary Resources: A Resource-Theoretic Perspective from Wave-Particle Duality
• Channel-based framework for phase esimation of multiple eigenvalues
• Entanglement of weighted graphs uncovers transitions in variable-range interacting models
• Non-stabilizerness and entanglement from cat-state injection
• Experimental Catalytic Amplification of Asymmetry
• State convertibility under genuinely incoherent operations
• Basis-independent Coherence in Noninertial Frames
• Coherence of quantum non-Gaussian states via nonlinear absorption of quanta
• Tradeoff between noise and banding in a quantum adder with qudits
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Classical Invasive Description of Informationally-Complete Quantum Processes
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm
• Entanglement as the cross-symmetric part of quantum discord
• Distribution of Non-Locality On Quantum Random Circuits
• Impact of quadrature measurement on quantum coherence
• Quantum coherence and counterdiabatic quantum computing