AI summaryⓘ
The authors developed a general method to prove how hard it is to estimate certain properties of quantum states, like how similar two states are or their entropy. They solved some open problems by showing that you need roughly the square of the number of samples, N, to make accurate estimates for these quantum properties. This also implies similar limits for related types of quantum queries. Their results confirm that many quantum algorithms proposed since 2016 are nearly as efficient as possible in this regard.
quantum statesUhlmann fidelitytrace distancevon Neumann entropyquantum algorithmsquery complexitylower boundssample complexityquantum information theory
Abstract
In this paper, we present a unified framework for proving lower bounds for estimating functionals of quantum states. We therefore resolve several open problems by establishing lower bounds that match known upper bounds: we show that it requires $\widetildeΩ(N^2)$ samples to estimate the Uhlmann fidelity, trace distance, and von Neumann entropy. Moreover, they immediately imply matching query lower bounds of $\widetildeΩ(N)$ by quantum sample-to-query lifting. These lower bounds imply the near-optimality of a dozen quantum algorithms since 2016.