Coherence as a Resource for Shor’s Algorithm

Felix Ahnefeld, Thomas Theurer, Dario Egloff, Juan Mauricio Matera, and Martin B. Plenio
Phys. Rev. Lett. 129, 120501 – Published 13 September 2022
PDFHTMLExport Citation

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.

  • Figure
  • Received 26 March 2022
  • Revised 10 July 2022
  • Accepted 1 August 2022

DOI:https://doi.org/10.1103/PhysRevLett.129.120501

© 2022 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & TechnologyGeneral Physics

Authors & Affiliations

Felix Ahnefeld1,*, Thomas Theurer2,†, Dario Egloff3,‡, Juan Mauricio Matera4,§, and Martin B. Plenio1,∥

  • 1Institute of Theoretical Physics, Universität Ulm, Albert-Einstein-Allee 11, D-89081 Ulm, Germany
  • 2Department of Mathematics and Statistics, Institute for Quantum Science and Technology, University of Calgary, Alberta T2N 1N4, Canada
  • 3Institute of Theoretical Physics, Technical University Dresden, D-01062 Dresden, Germany
  • 4IFLP-CONICET, Departamento de Física, Facultad de Ciencias Exactas, Universidad Nacional de La Plata, C.C. 67, La Plata 1900, Argentina

  • *Corresponding author. felix.ahnefeld@uni-ulm.de
  • thomas.theurer@ucalgary.ca
  • dario.egloff@mailbox.tu-dresden.de
  • §matera@fisica.unlp.edu.ar
  • martin.plenio@uni-ulm.de

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 129, Iss. 12 — 16 September 2022

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×