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

Minimax Quantum State Tomography in a Known Trace-Distance Ball

Yonglong Li

quant-phcs.ITSubmitted Oct 4, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Tight Lower Bounds for State Tomography with Limited Entanglement

Ufuk Keskin, Jason Luo, Mahbod Majid +1 more

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $ε$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}ε^2),d^2/ε^2\}$ for every $k$ and all sufficiently small $ε$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

quant-pharXiv:2609.05718•Sep 8, 2026•0 citations

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

Ashwin Nayak, Xingyu Zhou

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

quant-pharXiv:2609.10514•Sep 10, 2026•0 citations

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown $d$-dimensional quantum state $ρ$ and a known collection of observables $E_1,\ldots,E_M$, the goal is to estimate all expectation values $\{\text{Tr}(ρE_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ with probability at least $1-δ$. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on $M$, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity \[ O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), \] which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.

quant-pharXiv:2608.06345•Aug 7, 2026•0 citations

Minimax estimation of qubit states with Bures risk

Anirudh Acharya, Mădălin Guţǎ

Abstract The central problem of quantum statistics is to devise measurement schemes for the estimation of an unknown state, given an ensemble of n independent identically prepared systems. For locally quadratic loss functions, the risk of standard procedures has the usual scaling of 1/ n . However, it has been noticed that for fidelity based metrics such as the Bures distance, the risk of conventional (non-adaptive) qubit tomography schemes scales as 1 / n for states close to the boundary of the Bloch sphere. Several proposed estimators appear to improve this scaling, and our goal is to analyse the problem from the perspective of the maximum risk over all states. We propose qubit estimation strategies based on separate adaptive measurements, and collective measurements, that achieve 1/ n scalings for the maximum Bures risk. The estimator involving local measurements uses a fixed fraction of the available resource n to estimate the Bloch vector direction; the length of the Bloch vector is then estimated from the remaining copies by measuring in the estimator eigenbasis. The estimator based on collective measurements uses local asymptotic normality techniques which allows us to derive upper and lower bounds to its maximum Bures risk. We also discuss how to construct a minimax optimal estimator in this setup. Finally, we consider quantum relative entropy and show that the risk of the estimator based on collective measurements achieves a rate O ( n − 1 log ⁡ n ) under this loss function. Furthermore, we show that no estimator can achieve faster rates, in particular the ‘standard’ rate n −1 .

arXiv:1708.04941•Journal of Physics A Mathematical and Theoretical•Mar 15, 2018•2 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

Optimal lower bounds for quantum state tomography

Thilo Scharnhorst, Jack Spilecki, Wright, John

We show that $n = Ω(rd/\varepsilon^2)$ copies are necessary to learn a rank $r$ mixed state $ρ\in \mathbb{C}^{d \times d}$ up to error $\varepsilon$ in trace distance. This matches the upper bound of $n = O(rd/\varepsilon^2)$ from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which $ρ$ is promised to be of the form $ρ= P/r$, where $P \in \mathbb{C}^{d \times d}$ is a rank $r$ projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error $\varepsilon$ in trace distance to an algorithm which learns to error $O(\varepsilon)$ in the more stringent Bures distance.

arXiv:2510.07699•Oct 9, 2025•0 citations
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 [
Θ!\left(\min\left{R,\sqrt{\frac{Γ+\log(1/δ)}{n}}\right}\right). ] 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 study state tomography when each measurement acts on at most kkk fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary ddd-dimensional state to trace distance εεε is, up to absolute constant factors, max⁡{d3/(kε2),d2/ε2}\max\{d^3/(\sqrt{k}ε^2),d^2/ε^2\}max{d3/(k​ε2),d2/ε2} for every kkk and all sufficiently small εεε. This removes the earlier restriction that kkk be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order 1/d1/d1/d, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most ttt samples. For sufficiently small ε\varepsilonε, estimating an unknown state on Cd\mathbb{C}^dCd of rank at most rrr to trace norm error ε\varepsilonε with constant success probability requires, and is achievable with, Θ(drε2max{1,rt})Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)Θ(ε2dr​max{1,t​r​}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most ttt samples improve the complexity of algorithms making single-sample measurements by at most a factor t\sqrt{t}t​. Further, measuring order r2r^2r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on ttt samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown ddd-dimensional quantum state ρρρ and a known collection of observables E1,…,EME_1,\ldots,E_ME1​,…,EM​, the goal is to estimate all expectation values {Tr(ρEi)}i=1M\{\text{Tr}(ρE_i)\}_{i=1}^M{Tr(ρEi​)}i=1M​ to additive accuracy ε\varepsilonε with probability at least 1−δ1-δ1−δ. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on MMM, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(log⁡(M)log⁡(M/δ)ε2), O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), O(ε2log(M)log(M/δ)​), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
Abstract The central problem of quantum statistics is to devise measurement schemes for the estimation of an unknown state, given an ensemble of n independent identically prepared systems. For locally quadratic loss functions, the risk of standard procedures has the usual scaling of 1/ n . However, it has been noticed that for fidelity based metrics such as the Bures distance, the risk of conventional (non-adaptive) qubit tomography schemes scales as 1 / n for states close to the boundary of the Bloch sphere. Several proposed estimators appear to improve this scaling, and our goal is to analyse the problem from the perspective of the maximum risk over all states. We propose qubit estimation strategies based on separate adaptive measurements, and collective measurements, that achieve 1/ n scalings for the maximum Bures risk. The estimator involving local measurements uses a fixed fraction of the available resource n to estimate the Bloch vector direction; the length of the Bloch vector is then estimated from the remaining copies by measuring in the estimator eigenbasis. The estimator based on collective measurements uses local asymptotic normality techniques which allows us to derive upper and lower bounds to its maximum Bures risk. We also discuss how to construct a minimax optimal estimator in this setup. Finally, we consider quantum relative entropy and show that the risk of the estimator based on collective measurements achieves a rate O ( n − 1 log ⁡ n ) under this loss function. Furthermore, we show that no estimator can achieve faster rates, in particular the ‘standard’ rate n −1 .
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.
We show that n=Ω(rd/ε2)n = Ω(rd/\varepsilon^2)n=Ω(rd/ε2) copies are necessary to learn a rank rrr mixed state ρ∈Cd×dρ\in \mathbb{C}^{d \times d}ρ∈Cd×d up to error ε\varepsilonε in trace distance. This matches the upper bound of n=O(rd/ε2)n = O(rd/\varepsilon^2)n=O(rd/ε2) from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which ρρρ is promised to be of the form ρ=P/rρ= P/rρ=P/r, where P∈Cd×dP \in \mathbb{C}^{d \times d}P∈Cd×d is a rank rrr projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error ε\varepsilonε in trace distance to an algorithm which learns to error O(ε)O(\varepsilon)O(ε) in the more stringent Bures distance.