2014/12/31 by Rafał Demkowicz-Dobrzański, Rafal Demkowicz-Dobrzanski, Marcin Markiewicz · 21 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Computer engineering #Computer science #Conjecture #Discrete mathematics #Mathematics #Metrology #Oracle #Parallel computing #Physics #Quadratic equation #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum algorithm #Quantum computer #Quantum decoherence #Quantum mechanics #Quantum metrology #Quantum network #Speedup #Theoretical computer science #quant-ph
paper · pdf · doi:10.1103/physreva.91.062322
published in Physical Review A 91(6) (American Physical Society) · 6 pages, 2 figures
arxiv created 2015/06/17 · openalex publication_date 2015/06/17 · openalex created_date 2016/06/24 · arxiv updated 2016/10/13 · openalex updated_date 2026/08/05
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 the presence of decoherence to infer an analogous generic loss of quadratic speedup 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 deep insight into the relationship between quantum algorithms and quantum metrology protocols.