Quantum computation speedup limits from quantum metrological precision bounds
arXiv:1412.6111 · doi:10.1103/PhysRevA.91.062322
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.
arXiv comment6 pages, 2 figures
References in corpus (26)
- Advances in Quantum Metrology
- Quantum metrology
- Strengths and Weaknesses of Quantum Computing
- On the Improvement of Frequency Stardards with Quantum Entanglement
- General framework for estimating the ultimate precision limit in noisy quantum-enhanced metrology
- Quantum metrology from a quantum information science perspective
- The elusive Heisenberg limit in quantum enhanced metrology
- Grover's quantum searching algorithm is optimal
- Quantum speed limit for physical processes
- Optimal Quantum Phase Estimation
- Quantum limits to dynamical evolution
- Using entanglement against noise in quantum metrology
- Scaling laws for precision in quantum interferometry and bifurcation landscape of optimal state
- Efficient tools for quantum metrology with uncorrelated noise
- Extremal properties of the variance and the quantum Fisher information
- True precision limits in quantum metrology
- Phase estimation without a priori knowledge in the presence of loss
- Effects of Noisy Oracle on Search Algorithm Complexity
- Quantum states made to measure
- The effect of unitary noise on Grover's quantum search algorithm
- Noise effect on Grover algorithm
- Noise in Grover's Quantum Search Algorithm
- Quantum Search with General Nonlinearities
- Decoherence on Grover's quantum algorithm: perturbative approach
- Precision bounds in noisy quantum metrology
- Fault-ignorant Quantum Search
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