When evaluating the performance of quantum devices or validating quantum algorithms, we fundamentally need to answer a geometric question: how close is our prepared quantum state to the target state? This question is typically formalized using metrics like state fidelity, trace distance, or statistical divergences.
Traditionally, estimating these properties to an additive precision of $\epsilon$ required a sample or query complexity that scaled as $O(1/\epsilon^2)$. This scaling is a direct consequence of the standard quantum limit—the inherent shot noise that arises when reconstructing a continuous value from discrete measurement outcomes.
However, a recent wave of quantum algorithms has bypassed this bottleneck, achieving the absolute physical limit of $\epsilon$-precision: a query complexity of $\Theta(1/\epsilon)$. The core intuition behind this quadratic speedup lies in a paradigm shift from probability-based sampling to amplitude-based encoding.
The Precision Bottleneck: Why Sampling Scales as $1/\epsilon^2$
To understand why traditional methods are slow, consider a naive approach to estimating the fidelity $F$ between two states. Suppose we design a quantum circuit where the probability of measuring a specific basis state (say, $|0\rangle$) is exactly equal to $F$.
When we run this circuit and observe the outcomes, we are sampling from a Bernoulli distribution. According to the central limit theorem, the standard deviation of our estimate after $N$ samples scales as $1/\sqrt{N}$. To suppress this statistical fluctuation down to a desired error tolerance of $\epsilon$, we must collect enough samples such that $1/\sqrt{N} \le \epsilon$, which forces the number of samples to scale as:
$$N = \Omega\left(\frac{1}{\epsilon^2}\right)$$
This $1/\epsilon^2$ scaling is a hard floor for any algorithm that collapses the quantum state into a classical probability distribution before performing estimation. As shown by Yong Wang et al. in Efficient factored gradient descent algorithm for quantum state tomography, even sophisticated classical optimization techniques like factored gradient descent for full state tomography ultimately operate within this standard statistical framework, optimizing the infidelity scaling relative to the total number of collected measurement samples $N$.
The Core Mechanism: Amplitude-Based Encoding
To break past the $1/\epsilon^2$ barrier, we must avoid converting the target metric into a measurement probability early in the circuit. Instead, we can construct a unitary operator that maps the metric directly to the quantum amplitude of a state.
As detailed by Wang Fang in Optimal Quantum Algorithm for Estimating Fidelity to a Pure State, if we have purified query access to our quantum states, we can design a circuit that outputs a state of the form:
$$|\Psi\rangle = \sqrt{F}|0\rangle|\phi_0\rangle + \sqrt{1-F}|1\rangle|\phi_1\rangle$$
Here, the fidelity $F$ is encoded directly as an amplitude $\sqrt{F}$, rather than a probability.
Once the property is locked into a quantum amplitude, we can exploit coherent quantum evolution. Instead of measuring $|\Psi\rangle$ immediately, we treat it as a subspace inside a larger Hilbert space and apply a sequence of quantum reflections—a technique known as Amplitude Estimation.
Each pair of reflections rotates the state within this two-dimensional subspace by an angle directly proportional to $\theta = \arcsin(\sqrt{F})$. By applying this unitary rotation $T$ times coherently, the total rotation angle becomes $T\theta$. Crucially, the error in estimating a phase or rotation angle via quantum phase estimation scales as $1/T$. Therefore, to resolve the underlying amplitude to an accuracy of $\epsilon$, we only need the number of coherent operations to scale as:
$$T = \Theta\left(\frac{1}{\epsilon}\right)$$
This mechanism yields a quadratic speedup over classical sampling. Wang Fang leveraged this exact framework to show that the fidelity between a mixed state and a pure state can be estimated using only $\Theta(1/\epsilon)$ queries, proving that this matches the fundamental theoretical lower bound for property estimation.
Classical Sampling:
[State Preparation] -> [Measurement] -> [Classical Bit] === (Repeat 1/ε² times) ===> Estimate
Amplitude Encoding:
[State Preparation] -> [Coherent Reflections (1/ε times)] -> [Measurement] ========> Estimate
Proving the Fundamental Limits
Is it possible to do even better than $1/\epsilon$? The short answer is no. To prove that $\Theta(1/\epsilon)$ is the absolute physical floor, researchers use reductions from fundamental query complexity problems, such as distinguishing between two slightly biased probability distributions.
In Optimal Trace Distance and Fidelity Estimations for Pure Quantum States, Qisheng Wang established matching lower bounds for both trace distance and square-root fidelity estimation between pure states. By proving that any quantum query algorithm requires at least $\Omega(1/\epsilon)$ queries to achieve an additive error of $\epsilon$, the author confirmed that amplitude-encoded algorithms are asymptotically optimal.
This linear precision scaling is not limited to simple pure states. By utilizing advanced algebraic frameworks like block-encodings and the Quantum Singular Value Transformation (QSVT), Nana Liu et al. in Quantum algorithms for matrix geometric means extended this optimal $O(1/\epsilon)$ scaling to highly non-linear matrix operations, including the computation of matrix geometric means and Rényi entropies.
Extending to Distributions and Divergences
The power of amplitude encoding extends beyond purely quantum states into the domain of classical statistics. Classical probability distributions can be encoded as quantum states where the amplitudes correspond to the square roots of the probabilities:
$$|P\rangle = \sum_{i} \sqrt{p_i} |i\rangle$$
Once a classical distribution is mapped to a quantum state in this manner, the statistical distance between two distributions translates directly into the geometric distance between two quantum state vectors.
Using this mapping, András Gilyén et al. in Distributional property testing in a quantum world demonstrated that testing properties like distribution closeness or independence enjoys a quadratic speedup in query complexity relative to the domain size compared to classical sampling. This builds upon foundational work by Sergey Bravyi 0001 et al. in Quantum Algorithms for Testing Properties of Distributions, which combined classical Monte Carlo methods with quantum counting to compute statistical distances with $O(N^{1/2})$ complexity instead of the linear scaling required classically.
Similarly, in the context of quantum generative modeling, Chiara Leadbeater et al. in F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits showed that evaluating complex statistical metrics like the Pearson divergence on fault-tolerant quantum hardware inherits this exact quadratic acceleration over classical sampling methods.
The Role of State Structure: Rank and Dimension
While amplitude estimation provides an optimal scaling with respect to precision ($\epsilon$), the total sample complexity of a task is often constrained by the geometric and spectral properties of the states themselves—specifically their rank and dimension.
When we move from estimating a single scalar property (like fidelity) to fully certifying or reconstructing a state, the complexity bounds adapt to these structural parameters:
- Entangled vs. Incoherent Measurements: In Sample-optimal tomography of quantum states, Jeongwan Haah et al. demonstrated that "collective" measurements—which measure multiple copies of a state simultaneously in an entangled way—can dramatically reduce sample complexity by incorporating the state's rank as an optimization parameter. This allows low-rank or high-purity states to be reconstructed much faster than rank-agnostic approaches.
- The Curse of Dimensionality: If an experiment is restricted to "incoherent" measurements (measuring only one copy of a state at a time), a fundamental bottleneck emerges. As proven by Jerry Li et al. in Toward Instance-Optimal State Certification With Incoherent Measurements, single-copy measurements suffer from a severe dependence on the total dimension $d$ of the system, even if the target state appears simple or low-rank.
The interplay between these parameters is further highlighted when estimating higher-order properties, such as the trace of state powers $\text{tr}(\rho^q)$. In Improved sample upper and lower bounds for trace estimation of quantum state powers, Kean Chen et al. revealed that the optimal sample complexity exhibits distinct scaling behaviors depending on the power $q$. For $q > 2$, the complexity scales as $\tilde{O}(1/\epsilon^2)$, whereas for $1 < q < 2$, it drops to an improved $\tilde{O}(1/\epsilon)$ upper bound.
Summary
The transition from $O(1/\epsilon^2)$ to $\Theta(1/\epsilon)$ query complexity represents a fundamental shift in how we extract information from quantum systems. By designing circuits that encode target properties directly into quantum amplitudes rather than measurement probabilities, algorithms can utilize coherent reflections to systematically rotate the state toward a measurable target. While practical implementations must still navigate the constraints of state rank, purification costs (as explored by Hongshun Yao et al. in Protocols and trade-offs of quantum state purification), and measurement choices (such as the randomized stabilizer sampling analyzed by Akshay Seshadri et al. in Versatile Fidelity Estimation with Confidence), amplitude-based encoding sets the definitive mathematical benchmark for optimal property estimation.
Key Foundational Work
Quantum Algorithms for Testing Properties of Distributions (2011) — contributed 2 concept elements to this direction.
Sample-Optimal Tomography of Quantum States (2015) — contributed 1 concept elements to this direction.