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.

arXiv comment5+24 pages

References in corpus (67)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Quantifying Coherence
• Quantifying Entanglement
• Quantum Coherence as a Resource
• Entanglement Measures and Purification Procedures
• Quantum Resource Theories
• Measuring Quantum Coherence with Entanglement
• On the Power of One Bit of Quantum Information
• Quantum Networks for Elementary Arithmetic Operations
• On the role of entanglement in quantum computational speed-up
• Robustness of coherence: An operational and observable measure of quantum coherence
• The Resource Theory of Stabilizer Computation
• The resource theory of quantum reference frames: manipulations and monotones
• Semiclassical Fourier Transform for Quantum Computation
• How to quantify coherence: Distinguishing speakable and unspeakable notions
• Transforming quantum operations: quantum supermaps
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• Robustness of asymmetry and coherence of quantum states
• (Quantumness in the context of) Resource Theories
• Efficient Networks for Quantum Factoring
• Quantum speed limits, coherence and asymmetry
• Measuring the quality of a quantum reference frame: the relative entropy of frameness
• Reversible transformations from pure to mixed states, and the unique measure of information
• The theory of manipulations of pure state asymmetry: basic tools and equivalence classes of states under symmetric operations
• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Coherence depletion in the Grover quantum search algorithm
• Cohering and de-cohering power of quantum channels
• Resource Destroying Maps
• Quantifying quantum resources with conic programming
• On the capacities of bipartite Hamiltonians and unitary gates
• Operational Advantage of Quantum Resources in Subchannel Discrimination
• Quantum processes which do not use coherence
• All sets of incompatible measurements give an advantage in quantum state discrimination
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Quantifying the magic of quantum channels
• Operational Resource Theory of Quantum Channels
• Quantifying Operations with an Application to Coherence
• Quantifying Contextuality
• A resource theory of quantum memories and their faithful verification with minimal assumptions
• Resource Theory of Coherence - Beyond States
• How to quantify a dynamical quantum resource
• Using and reusing coherence to realize quantum processes
• Robustness of Measurement, discrimination games and accessible information
• Resource theory of non-Gaussian operations
• Interferometric visibility and coherence
• Cohering power of quantum operations
• Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers
• Application of the Resource Theory of Channels to Communication Scenarios
• Resource theory of asymmetric distinguishability for quantum channels
• All quantum resources provide an advantage in exclusion tasks
• Coherence and non-classicality of quantum Markov processes
• Optimal resource cost for error mitigation
• Dynamical Resource Theory of Quantum Coherence
• Operational interpretation of weight-based resource quantifiers in convex quantum resource theories of states
• Dynamical Entanglement
• Entanglement of a bipartite channel
• Quantifying the resource content of quantum channels: An operational approach
• Coherence distillation machines are impossible in quantum thermodynamics
• Quantifying the Nonclassicality of Operations
• Experimental quantification of coherence of a tunable quantum detector
• Operational characterization of incompatibility of quantum channels with quantum state discrimination
• Quantifying dynamical coherence with dynamical entanglement
• Of Local Operations and Physical Wires
• Coherence of operations and interferometry
• Coherence Depletion in Quantum Algorithms
• 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