Quantum computation speedup limits from quantum metrological precision bounds

Understand

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.