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

The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetildeΘ(r^2/\varepsilon^2)$

Gye Jin Lee, Sunghyeon Jo

quant-phSubmitted Aug 3, 2026• Announced Aug 4, 2026• 0 citations
v1 · Aug 3, 2026v2 · Oct 1, 2026
arXivHTMLPDF

Abstract

We settle the sample complexity of estimating the root Uhlmann fidelity $F(ρ,σ)=\operatorname{tr}\sqrt{\sqrtσρ\sqrtσ}$ between an unknown state $ρ$ and a known rank-$r$ reference state $σ$. Writing $S(r,\varepsilon)$ for the sample complexity at additive error $\varepsilon$, we resolve the open problem posed by Wang by closing, up to logarithmic factors, the gap between the previously known bounds $Ω(r/\varepsilon^2)$ and $O(r^2/\varepsilon^2)$. We prove $S(r,\varepsilon)=\widetildeΘ(r^2/\varepsilon^2)$ for all $0<\varepsilon\le\varepsilon_0$, where $\varepsilon_0>0$ is a universal constant. The lower bound already holds on a $2r$-dimensional system when $σ$ is maximally mixed on a fixed $r$-dimensional subspace, and for a hard family of states that do not commute with $σ$. The proof combines exact spectral moment matching, a radially size-biased doubly correlated Wishart model, and the Cauchy identity, reducing state indistinguishability to a long-cycle estimate for a weighted random permutation. A direct-sum embedding and binomial thinning yield the optimal $1/\varepsilon^2$ dependence. We also prove a near-quadratic lower bound $\widetildeΩ(r^2)$ for quantum spectrum estimation at constant accuracy. Combined with the recent $O(r^2(\log\log r/\log r)^2)$ upper bound, this determines the polynomial order of the sample complexity in this regime and establishes a near-quadratic barrier.

Comments
28 pages

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

Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States

Pavel Svetlichnyy

We study coherent classical shadows protocols for an unknown $d$-dimensional quantum state of rank at most $r$, allowing an arbitrary joint measurement on all available copies. For observables with operator norm at most one and centered squared Frobenius norm at most $F$, we study the minumum number of copies $T$ needed for the protocol to successed with propbability $1 - δ$. We prove a lower bound on $T$, that depends both on $δ$ and the number $M$ of post-measurement observables. Denoting $\ell=\max\{\log(2M),\log(1/δ)\}$, we show that $T=Ω\left(\min\left\{\frac{\sqrt{rF\ell}}{\varepsilon},\frac{(F\ell)^{2/3}}{\varepsilon^{4/3}}\right\}+\frac{\ell}{\varepsilon^2}\right)$ under the mild assumption $\log(2M)\lesssim d\min\{r,F\}$. The lower bound nearly matches the known upper bound and matches the conjectural strengthening of the known upper bound. The proof is inspired by the framework of the proof of the lower bound for Boolean Hidden Matching. We develop a Gaussian-lift noise kernel that transfers forward and reverse Gaussian hypercontractivity to the Grassmannian, allowing us to bound the distinguishing advantage in an auxiliary game with a revealed query observable. We use Schur--Weyl structure and posterior moment bounds to control arbitrary coherent measurements on the source side.

quant-pharXiv:2610.18031•Oct 14, 2026•0 citations

Optimal copy complexity of quantum state cloning

Sangwoo Jeon, Vaughn Sohn, Changhun Oh

Quantum state cloning is the task of approximately producing additional copies of an unknown quantum state from a finite number of input copies. The optimal cloning fidelity is known exactly for pure states, but no comparable characterization is known for general mixed states. We determine the optimal asymptotic copy complexity for $d$-dimensional states of rank at most $r$: producing $M$ additional copies with worst-case fidelity at least $1-\varepsilon$ requires and is achievable with $N=Θ(Mrd/\varepsilon)$ input copies. Remarkably, the lower bound already holds for a family of states with a fixed flat spectrum, while the matching upper bound is achieved by random purification followed by optimal pure-state cloning. For $M=1$, we further show that high-fidelity tomography can be coherently converted into cloning with comparable error, revealing an operational origin of the matching cloning and tomography complexities.

quant-pharXiv:2608.24484•Aug 26, 2026•0 citations

Minimax Quantum State Tomography in a Known Trace-Distance Ball

Yonglong Li

