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:2409.04189 · PRX Quantum

Optimal Fidelity Estimation from Binary Measurements for Discrete and Continuous Variable Systems

Omar Fawzi, Aadil Oufkir, Robert Salzmann

Published Sep 22, 2025• 2 citations
arXivHTMLPDF

Abstract

Estimating the fidelity between a desired target quantum state and an actual prepared state is essential for assessing the success of experiments. For pure target states, we use functional representations that can be measured directly and determine the number of copies of the prepared state needed for fidelity estimation. In continuous variable (CV) systems, we use the Wigner function, which can be measured via displaced parity measurements. We provide upper and lower bounds on the sample complexity required for fidelity estimation, considering the worst-case scenario across all possible prepared states. For target states of particular interest, such as Fock and Gaussian states, we find that this sample complexity is characterized by the L 1 -norm of the Wigner function, a measure of Wigner negativity widely studied in the literature, in particular in resource theories of quantum computation. For discrete variable systems consisting of n qubits, we explore fidelity estimation protocols using Pauli string measurements. Similarly as for the CV approach, the sample complexity is shown to be characterized by the L 1 -norm of the characteristic function of the target state for both Haar random states and stabilizer states. Furthermore, in a general black box model, we prove that, for any target state, the optimal sample complexity for fidelity estimation is characterized by the smoothed L 1 -norm of the target state. To the best of our knowledge, this is the first time the L 1 -norm of the Wigner function provides a lower bound on the cost of some information processing task.

DOI
10.1103/qd1c-1fk9

Related papers

Optimizing resource bounds in direct fidelity estimation

Netanel Barel, Lee Peleg, Yotam Kadish +2 more

Direct fidelity estimation provides a way to estimate the fidelity between an experimentally prepared state and a desired pure target state without performing full tomography. Two influential formulations were introduced in 2011 by Flammia and Liu and by da Silva, Landon-Cardinal, and Poulin. In these protocols, the total estimation error is controlled through two distinct probabilistic steps: first, the fidelity is approximated using randomly sampled Pauli observables; second, each sampled expectation value is estimated from finitely many measurement outcomes. In this work we show that additional structural information about the noise can substantially sharpen the corresponding resource bounds. In particular, for some canonical channels the effective number of sampled Pauli settings can be reduced, leading to lower measurement cost both in the general pure-state setting and in the case of a stabilizer state. These results illustrate a broader point: worst-case confidence bounds in direct fidelity estimation can be significantly conservative when experimentally relevant structure is ignored. As a technical ingredient, we also revisit the allocation of the total accuracy and confidence budgets between the two probabilistic steps. Reformulating the analysis in terms of separate error parameters yields a constrained optimization problem whose solution lowers the average number of measurements in the general pure-state setting. Numerical simulations based on quantum circuits implemented in Qiskit illustrate both the improvement obtained under structured-noise assumptions and the conservativeness of the original worst-case bounds.

quant-pharXiv:2606.16336•Jun 16, 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

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

Fidelity Estimation of Entangled Measurements with Local States

Zanqiu Shen, Kun Wang

We propose an efficient protocol to estimate the fidelity of an $n$-qubit entangled measurement device, requiring only qubit state preparations and classical data post-processing. It works by measuring the eigenstates of Pauli operators, which are strategically selected according to their importance weights and collectively contributed by all measurement operators. We rigorously analyze the protocol's performance and demonstrate that its sample complexity is uniquely determined by the number of Pauli operators possessing non-zero expectation values with respect to the target measurement. Moreover, from a resource-theoretic perspective, we introduce the stabilizer Rényi entropy of quantum measurements as a precise metric to quantify the inherent difficulty of estimating measurement fidelity.

arXiv:2312.13730•Dec 21, 2023•0 citations

Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank

Gye Jin Lee, Sunghyeon Jo

We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most $s$, we give an estimator using $O(s^2/\varepsilon^2)$ copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds $r,s$ as $\min\{r,s\}^2/\varepsilon^2$ up to logarithmic factors in the smaller rank. The same estimator gives the upper bound $O(r(\operatorname{tr}\sqrtσ)^2/\varepsilon^2)$ for a rank-$r$ reference $σ$. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra $λ_i\propto i^{-α}$ with fixed $1<α\le2$, as $\varepsilon\downarrow0$ with $r\ge C_α\varepsilon^{-2/(α-1)}$, the bounds determine the complexity as $\widetildeΘ_α(\varepsilon^{-4/(α-1)})$. In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.

