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.
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.
Quantum precision enhancement is of fundamental importance for the development of advanced metrological optical experiments, such as gravitational wave detection and frequency calibration with atomic clocks. Precision in these experiments is strongly limited by the 1/√N shot noise factor with N being the number of probes (photons, atoms) employed in the experiment. Quantum theory provides tools to overcome the bound by using entangled probes. In an idealized scenario this gives rise to the Heisenberg scaling of precision 1/N. Here we show that when decoherence is taken into account, the maximal possible quantum enhancement in the asymptotic limit of infinite N amounts generically to a constant factor rather than quadratic improvement. We provide efficient and intuitive tools for deriving the bounds based on the geometry of quantum channels and semi-definite programming. We apply these tools to derive bounds for models of decoherence relevant for metrological applications including: depolarization, dephasing, spontaneous emission and photon loss. Quantum metrology employs the properties of quantum states to further enhance the accuracy of some of the most precise measurement schemes to date. Here, a method for estimating the upper bounds to achievable precision in quantum-enhanced metrology protocols in the presence of decoherence is presented.
Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
We show that quantification of the performance of quantum-enhanced measurement schemes based on the concept of quantum Fisher information (QFI) yields results that are asymptotically equivalent to those from the rigorous Bayesian approach, provided generic uncorrelated noise is present in the setup. At the same time, we show that for the problem of decoherence-free phase estimation this equivalence breaks down, and the achievable estimation uncertainty calculated within the Bayesian approach is larger by a factor of π than that predicted from the QFI even in the large prior knowledge (small parameter fluctuation) regime, where the QFI is conventionally regarded as a reliable figure of merit. We conjecture that an analogous discrepancy is present in the arbitrary decoherence-free unitary parameter estimation scheme, and propose a general formula for the asymptotically achievable precision limit. We also discuss protocols utilizing states with an indefinite number of particles, and show that within the Bayesian approach it is legitimate to replace the number of particles with the mean number of particles in the formulas for the asymptotic precision, which as a consequence provides another argument for proposals based on the properties of the QFI of indefinite particle number states leading to sub-Heisenberg precisions not being practically feasible.
In an idealistic setting, quantum metrology protocols allow to sense physical parameters with mean squared error that scales as 1/N2 with the number of particles involved---substantially surpassing the 1/N-scaling characteristic to classical statistics. A natural question arises, whether such an impressive enhancement persists when one takes into account the decoherence effects that are unavoidable in any real-life implementation. In this thesis, we resolve a major part of this issue by describing general techniques that allow to quantify the attainable precision in metrological schemes in the presence of uncorrelated noise. We show that the abstract geometrical structure of a quantum channel describing the noisy evolution of a single particle dictates then critical bounds on the ultimate quantum enhancement. Our results prove that an infinitesimal amount of noise is enough to restrict the precision to scale classically in the asymptotic N limit, and thus constrain the maximal improvement to a constant factor. Although for low numbers of particles the decoherence may be ignored, for large N the presence of noise heavily alters the form of both optimal states and measurements attaining the ultimate resolution. However, the established bounds are then typically achievable with use of techniques natural to current experiments. In this work, we thoroughly introduce the necessary concepts and mathematical tools lying behind metrological tasks, including both frequentist and Bayesian estimation theory frameworks. We provide examples of applications of the methods presented to typical qubit noise models, yet we also discuss in detail the phase estimation tasks in Mach-Zehnder interferometry both in the classical and quantum setting---with particular emphasis given to photonic losses while analysing the impact of decoherence.
Abstract Quantum metrology can achieve far better precision than classical metrology, and is one of the most important applications of quantum technologies in the real world. To attain the highest precision promised by quantum metrology, all steps of the schemes need to be optimized, which include the state preparation, parametrization, and measurement. Here the recent progresses on the optimization of these steps, which are essential for the identification and achievement of the ultimate precision limit in quantum metrology, are reviewed. It is hoped this provides a useful reference for the researchers in quantum metrology and related fields.
Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.