For two unknown mixed quantum states$\rho $and$\sigma $in an$N$-dimensional Hilbert space, computing their fidelity$F(\rho,\sigma)$is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem in${\mathrm{ poly}}(\log (N), r, 1/\varepsilon)$time, where$r$is the lower rank of$\rho $and$\sigma $, and$\varepsilon $is the desired precision, provided that the purifications of$\rho $and$\sigma $are prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial in$N$.
For two unknown mixed quantum statesρandσin anN-dimensional Hilbert space, computing their fidelityF(ρ,σ)is a basic problem with many important applications in quantum computing and quantum information, for example verification and characterization of the outputs of a quantum computer, and design and analysis of quantum algorithms. In this paper, we propose a quantum algorithm that solves this problem inpoly(log(N),r,1/ε)time, whereris the lower rank ofρandσ, andεis the desired precision, provided that the purifications ofρandσare prepared by quantum oracles. This algorithm exhibits an exponential speedup over the best known algorithm (based on quantum state tomography) which has time complexity polynomial inN.
The fidelity estimation between two quantum states is crucial for quantum computation and information science. However, an efficacious method for this, especially for mixed states and higher-dimensional density matrices, remains elusive. While there are many existing algorithms on computing the fidelity between two pure states, there is not much work on how to obtain the fidelity between two mixed states. Here, an efficient quantum algorithm for the fidelity estimation is proposed, based primarily on the density matrix exponentiation and interferometeric scheme for mixed states, with a time complexity of O(κ2N2/ε7), where N is the system size, κ is the larger of the condition number of the density matrices and ε is a precision error. This algorithm may serve as a resource-efficient technique to deduce fidelity of any two (pure or mixed) unknown or known quantum states, when the density matrices of the quantum states commute with each other.
Computation of Uhlmann fidelity between many-body mixed states generally involves full diagonalization of exponentially large matrices. In this work, we introduce a polynomial-time algorithm to compute certified lower and upper bounds for the fidelity between matrix product density operators (MPDOs). Our method maps the fidelity estimation problem to a variational optimization of sequential quantum circuits, allowing for systematic improvement of the lower bounds by increasing the circuit depth. Complementarily, we obtain certified upper bounds on fidelity by variational lower bounds on the trace distance through the same framework. We demonstrate the power of this approach with two examples: fidelity correlators in critical mixed states, and codeword distinguishability in an approximate quantum error-correcting code. Remarkably, the variational lower bound accurately track the universal scaling behavior of the fidelity with a size-consistent relative error, allowing for the extraction of previously unknown critical exponents. Our results offer an exponential improvement in precision over known moment-based bounds and establish a scalable framework for the verification of many-body quantum systems.
Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficult to give good estimates of fidelity, especially when one works with mixed states over Hilbert spaces of very high dimension. Although, there has been some progress on fidelity estimation, all prior work either requires a large number of identical copies of the relevant states, or relies on unproven heuristics. In this work, we improve on both of these aspects by developing new and efficient quantum algorithms for fidelity estimation with provable performance guarantees in case at least one of the states is approximately low-rank. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation, as well as density matrix exponentiation and quantum spectral sampling. As a complementary result, we prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general, by giving a sample complexity lower bound that depends polynomially on the dimension. Moreover, if circuit descriptions for the relevant states are provided, we show that the task is hard for the complexity class called (honest verifier) quantum statistical zero knowledge via a reduction to a closely related result by Watrous.
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 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).
Computing quantum state fidelity will be important to verify and characterize states prepared on a quantum computer. In this work, we propose novel lower and upper bounds for the fidelity F ( ρ , σ ) based on the ``truncated fidelity'' F ( ρ m , σ ) , which is evaluated for a state ρ m obtained by projecting ρ onto its m -largest eigenvalues. Our bounds can be refined, i.e., they tighten monotonically with m . To compute our bounds, we introduce a hybrid quantum-classical algorithm, called Variational Quantum Fidelity Estimation, that involves three steps: (1) variationally diagonalize ρ , (2) compute matrix elements of σ in the eigenbasis of ρ , and (3) combine these matrix elements to compute our bounds. Our algorithm is aimed at the case where σ is arbitrary and ρ is low rank, which we call low-rank fidelity estimation, and we prove that no classical algorithm can efficiently solve this problem under reasonable assumptions. Finally, we demonstrate that our bounds can detect quantum phase transitions and are often tighter than previously known computable bounds for realistic situations.