Coherence as a Resource for Shor’s Algorithm
- 13 September 2022
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 129 (12) , 120501
Abstract
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.Keywords
Funding Information
- Consejo Nacional de Investigaciones Científicas y Técnicas
- Pacific Institute for the Mathematical Sciences
This publication has 78 references indexed in Scilit:
- (QUANTUMNESS IN THE CONTEXT OF) RESOURCE THEORIESInternational Journal of Modern Physics B, 2012
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Transforming quantum operations: Quantum supermapsEurophysics Letters, 2008
- On the capacities of bipartite hamiltonians and unitary gatesIEEE Transactions on Information Theory, 2003
- Reversible transformations from pure to mixed states and the unique measure of informationPhysical Review A, 2003
- Efficient Factorization with a Single Pure Qubit andMixed QubitsPhysical Review Letters, 2000
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric conesOptimization Methods and Software, 1999
- Quantifying EntanglementPhysical Review Letters, 1997
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978