quant-pharXiv:2608.01770•Aug 4, 2026•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
Estimating the fidelity between a desired target quantum state and an actual prepared state is essential for assessing the success of experiments. For pure target states, we use functional representations that can be measured directly and determine the number of copies of the prepared state needed for fidelity estimation. In continuous variable (CV) systems, we use the Wigner function, which can be measured via displaced parity measurements. We provide upper and lower bounds on the sample complexity required for fidelity estimation, considering the worst-case scenario across all possible prepared states. For target states of particular interest, such as Fock and Gaussian states, we find that this sample complexity is characterized by the L 1 -norm of the Wigner function, a measure of Wigner negativity widely studied in the literature, in particular in resource theories of quantum computation. For discrete variable systems consisting of n qubits, we explore fidelity estimation protocols using Pauli string measurements. Similarly as for the CV approach, the sample complexity is shown to be characterized by the L 1 -norm of the characteristic function of the target state for both Haar random states and stabilizer states. Furthermore, in a general black box model, we prove that, for any target state, the optimal sample complexity for fidelity estimation is characterized by the smoothed L 1 -norm of the target state. To the best of our knowledge, this is the first time the L 1 -norm of the Wigner function provides a lower bound on the cost of some information processing task.
Direct fidelity estimation provides a way to estimate the fidelity between an experimentally prepared state and a desired pure target state without performing full tomography. Two influential formulations were introduced in 2011 by Flammia and Liu and by da Silva, Landon-Cardinal, and Poulin. In these protocols, the total estimation error is controlled through two distinct probabilistic steps: first, the fidelity is approximated using randomly sampled Pauli observables; second, each sampled expectation value is estimated from finitely many measurement outcomes. In this work we show that additional structural information about the noise can substantially sharpen the corresponding resource bounds. In particular, for some canonical channels the effective number of sampled Pauli settings can be reduced, leading to lower measurement cost both in the general pure-state setting and in the case of a stabilizer state. These results illustrate a broader point: worst-case confidence bounds in direct fidelity estimation can be significantly conservative when experimentally relevant structure is ignored. As a technical ingredient, we also revisit the allocation of the total accuracy and confidence budgets between the two probabilistic steps. Reformulating the analysis in terms of separate error parameters yields a constrained optimization problem whose solution lowers the average number of measurements in the general pure-state setting. Numerical simulations based on quantum circuits implemented in Qiskit illustrate both the improvement obtained under structured-noise assumptions and the conservativeness of the original worst-case bounds.
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.
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.
We propose an efficient protocol to estimate the fidelity of an nnn-qubit entangled measurement device, requiring only qubit state preparations and classical data post-processing. It works by measuring the eigenstates of Pauli operators, which are strategically selected according to their importance weights and collectively contributed by all measurement operators. We rigorously analyze the protocol's performance and demonstrate that its sample complexity is uniquely determined by the number of Pauli operators possessing non-zero expectation values with respect to the target measurement. Moreover, from a resource-theoretic perspective, we introduce the stabilizer Rényi entropy of quantum measurements as a precise metric to quantify the inherent difficulty of estimating measurement fidelity.
We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most sss, we give an estimator using O(s2/ε2)O(s^2/\varepsilon^2)O(s2/ε2) copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds r,sr,sr,s as min⁡{r,s}2/ε2\min\{r,s\}^2/\varepsilon^2min{r,s}2/ε2 up to logarithmic factors in the smaller rank. The same estimator gives the upper bound O(r(tr⁡σ)2/ε2)O(r(\operatorname{tr}\sqrtσ)^2/\varepsilon^2)O(r(trσ​)2/ε2) for a rank-rrr reference σσσ. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra λi∝i−αλ_i\propto i^{-α}λi​∝i−α with fixed 1<α≤21<α\le21<α≤2, as ε↓0\varepsilon\downarrow0ε↓0 with r≥Cαε−2/(α−1)r\ge C_α\varepsilon^{-2/(α-1)}r≥Cα​ε−2/(α−1), the bounds determine the complexity as Θ~α(ε−4/(α−1))\widetildeΘ_α(\varepsilon^{-4/(α-1)})Θα​(ε−4/(α−1)). In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.
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.