We settle the problem of estimating the trace distance and (square root) fidelity between $n$-qubit pure quantum states to within additive error $\varepsilon$, 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/\varepsilon^2)$, improving the long-standing folklore with sample complexity $O(1/\varepsilon^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|ψ\rangle\!\langleψ|$ can be converted to a $δ$-close (in the diamond norm distance) quantum sample algorithm using $Θ(Q^2/δ)$ samples of the state $|ψ\rangle$. This samplizer for pure states is also shown to be optimal.
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.
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.
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)queriestotheirstate−preparationcircuits,quadraticallyimprovingthelong−standingfolkloreO(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.
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.
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including:
1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr(ρ2) and the inner product tr(ρσ).
2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr(ρk).
3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal.
4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state.
5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states.
6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal.
To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error ε. We show that the sample complexity is O(r2/ε2) with optimal ε-dependence when the reference state is of rank r, improving the previous best O(r2log2(1/ε)/ε4) due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of Ω(r/ε2), improving the previous best Ω(r/ε+1/ε2), with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most r while the reference state can be arbitrary, for which the sample complexity is shown to be O(r2/ε4). As an application, we present an approach to tolerant quantum state certification, generalizing the exact certification studied in Bădescu, O'Donnell, and Wright (STOC 2019).
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.