Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
arXiv:2001.04486 · doi:10.1038/s41598-020-80153-z
Abstract
Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.
arXiv comment6 pages, 2 figures
References in corpus (39)
- Quantum entanglement
- Quantum Mechanics helps in searching for a needle in a haystack
- Efficient classical simulation of slightly entangled quantum computations
- Quantum Coherence as a Resource
- Quantum metrology with nonclassical states of atomic ensembles
- Strengths and Weaknesses of Quantum Computing
- Quantum discord and the power of one qubit
- Entanglement, Non-linear Dynamics, and the Heisenberg Limit
- Quantum metrology from a quantum information science perspective
- On the role of entanglement in quantum computational speed-up
- Grover's quantum searching algorithm is optimal
- Contextuality supplies the magic for quantum computation
- Fisher information and multiparticle entanglement
- Multipartite entanglement and high precision metrology
- Global entanglement in multiparticle systems
- Fisher Information and entanglement of non-Gaussian spin states
- Converting Coherence to Quantum Correlations
- How to quantify coherence: Distinguishing speakable and unspeakable notions
- Extending Noether's theorem by quantifying the asymmetry of quantum states
- Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
- Quantum Algorithms: Entanglement Enhanced Information Processing
- Coherence depletion in the Grover quantum search algorithm
- Implementation of quantum search algorithm using classical Fourier optics
- Quantum search without entanglement
- Universal quantum computation with little entanglement
- Good dynamics versus bad kinematics. Is entanglement needed for quantum computation?
- Quantum Computing Without Entanglement
- Multipartite entanglement in quantum algorithms
- Witnessing Multipartite Entanglement without Entanglement Witness Operators
- Quantum correlations and distinguishability of quantum states
- Statistical speed of quantum states: Generalized quantum Fisher information and Schatten speed
- The elusive source of quantum effectiveness
- Quantum interference as a resource for quantum speedup
- Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
- Scale invariance of entanglement dynamics in Grover's quantum search algorithm
- The Degree of Quantum Correlation Required to Speed-Up a Computation
- Grover's search with local and total depolarizing channel errors
- State complexity and quantum computation
- Fault-ignorant Quantum Search