Quantum computation speedup limits from quantum metrological precision bounds

Abstract

We propose a scheme for translating metrological precision bounds into lower bounds on query complexity of quantum search algorithms. Within the scheme the link between quadratic performance enhancement in idealized quantum metrological and quantum computing schemes becomes clear. More importantly, we utilize results from the field of quantum metrology on a generic loss of quadratic quantum precision enhancement in presence of decoherence to infer an analogous generic loss of quadratic speed-up in oracle based quantum computing. While most of our reasoning is rigorous, at one of the final steps, we need to make use of an unproven technical conjecture. We hope that we will be able to amend this deficiency in the near future, but we are convinced that even without the conjecture proven our results provide a novel and deep insight into relationship between quantum algorithms and quantum metrology protocols.

6 pages, 2 figures

References in corpus (8)

• Quantum metrology from a quantum information science perspective
• Quantum speed limit for physical processes
• Optimal Quantum Phase Estimation
• Using entanglement against noise in quantum metrology
• True precision limits in quantum metrology
• Phase estimation without a priori knowledge in the presence of loss
• Noise effect on Grover algorithm
• Precision bounds in noisy quantum metrology

Cited by in corpus (13)

• Macroscopic quantum states: measures, fragility and implementations
• Flexible resources for quantum metrology
• Hamiltonian Simulation with Optimal Sample Complexity
• Probe incompatibility in multiparameter noisy quantum metrology
• Finite-error metrological bounds on the multi-parameter Hamiltonian estimation
• Does a large quantum Fisher information imply Bell correlations?
• Power of One Bit of Quantum Information in Quantum Metrology
• Grover's search with local and total depolarizing channel errors
• Active Learning of Quantum System Hamiltonians yields Query Advantage
• Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
• Quantum noise generated by local random Hamiltonians
• Exploring Many-body Interactions Through Quantum Fisher Information
• Quantum-enhanced mean value estimation via adaptive measurement