Measuring the distinguishability between quantum states is a basic problem in quantum information theory. In this paper, we develop optimal quantum algorithms that estimate both the trace distance and the (square root) fidelity between pure states to within additive error$\varepsilon $using$\Theta (1/\varepsilon)$queries to their state-preparation circuits, quadratically improving the long-standing folklore$O(1/\varepsilon ^{2}) $. At the heart of our construction, is an algorithmic tool for quantum square root amplitude estimation, which generalizes the well-known quantum amplitude estimation.
Measuring the distinguishability between quantum states is a basic problem in quantum information theory. In this paper, we develop optimal quantum algorithms that estimate both the trace distance and the (square root) fidelity between pure states to within additive errorεusingΘ(1/ε)queries to their state-preparation circuits, quadratically improving the long-standing folkloreO(1/ε2). At the heart of our construction, is an algorithmic tool for quantum square root amplitude estimation, which generalizes the well-known quantum amplitude estimation.
We settle the problem of estimating the trace distance and (square root) fidelity between n-qubit pure quantum states to within additive error ε, given their independent samples, which was raised as an open question by Wang (IEEE Trans. Inf. Theory 2024). This is achieved by a quantum algorithm with optimal sample complexity Θ(1/ε2), improving the long-standing folklore with sample complexity O(1/ε4). At the heart of our algorithm is a samplized phase estimation of the product of two Householder reflections. This is realized by an improved (multi-)samplizer for pure states, through which any quantum query algorithm using Q queries to the reflection operator I−2∣ψ⟩⟨ψ∣ can be converted to a δ-close (in the diamond norm distance) quantum sample algorithm using Θ(Q2/δ) samples of the state ∣ψ⟩. This samplizer for pure states is also shown to be optimal.
The Uhlmann fidelity F(ρ0,ρ1)=tr∣ρ0ρ1∣ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error ε requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of ρ0 and ρ1. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on 1/ε. However, the known optimal estimator for F(ρ,∣ψ⟩⟨ψ∣) due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure.
In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for F(ρ,∣ψ⟩⟨ψ∣) under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of trA(∣ψ0⟩⟨ψ1∣) (or its inverse) to the reference register R of the purification ∣ψ1⟩ (or ∣ψ0⟩) on the registers A and R, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1), defined via the operator norm ∥A∥∞=σmax(A), given poly(n)-size state-preparation circuits of n-qubit quantum states ρ0 and ρ1. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states:
1. When one state is pure, we establish an optimal quantum estimator using Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5, our estimator runs in poly(n) time. Since the operator norm distance T∞(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩⟨ψ∣,ρ), our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with rank(ρ), which can be exp(n) in general.
2. For general quantum states, we also provide a quantum estimator using O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP-complete and improves the QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε) quantum query complexity lower bound, this leaves only square-root room for improvement.
The key intuition behind our estimators is that, when one state is pure, the pure state ∣ψ⟩ has overlap at least 1/2 with the top unit eigenvector of ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
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.
When it comes to discriminating between two quantum states, trace distance is one of the well-known metrics used in quantum computation and quantum information theory. While there are several quantum algorithms for calculating the trace distance between two quantum states, computing it for any two general density matrices remains computationally demanding. In this paper, we propose a quantum algorithm based on the exponentiation of the density matrix and the improved quantum phase estimation (IQPE) to determine the trace distance for both pure and mixed states, with a time complexity of O(N2/ε6) where N is the number of qubits of the given states and ε is the simulation or estimation precision error. We demonstrate its ability to predict the quantity with proof-of-principle simulations and also quantum hardware computations on the IBM quantum computers, confirming its promise for near-term quantum devices.
In the quantum state distinguishing problem, an algorithm is given copies of a state ∣ψ⟩ or ∣φ⟩ separated by trace distance ε, and tasked with deciding which is the case. It is a standard result that Θ(ε−2) copies are required, while having access to a unitary state preparation oracle and its inverse improves this to Θ(ε−1) queries. We study the intermediate case with forward-only access, capturing scenarios where the oracle is a physical process that cannot be reversed. Tang and Wright recently showed that distinguishing a known state from an \emph{unknown} close state requires Ω(ε−2) forward queries in high dimension; we strengthen this result by proving the same bound even when both states are known, as in the state distinguishing setting. Moreover, our lower bound uses a direct hybrid argument, avoiding advanced compressed oracle techniques used in the prior work. In contrast, we give a dimension-independent algorithm solving a continuous-time variant of state distinguishing with only O(ε−1) total forward evolution time. The algorithm uses quantum Zeno dynamics to confine evolution to a known two-dimensional subspace. Thus, a quadratic advantage survives without inverse access for a natural continuous-time analogue of state distinguishing.