Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Wang Fang, Qisheng WangarXiv 2025 · DOI · arXiv

TL;DR

Researchers have developed a query-optimal quantum algorithm that estimates the fidelity between a mixed quantum state and a pure state with a quadratic speedup over traditional methods. By leveraging purified quantum query access and square-root amplitude estimation, the algorithm achieves a complexity of $\Theta(1/\epsilon)$, reaching the theoretical lower bound for this problem.

What Problem Does This Paper Address?

In quantum information, fidelity is the standard metric for measuring how "close" two quantum states are. While calculating fidelity between two pure states is relatively straightforward, doing so for mixed states (which represent statistical ensembles of pure states) is significantly more complex. In fact, general mixed-state fidelity estimation is known to be "QSZK-hard," meaning it's likely impossible to solve efficiently on a quantum computer for arbitrary states.

The specific challenge addressed here is the intermediate case: estimating the fidelity between a mixed state ($\rho$) and a pure state ($\sigma = |\psi\rangle\langle\psi|$). The "folklore" approach—using the well-known SWAP test—requires $O(1/\epsilon^2)$ queries to reach an additive error of $\epsilon$. The authors sought to determine if a faster, optimal approach existed.

Methods

The authors utilize the purified quantum query access model. In this setup, the algorithm has access to a unitary oracle that prepares a "purification" of the mixed state (essentially treating the mixed state as part of a larger, pure system).

The core of their approach involves:

  1. Amplitude Encoding: Instead of using the SWAP test (which encodes fidelity into a probability), they design a quantum circuit $W$ that encodes the fidelity value directly into the amplitude of a specific quantum state.
  2. Square Root Amplitude Estimation: By using a specialized version of amplitude estimation (Theorem 3.2), they can extract this encoded amplitude with $O(1/\epsilon)$ queries.
  3. Generalization: They extend this technique to estimate a less common but mathematically interesting quantity, $\sqrt{\text{tr}(\rho\sigma^2)}$, which reduces to standard fidelity when $\sigma$ is pure.

Datasets

As a theoretical paper focused on quantum algorithm design and query complexity, no empirical datasets or benchmarks were used. The results are proven mathematically rather than through numerical simulation or hardware execution.

Key Insights and Ideas

  • Moving from Probabilities to Amplitudes: The "aha moment" is the realization that the $O(1/\epsilon^2)$ bottleneck in the SWAP test comes from estimating a probability. By restructuring the circuit to encode the value as a quantum amplitude, they can apply Grover-like speedups to achieve $O(1/\epsilon)$.
  • Purified Access is Key: The algorithm relies on the ability to query the preparation of the state's purification. This is a standard assumption in many modern quantum algorithms (like those for Hamiltonian simulation) but is more powerful than simply having "samples" of a state.
  • Proven Optimality: The authors don't just provide a faster algorithm; they provide a matching lower bound. They prove that any algorithm estimating this fidelity requires at least $\Omega(1/\epsilon)$ queries, meaning their algorithm cannot be improved further in terms of scaling.

Key Results

  • Quadratic Speedup: The algorithm improves the query complexity from the traditional $O(1/\epsilon^2)$ to an optimal $O(1/\epsilon)$.
  • Query Optimality: The paper establishes that $\Theta(1/\epsilon)$ is the fundamental limit for estimating fidelity to a pure state, regardless of the rank of the mixed state.
  • New Estimator: The authors introduced a query-optimal method for the quantity $\sqrt{\text{tr}(\rho\sigma^2)}$, which may have independent applications in quantum property testing.
Condition Previous Best (Queries) This Work (Queries)
One state is pure $O(1/\epsilon^2)$ $\Theta(1/\epsilon)$ (Optimal)
Both states are pure $\Theta(1/\epsilon)$ $\Theta(1/\epsilon)$ (Generalizes)

Limitations and Future Work

  • The "Pure State" Constraint: The $O(1/\epsilon)$ scaling specifically requires at least one of the two states to be pure. Estimating fidelity between two arbitrary mixed states remains a much harder problem (QSZK-hard).
  • Sample Complexity: This work focuses on query complexity (how many times we call the preparation circuit). The authors suggest that future research could investigate whether a similar optimal scaling can be achieved in terms of sample complexity (using physical copies of the state).
  • Frobenius Norm: The authors pose an open question: can these amplitude encoding techniques be adapted to estimate the Frobenius norm ($\|\rho\|_F = \sqrt{\text{tr}(\rho^2)}$) with similar efficiency?

Summary updated

Abstract

We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error ε by using Θ(1/ε) queries to their state-preparation circuits, achieving a quadratic speedup over the folklore O(1/ε²). Our approach is technically simple, and can moreover estimate the quantity √{tr(ρσ²)} that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.
BibTeX
@misc{fang2025optimal,
  author = {Wang Fang and Qisheng Wang},
  title = {{Optimal Quantum Algorithm for Estimating Fidelity to a Pure State}},
  year = {2025},
  eprint = {2506.23650},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.23650},
  howpublished = {arXiv},
}
Figure