We study quantum state tomography when the unknown state lies in a trace-distance ball of radius $R$ around a known reference state $ρ$. For arbitrary collective measurements, we determine the minimax expected risk and confidence radius up to universal constants, uniformly over the dimension, center spectrum, radius, and sample size. Write $Γ=d(\mathrm{Tr}\sqrtρ)^2+d^2R$. For $d\ge2$, $0<R\le1$, and $n\ge1$ copies, the expected risk is $Θ(\min\{R,\sqrt{Γ/n}\})$. At failure probability $0<δ\le1/3$, the minimax confidence radius is \[ Θ\!\left(\min\left\{R,\sqrt{\frac{Γ+\log(1/δ)}{n}}\right\}\right). \] For $\varepsilon\le c_0R$ with a universal $c_0>0$, the copy complexity is $Θ((Γ+\log(1/δ))/\varepsilon^2)$. For the lower bound we use a weighted trace-norm witness to retain all spectral scales in a square-root perturbation family. For the upper bound, we give a direct spectral and concentration analysis of a modified existing purification-based procedure.

quant-pharXiv:2610.05374•Oct 6, 2026•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

Optimal single-copy estimation of quantum state moments: why $\operatorname{Tr}(ρ^3)$ and $\operatorname{Tr}(ρ^4)$ are equally hard

Zhenhuan Liu

Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments $\operatorname{Tr}(ρ^t)$, allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity $Θ(\sqrt d)$ at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer $t\ge 2$: for any sufficiently small constant additive error, the optimal sample complexity is \[ Θ\!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) \] with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer $h\geq1$, all moment orders $2^{h-1}<t\leq2^h$ share the same exponent. In particular, the third and fourth moments both require $Θ(d^{2/3})$ copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an $Ω(d^{1-1/t})$ lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every $t\geq4$. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond $\sqrt d$.

