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(N^8)$ where $N$ is the number of qubits of the given states. 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.
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(N8) where N is the number of qubits of the given states. 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.
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.
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.
In quantum information, trace distance is a basic metric of distinguishability between quantum states. However, there is no known efficient approach to estimate the value of trace distance in general. In this paper, we propose efficient quantum algorithms for estimating the trace distance within additive error ε between mixed quantum states of rankr. Specifically, we first provide a quantum algorithm usingr· Õ(1/ε2) queries to the quantum circuits that prepare the purifications of quantum states. Then, we modify this quantum algorithm to obtain another algorithm using Õ (r2/ε5) samples of quantum states, which can be applied to quantum state certification. These algorithms have query/sample complexities that are independent of the dimensionNof quantum states, and their time complexities only incur an extraO(log(N)) factor. In addition, we show that the decision version of low-rank trace distance estimation is BQP-complete.
Abstract Estimating the difference between quantum data is crucial in quantum computing. However, as typical characterizations of quantum data similarity, the trace distance and quantum fidelity are believed to be exponentially-hard to evaluate in general. In this work, we introduce hybrid quantum–classical algorithms for these two distance measures on near-term quantum devices where no assumption of input state is required. First, we introduce the variational trace distance estimation (VTDE) algorithm. We in particular provide the technique to extract the desired spectrum information of any Hermitian matrix by local measurement. A novel variational algorithm for trace distance estimation is then derived from this technique, with the assistance of a single ancillary qubit. Notably, VTDE could avoid the barren plateau issue with logarithmic depth circuits due to a local cost function. Second, we introduce the variational fidelity estimation algorithm. We combine Uhlmann’s theorem and the freedom in purification to translate the estimation task into an optimization problem over a unitary on an ancillary system with fixed purified inputs. We then provide a purification subroutine to complete the translation. Both algorithms are verified by numerical simulations and experimental implementations, exhibiting high accuracy for randomly generated mixed states.
It is known that a reliable geometric quantifier of discord-like correlations can be built by employing the so-called trace distance. This is used to measure how far the state under investigation is from the closest "classical-quantum" one. To date, the explicit calculation of this indicator for two qubits was accomplished only for states such that the reduced density matrix of the measured party is maximally mixed, a class that includes Bell-diagonal states. Here, we first reduce the required optimization for a general two-qubit state to the minimization of an explicit two-variable function. Using this framework, we show next that the minimum can be analytically worked out in a number of relevant cases including quantum-classical and X states. This provides an explicit and compact expression for the trace distance discord of an arbitrary state belonging to either of these important classes of density matrices.
Continuous-variable quantum systems are central to quantum technologies, with Gaussian states playing a key role due to their broad applicability and simple description via first and second moments. Distinguishing Gaussian states requires computing their trace distance, but no analytical formula exists for general states, and numerical evaluation is difficult due to the exponential cost of representing infinite-dimensional operators. We introduce an efficient numerical method to compute the trace distance between a pure and a mixed Gaussian state, based on a generalized Lanczos algorithm that avoids explicit matrix representations and uses only moment information. The technique extends to non-Gaussian states expressible as linear combinations of Gaussian states. We also show how it can yield lower bounds on the trace distance between mixed Gaussian states, offering a practical tool for state certification and learning in continuous-variable quantum systems.