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:2203.15993

Improved Quantum Algorithms for Fidelity Estimation

András Gilyén, Alexander Poremba

Published Mar 30, 2022• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2203.15993

Related papers

Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform

Yupan Liu, Qisheng Wang

The Uhlmann fidelity ${\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_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 $\varepsilon$ 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/\varepsilon$. However, the known optimal estimator for ${\rm F}(ρ,|ψ\rangle\!\langleψ|)$ 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 ${\rm F}(ρ, |ψ\rangle\!\langleψ|)$ 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 ${\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|ψ_1\rangle$ (or $|ψ_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.

quant-pharXiv:2608.10674•Aug 12, 2026•0 citations

Efficient Quantum State Identity Testing

Shih-Han Hung, Ming-Hsien Tsai

We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\in(0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log(n/δ)\log(2/δ))$ copies of each input state to succeed with probability at least $1-δ$. The second uses the Schur transform to reduce the sample complexity to $O(\log(n/δ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $Ω(\log(n/δ))$ for any quantum algorithm with failure probability at most $δ\le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $δ$ for fixed $\varepsilon$.

quant-pharXiv:2610.04597•Oct 6, 2026•0 citations

Quantum fidelity estimation in the resource theory of nonstabilizerness

Zhiping Liu, Kun Wang, Xin Wang

Quantum fidelity estimation is essential for benchmarking quantum states and processes on noisy quantum devices. While stabilizer operations form the foundation of fault-tolerant quantum computing, nonstabilizer resources further enable universal quantum computation through state injection. In this work, we propose several efficient quantum fidelity estimation protocols for both quantum states and channels within the resource theory of nonstabilizerness, focusing on qudit systems with odd prime dimensions. Our fidelity estimation algorithms require measuring only a constant number of phase-space point operator expectation values, with operators selected randomly according to an importance weighting scheme tailored to the target state. Notably, we demonstrate that mathematically defined nonstabilizerness measures---such as Wigner rank and mana---quantify the sample complexity of the proposed protocols, thereby endowing them with a clear operational interpretation in the fidelity estimation task. This connection reveals a fundamental trade-off: while fidelity estimation for general quantum states and channels requires resources that scale exponentially with their nonstabilizerness, the task remains tractable for states and channels that admit efficient classical simulation.

arXiv:2506.12938•Physical Review A•Aug 26, 2025•0 citations

Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic

Guedong Park, Jaekwon Chang, Yosep Kim +2 more

Direct fidelity estimation (DFE) is a famous tool for estimating the fidelity with a target pure state. However, such a method generally requires exponentially many sampling copies due to the large magic of the target state. This work proposes a sample- and gate-efficient fidelity estimation algorithm that is affordable within feasible quantum devices. We show that the fidelity estimation with pure states close to the structure of phase states, for which sample-efficient DFE is limited by their strong entanglement and magic, can be done by using $\mathcal{O}({\rm poly}(n))$ sampling copies, with a single $n$-qubit fan-out gate. As the target state becomes a phase state, the sampling complexity reaches $\mathcal{O}(1)$. Such a drastic improvement stems from a crucial step in our scheme, the so-called phase stripping, which can significantly reduce the target-state magic. Furthermore, we convert a complex diagonal gate resource, which is needed to design a phase-stripping-adapted algorithm, into nonlinear classical post-processing of Pauli measurements so that we only require a single fan-out gate. Additionally, as another variant using the nonlinear post-processing, we propose a nonlinear extension of the conventional DFE scheme. Here, the sampling reduction compared to DFE is also guaranteed, while preserving the Pauli measurement as the only circuit resource. We expect our work to contribute to establishing noise-resilient quantum algorithms by enabling a significant reduction in sampling overhead for fidelity estimation under the restricted gate resources, and ultimately to clarifying a fundamental gap between the resource overhead required to understand complex physical properties and that required to generate them.

quant-pharXiv:2602.09710•Feb 11, 2026•0 citations

Efficient Fidelity Estimation of General Quantum Resource States via Clifford Circuits

Shunta Takahashi, Keisuke Fujii

Fidelity estimation is a fundamental tool for assessing quantum resource states across quantum information science. For small infidelity $ε$, tomography and direct fidelity estimation (DFE) have worst-case sample complexity $O(1/ε^2)$ at fixed relative accuracy and confidence. Direct target projections achieve $O(1/ε)$ but generally require non-Clifford operations whose reliability depends on the resource states that are typically the target of benchmarking. Here, we introduce the Bell--coherence fidelity estimation (BCFE) with optimal sample complexity $Θ(1/ε)$ using only Clifford gates and Pauli measurements. We prove that BCFE is applicable to arbitrary pure targets, possibly multi-qubit, with the statistical error of the single-copy coherence part explicitly controlled. To evaluate BCFE in a practical setting, we apply BCFE to analog rotation resource states in the candidate early-FTQC architecture called the Space-Time Efficient Analog Rotations (STAR) architecture. In the simulations using surface codes, BCFE is estimated to require up to approximately $27$ times fewer resource states than DFE for the same standard error in the infidelity estimate, while its estimates remain close to reference values despite circuit-level noise in the additional Bell measurement operations. These results support efficient resource benchmarking within fault-tolerant quantum computing.

quant-pharXiv:2610.05222•Oct 6, 2026•0 citations

Optimal fidelity estimation for density matrix

Yiping Lu, Liyu Lai, Jun Xiang +3 more

Fidelity estimation is a necessary tool for evaluating noise in quantum measurement and quantum computation. The traditional fidelity estimation is to calculate the distance between two density matrices by employing direct fidelity estimation, which consumes too much copies of state. To reduce the number of copies of the state, we develop optimal fidelity estimation by proposing an optimal model. It calculates the minimum number of copies of state given a fixed value for the fidelity deviation. The result shows it saves a large number of copies of state compared with traditional approach (Direct Fidelity estimation) that is developed several years ago.The number of copies of the state employed increases slower than linear increase with increase of the dimension of density matrix when pauli measurement basis is applied. In addition, it consumes roughly a constant number of copies of the state with the increase of dimension of density matrix when the measurement bases are freely chosen.

Scientific Reports•Dec 5, 2024•0 citations
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∣{\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_1}|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 ε\varepsilonε 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ρ_0ρ0​ and ρ1ρ_1ρ1​. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on 1/ε1/\varepsilon1/ε. However, the known optimal estimator for F(ρ,∣ψ⟩ ⁣⟨ψ∣){\rm F}(ρ,|ψ\rangle\!\langleψ|)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(ρ,∣ψ⟩ ⁣⟨ψ∣){\rm F}(ρ, |ψ\rangle\!\langleψ|)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∣){\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)trA​(∣ψ0​⟩⟨ψ1​∣) (or its inverse) to the reference register R\sf RR of the purification ∣ψ1⟩|ψ_1\rangle∣ψ1​⟩ (or ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩) on the registers A\sf AA and R\sf RR, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.
We study the following quantum state identity problem: given access to copies of nnn unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε1-\varepsilon1−ε or some pair has fidelity at most ε\varepsilonε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4)\varepsilon\in(0,1/4)ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log⁡(n/δ)log⁡(2/δ))O(\log(n/δ)\log(2/δ))O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ1-δ1−δ. The second uses the Schur transform to reduce the sample complexity to O(log⁡(n/δ))O(\log(n/δ))O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log⁡(n/δ))Ω(\log(n/δ))Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−cδ\le 1/2-cδ≤1/2−c, for any constant c>0c>0c>0, establishing that the second algorithm achieves the optimal dependence on both nnn and δδδ for fixed ε\varepsilonε.
Quantum fidelity estimation is essential for benchmarking quantum states and processes on noisy quantum devices. While stabilizer operations form the foundation of fault-tolerant quantum computing, nonstabilizer resources further enable universal quantum computation through state injection. In this work, we propose several efficient quantum fidelity estimation protocols for both quantum states and channels within the resource theory of nonstabilizerness, focusing on qudit systems with odd prime dimensions. Our fidelity estimation algorithms require measuring only a constant number of phase-space point operator expectation values, with operators selected randomly according to an importance weighting scheme tailored to the target state. Notably, we demonstrate that mathematically defined nonstabilizerness measures---such as Wigner rank and mana---quantify the sample complexity of the proposed protocols, thereby endowing them with a clear operational interpretation in the fidelity estimation task. This connection reveals a fundamental trade-off: while fidelity estimation for general quantum states and channels requires resources that scale exponentially with their nonstabilizerness, the task remains tractable for states and channels that admit efficient classical simulation.
Direct fidelity estimation (DFE) is a famous tool for estimating the fidelity with a target pure state. However, such a method generally requires exponentially many sampling copies due to the large magic of the target state. This work proposes a sample- and gate-efficient fidelity estimation algorithm that is affordable within feasible quantum devices. We show that the fidelity estimation with pure states close to the structure of phase states, for which sample-efficient DFE is limited by their strong entanglement and magic, can be done by using O(poly(n))\mathcal{O}({\rm poly}(n))O(poly(n)) sampling copies, with a single nnn-qubit fan-out gate. As the target state becomes a phase state, the sampling complexity reaches O(1)\mathcal{O}(1)O(1). Such a drastic improvement stems from a crucial step in our scheme, the so-called phase stripping, which can significantly reduce the target-state magic. Furthermore, we convert a complex diagonal gate resource, which is needed to design a phase-stripping-adapted algorithm, into nonlinear classical post-processing of Pauli measurements so that we only require a single fan-out gate. Additionally, as another variant using the nonlinear post-processing, we propose a nonlinear extension of the conventional DFE scheme. Here, the sampling reduction compared to DFE is also guaranteed, while preserving the Pauli measurement as the only circuit resource. We expect our work to contribute to establishing noise-resilient quantum algorithms by enabling a significant reduction in sampling overhead for fidelity estimation under the restricted gate resources, and ultimately to clarifying a fundamental gap between the resource overhead required to understand complex physical properties and that required to generate them.
Fidelity estimation is a fundamental tool for assessing quantum resource states across quantum information science. For small infidelity εεε, tomography and direct fidelity estimation (DFE) have worst-case sample complexity O(1/ε2)O(1/ε^2)O(1/ε2) at fixed relative accuracy and confidence. Direct target projections achieve O(1/ε)O(1/ε)O(1/ε) but generally require non-Clifford operations whose reliability depends on the resource states that are typically the target of benchmarking. Here, we introduce the Bell--coherence fidelity estimation (BCFE) with optimal sample complexity Θ(1/ε)Θ(1/ε)Θ(1/ε) using only Clifford gates and Pauli measurements. We prove that BCFE is applicable to arbitrary pure targets, possibly multi-qubit, with the statistical error of the single-copy coherence part explicitly controlled. To evaluate BCFE in a practical setting, we apply BCFE to analog rotation resource states in the candidate early-FTQC architecture called the Space-Time Efficient Analog Rotations (STAR) architecture. In the simulations using surface codes, BCFE is estimated to require up to approximately 272727 times fewer resource states than DFE for the same standard error in the infidelity estimate, while its estimates remain close to reference values despite circuit-level noise in the additional Bell measurement operations. These results support efficient resource benchmarking within fault-tolerant quantum computing.
Fidelity estimation is a necessary tool for evaluating noise in quantum measurement and quantum computation. The traditional fidelity estimation is to calculate the distance between two density matrices by employing direct fidelity estimation, which consumes too much copies of state. To reduce the number of copies of the state, we develop optimal fidelity estimation by proposing an optimal model. It calculates the minimum number of copies of state given a fixed value for the fidelity deviation. The result shows it saves a large number of copies of state compared with traditional approach (Direct Fidelity estimation) that is developed several years ago.The number of copies of the state employed increases slower than linear increase with increase of the dimension of density matrix when pauli measurement basis is applied. In addition, it consumes roughly a constant number of copies of the state with the increase of dimension of density matrix when the measurement bases are freely chosen.