Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2301.06783 · IEEE Transactions on Information Theory

Fast Quantum Algorithms for Trace Distance Estimation

Qisheng Wang, Zhicheng Zhang

Published Oct 2, 2023• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2023.3321121

Related papers

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm 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 ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, 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 ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf 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 $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905•Leibniz international proceedings in informatics•Jul 7, 2026•0 citations

Optimal Trace Distance and Fidelity Estimations for Pure Quantum States

Qisheng Wang

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.

arXiv:2408.16655•IEEE Transactions on Information Theory•Aug 22, 2024•11 citations

Estimation of trace distance between two arbitrary quantum states

Sanchita Ghosh, Anumita Mukhopadhyay, Anindita Bera +2 more

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^2/\varepsilon^6)$ where $N$ is the number of qubits of the given states and $\varepsilon$ 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.

quant-pharXiv:2604.05628•Apr 8, 2026•0 citations

New Quantum Algorithms for Computing Quantum Entropies and Distances

Qisheng Wang, Ji Guan, Junyi Liu +2 more

We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, forN-dimensional quantum states of rankr, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error ε have time complexity of Õ(r/ε2), Õ(r5/ε6) and Õ(r6.5/ε7.5), respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity Ω(N), and the prior best one for fidelity has time complexity Õ(r12.5/ε13.5). The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.

arXiv:2203.13522•IEEE Transactions on Information Theory•May 13, 2024•39 citations

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer

Qisheng Wang, Zhicheng Zhang

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.

arXiv:2410.21201•Leibniz international proceedings in informatics•Oct 28, 2024•0 citations

Estimating Fidelity to a Reference Quantum State

Qisheng Wang

We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\varepsilon$. We show that the sample complexity is $O(r^2/\varepsilon^2)$ with optimal $\varepsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2\log^2(1/\varepsilon)/\varepsilon^4)$ due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of $Ω(r/\varepsilon^2)$, improving the previous best $Ω(r/\varepsilon+1/\varepsilon^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(r^2/\varepsilon^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).

quant-pharXiv:2606.26034•Jun 25, 2026•0 citations
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.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1){\rm T}_{\infty}(ρ_0,ρ_1)T∞​(ρ0​,ρ1​), defined via the operator norm ∥A∥∞=σmax⁡(A)\|A\|_{\infty} = σ_{\max}(A)∥A∥∞​=σmax​(A), given poly(n){\rm poly}(n)poly(n)-size state-preparation circuits of nnn-qubit quantum states ρ0ρ_0ρ0​ and ρ1ρ_1ρ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/ε)Θ(1/ε)Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5ε=1/5ε=1/5, our estimator runs in poly(n){\rm poly}(n)poly(n) time. Since the operator norm distance T∞(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)T∞​(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}(|ψ\rangle\!\langleψ|,ρ)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(ρ){\rm rank}(ρ)rank(ρ), which can be exp⁡(n)\exp(n)exp(n) in general. 2. For general quantum states, we also provide a quantum estimator using O~(1/ε3/2)\widetilde{O}(1/ε^{3/2})O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP{\sf BQP}BQP-complete and improves the QMA{\sf QMA}QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε)Ω(1/ε)Ω(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 ∣ψ⟩|ψ\rangle∣ψ⟩ has overlap at least 1/21/21/2 with the top unit eigenvector of ∣ψ⟩ ⁣⟨ψ∣−ρ|ψ\rangle\!\langleψ|-ρ∣ψ⟩⟨ψ∣−ρ, 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 usingusingusing\Theta (1/\varepsilon)queriestotheirstate−preparationcircuits,quadraticallyimprovingthelong−standingfolklorequeries to their state-preparation circuits, quadratically improving the long-standing folklorequeriestotheirstate−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.
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)O(N^2/\varepsilon^6)O(N2/ε6) where NNN is the number of qubits of the given states and ε\varepsilonε 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.
We propose a series of quantum algorithms for computing a wide range of quantum entropies and distances, including the von Neumann entropy, quantum Rényi entropy, trace distance, and fidelity. The proposed algorithms significantly outperform the prior best (and even quantum) ones in the low-rank case, some of which achieve exponential speedups. In particular, forN-dimensional quantum states of rankr, our proposed quantum algorithms for computing the von Neumann entropy, trace distance and fidelity within additive error ε have time complexity of Õ(r/ε2), Õ(r5/ε6) and Õ(r6.5/ε7.5), respectively. By contrast, prior quantum algorithms for the von Neumann entropy and trace distance usually have time complexity Ω(N), and the prior best one for fidelity has time complexity Õ(r12.5/ε13.5). The key idea of our quantum algorithms is to extend block-encoding from unitary operators in previous work to quantum states (i.e., density operators). It is realized by developing several convenient techniques to manipulate quantum states and extract information from them. The advantage of our techniques over the existing methods is that no restrictions on density operators are required; in sharp contrast, the previous methods usually require a lower bound on the minimal non-zero eigenvalue of density operators.
We settle the problem of estimating the trace distance and (square root) fidelity between nnn-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/ε2)Θ(1/\varepsilon^2)Θ(1/ε2), improving the long-standing folklore with sample complexity O(1/ε4)O(1/\varepsilon^4)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 QQQ queries to the reflection operator I−2∣ψ⟩ ⁣⟨ψ∣I - 2|ψ\rangle\!\langleψ|I−2∣ψ⟩⟨ψ∣ can be converted to a δδδ-close (in the diamond norm distance) quantum sample algorithm using Θ(Q2/δ)Θ(Q^2/δ)Θ(Q2/δ) samples of the state ∣ψ⟩|ψ\rangle∣ψ⟩. This samplizer for pure states is also shown to be optimal.
We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error ε\varepsilonε. We show that the sample complexity is O(r2/ε2)O(r^2/\varepsilon^2)O(r2/ε2) with optimal ε\varepsilonε-dependence when the reference state is of rank rrr, improving the previous best O(r2log⁡2(1/ε)/ε4)O(r^2\log^2(1/\varepsilon)/\varepsilon^4)O(r2log2(1/ε)/ε4) due to Utsumi, Nakata, Wang, and Takagi (QIP 2026). We also provide a lower bound of Ω(r/ε2)Ω(r/\varepsilon^2)Ω(r/ε2), improving the previous best Ω(r/ε+1/ε2)Ω(r/\varepsilon+1/\varepsilon^2)Ω(r/ε+1/ε2), with implications to quantum query complexity. Moreover, we further consider the case where the unknown state is of rank at most rrr while the reference state can be arbitrary, for which the sample complexity is shown to be O(r2/ε4)O(r^2/\varepsilon^4)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).