quant-pharXiv:2609.37781•Sep 30, 2026•0 citations
The Sample Complexity of Fidelity Estimation to a Known Rank-rrr Reference State Is Θ~(r2/ε2)\widetildeΘ(r^2/\varepsilon^2)Θ(r2/ε2)
We settle the sample complexity of estimating the root Uhlmann fidelity F(ρ,σ)=tr⁡σρσF(ρ,σ)=\operatorname{tr}\sqrt{\sqrtσρ\sqrtσ}F(ρ,σ)=trσ​ρσ​​ between an unknown state ρρρ and a known rank-rrr reference state σσσ. Writing S(r,ε)S(r,\varepsilon)S(r,ε) for the sample complexity at additive error ε\varepsilonε, we resolve the open problem posed by Wang by closing, up to logarithmic factors, the gap between the previously known bounds Ω(r/ε2)Ω(r/\varepsilon^2)Ω(r/ε2) and O(r2/ε2)O(r^2/\varepsilon^2)O(r2/ε2). We prove S(r,ε)=Θ~(r2/ε2)S(r,\varepsilon)=\widetildeΘ(r^2/\varepsilon^2)S(r,ε)=Θ(r2/ε2) for all 0<ε≤ε00<\varepsilon\le\varepsilon_00<ε≤ε0​, where ε0>0\varepsilon_0>0ε0​>0 is a universal constant. The lower bound already holds on a 2r2r2r-dimensional system when σσσ is maximally mixed on a fixed rrr-dimensional subspace, and for a hard family of states that do not commute with σσσ. The proof combines exact spectral moment matching, a radially size-biased doubly correlated Wishart model, and the Cauchy identity, reducing state indistinguishability to a long-cycle estimate for a weighted random permutation. A direct-sum embedding and binomial thinning yield the optimal 1/ε21/\varepsilon^21/ε2 dependence. We also prove a near-quadratic lower bound Ω~(r2)\widetildeΩ(r^2)Ω(r2) for quantum spectrum estimation at constant accuracy. Combined with the recent O(r2(log⁡log⁡r/log⁡r)2)O(r^2(\log\log r/\log r)^2)O(r2(loglogr/logr)2) upper bound, this determines the polynomial order of the sample complexity in this regime and establishes a near-quadratic barrier.
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 coherent classical shadows protocols for an unknown ddd-dimensional quantum state of rank at most rrr, allowing an arbitrary joint measurement on all available copies. For observables with operator norm at most one and centered squared Frobenius norm at most FFF, we study the minumum number of copies TTT needed for the protocol to successed with propbability 1−δ1 - δ1−δ. We prove a lower bound on TTT, that depends both on δδδ and the number MMM of post-measurement observables. Denoting ℓ=max⁡{log⁡(2M),log⁡(1/δ)}\ell=\max\{\log(2M),\log(1/δ)\}ℓ=max{log(2M),log(1/δ)}, we show that T=Ω(min⁡{rFℓε,(Fℓ)2/3ε4/3}+ℓε2)T=Ω\left(\min\left\{\frac{\sqrt{rF\ell}}{\varepsilon},\frac{(F\ell)^{2/3}}{\varepsilon^{4/3}}\right\}+\frac{\ell}{\varepsilon^2}\right)T=Ω(min{εrFℓ​​,ε4/3(Fℓ)2/3​}+ε2ℓ​) under the mild assumption log⁡(2M)≲dmin⁡{r,F}\log(2M)\lesssim d\min\{r,F\}log(2M)≲dmin{r,F}. The lower bound nearly matches the known upper bound and matches the conjectural strengthening of the known upper bound. The proof is inspired by the framework of the proof of the lower bound for Boolean Hidden Matching. We develop a Gaussian-lift noise kernel that transfers forward and reverse Gaussian hypercontractivity to the Grassmannian, allowing us to bound the distinguishing advantage in an auxiliary game with a revealed query observable. We use Schur--Weyl structure and posterior moment bounds to control arbitrary coherent measurements on the source side.
Quantum state cloning is the task of approximately producing additional copies of an unknown quantum state from a finite number of input copies. The optimal cloning fidelity is known exactly for pure states, but no comparable characterization is known for general mixed states. We determine the optimal asymptotic copy complexity for ddd-dimensional states of rank at most rrr: producing MMM additional copies with worst-case fidelity at least 1−ε1-\varepsilon1−ε requires and is achievable with N=Θ(Mrd/ε)N=Θ(Mrd/\varepsilon)N=Θ(Mrd/ε) input copies. Remarkably, the lower bound already holds for a family of states with a fixed flat spectrum, while the matching upper bound is achieved by random purification followed by optimal pure-state cloning. For M=1M=1M=1, we further show that high-fidelity tomography can be coherently converted into cloning with comparable error, revealing an operational origin of the matching cloning and tomography complexities.
We study quantum state tomography when the unknown state lies in a trace-distance ball of radius RRR around a known reference state ρρρ. For arbitrary collective measurements, we determine the minimax expected risk and confidence radius up to universal constants, uniformly over the dimension, center spectrum, radius, and sample size. Write Γ=d(Trρ)2+d2RΓ=d(\mathrm{Tr}\sqrtρ)^2+d^2RΓ=d(Trρ​)2+d2R. For d≥2d\ge2d≥2, 0<R≤10<R\le10<R≤1, and n≥1n\ge1n≥1 copies, the expected risk is Θ(min⁡{R,Γ/n})Θ(\min\{R,\sqrt{Γ/n}\})Θ(min{R,Γ/n​}). At failure probability 0<δ≤1/30<δ\le1/30<δ≤1/3, the minimax confidence radius is Θ ⁣(min⁡{R,Γ+log⁡(1/δ)n}). Θ\!\left(\min\left\{R,\sqrt{\frac{Γ+\log(1/δ)}{n}}\right\}\right). Θ(min{R,nΓ+log(1/δ)​​}). For ε≤c0R\varepsilon\le c_0Rε≤c0​R with a universal c0>0c_0>0c0​>0, the copy complexity is Θ((Γ+log⁡(1/δ))/ε2)Θ((Γ+\log(1/δ))/\varepsilon^2)Θ((Γ+log(1/δ))/ε2). For the lower bound we use a weighted trace-norm witness to retain all spectral scales in a square-root perturbation family. For the upper bound, we give a direct spectral and concentration analysis of a modified existing purification-based procedure.
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).
Optimal single-copy estimation of quantum state moments: why Tr⁡(ρ3)\operatorname{Tr}(ρ^3)Tr(ρ3) and Tr⁡(ρ4)\operatorname{Tr}(ρ^4)Tr(ρ4) are equally hard
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments Tr⁡(ρt)\operatorname{Tr}(ρ^t)Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d)Θ(\sqrt d)Θ(d​) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2t\ge 2t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ ⁣(d⌈log⁡2t⌉1+⌈log⁡2t⌉) Θ\!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) Θ(d1+⌈log2​t⌉⌈log2​t⌉​) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1h\geq1h≥1, all moment orders 2h−1<t≤2h2^{h-1}<t\leq2^h2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3)Θ(d^{2/3})Θ(d2/3) copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an Ω(d1−1/t)Ω(d^{1-1/t})Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4t\geq4t≥4. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond d\sqrt dd​.