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.

AI Summary

The paper studies tomography of an unknown $d$-dimensional state $\sigma$ promised to lie within trace distance $R$ of a known reference state $\rho$, allowing arbitrary collective measurements. It asks how the reference spectrum and neighborhood radius determine the minimax estimation cost, including at singular centers and when alternatives can increase rank. Writing $\Gamma=d(\operatorname{Tr}\sqrt{\rho})^2+d^2R$, it establishes expected minimax trace-distance risk $\Theta(\min\{R,\sqrt{\Gamma/n}\})$ and minimax confidence radius $\Theta(\min\{R,\sqrt{(\Gamma+\log(1/\delta))/n}\})$ for $d\ge2$, $0<R\le1$, $n\ge1$, and $0<\delta\le1/3$, with universal constants. Consequently, for $\varepsilon\le c_0R$, copy complexity is $\Theta((\Gamma+\log(1/\delta))/\varepsilon^2)$. Pure centers give $\Gamma=d+d^2R$, while normalized rank-$r$ projectors give $\Gamma=dr+d^2R$. The main converse regularizes the center inside the ball, constructs square-root perturbations indexed by sign matrices, and combines neighboring-state testing with a spectrally weighted trace-norm witness that retains all spectral scales. A two-point argument supplies the confidence term. Achievability uses an existing purification/Hayashi measurement, analyzed through an exact Gaussian representation, together with returning $\rho$ at small sample sizes. The paper explicitly identifies the upper rates as consequences of prior results. The guarantees impose no computational or measurement restrictions and assume, rather than verify, the neighborhood promise. They do not locate the precise transition as $\varepsilon/R$ approaches one. Local rates for restricted measurements, efficient implementations, and arbitrary nonuniform fixed-rank centers remain open.

Almost certainly largely AI-generatedAI use disclosed
Chat GPT 6 Astra was used to draft the paper and refine the mathematical arguments.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Minimax Quantum State Tomography with Periodic Clifford Measurements

Hongru Zhao

Quantum state tomography provides a foundation for characterizing state preparation and predicting measurement outcomes. We characterize the minimax expected trace norm risk of quantum state tomography over classes with polynomial spectral decay under randomized nonadaptive single copy measurements. Under an explicit sufficient block size condition for the two layer periodic Clifford ensemble, we establish statewise expected trace norm oracle inequalities for operator norm minimum distance and measurement weighted projected least squares, with bounds that depend on each state's actual spectral tail, while the estimators require no prior knowledge of the state's structural characteristics, including its rank, eigenbasis, or spectral structure. Over these polynomial spectral decay classes, both estimators attain the minimax expected trace norm rates up to constants. As a direct consequence, the same estimators attain the minimax rate over every fixed rank constrained class, while remaining adaptive to the unknown structural characteristics of the state. For admissible logarithmic block sizes, the periodic Clifford measurements attain these guarantees with logarithmic elementary gate depth. The main technical ingredient is a uniform bound on the fourth moment of projectors for the periodic Clifford ensemble. The bound is sharp in dimension and holds for arbitrary test states, including those entangled across blocks. Covariance concentration and positivity yield adaptive oracle bounds, while a shared rotation information argument on spectral tail packings establishes matching lower bounds. We also provide polynomial time reconstruction algorithms, numerical comparisons, and Lean formalizations of all labeled theoretical results.

quant-pharXiv:2610.00210•Sep 22, 2026•0 citations

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•8 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•6 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•6 citations

Minimax Quantum Tomography: Estimators and Relative Entropy Bounds

Christopher Ferrie, Robin Blume-Kohout

A minimax estimator has the minimum possible error ("risk") in the worst case. We construct the first minimax estimators for quantum state tomography with relative entropy risk. The minimax risk of nonadaptive tomography scales as O(1/sqrt[N])-in contrast to that of classical probability estimation, which is O(1/N)-where N is the number of copies of the quantum state used. We trace this deficiency to sampling mismatch: future observations that determine risk may come from a different sample space than the past data that determine the estimate. This makes minimax estimators very biased, and we propose a computationally tractable alternative with similar behavior in the worst case, but superior accuracy on most states.

arXiv:1503.03100•Physical Review Letters•Mar 4, 2016•20 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•3 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.
The paper studies tomography of an unknown ddd-dimensional state σ\sigmaσ promised to lie within trace distance RRR of a known reference state ρ\rhoρ, allowing arbitrary collective measurements. It asks how the reference spectrum and neighborhood radius determine the minimax estimation cost, including at singular centers and when alternatives can increase rank.
Writing Γ=d(Tr⁡ρ)2+d2R\Gamma=d(\operatorname{Tr}\sqrt{\rho})^2+d^2RΓ=d(Trρ​)2+d2R, it establishes expected minimax trace-distance risk Θ(min⁡{R,Γ/n})\Theta(\min\{R,\sqrt{\Gamma/n}\})Θ(min{R,Γ/n​}) and minimax confidence radius Θ(min⁡{R,(Γ+log⁡(1/δ))/n})\Theta(\min\{R,\sqrt{(\Gamma+\log(1/\delta))/n}\})Θ(min{R,(Γ+log(1/δ))/n​}) for d≥2d\ge2d≥2, 0<R≤10<R\le10<R≤1, n≥1n\ge1n≥1, and 0<δ≤1/30<\delta\le1/30<δ≤1/3, with universal constants. Consequently, for ε≤c0R\varepsilon\le c_0Rε≤c0​R, copy complexity is Θ((Γ+log⁡(1/δ))/ε2)\Theta((\Gamma+\log(1/\delta))/\varepsilon^2)Θ((Γ+log(1/δ))/ε2). Pure centers give Γ=d+d2R\Gamma=d+d^2RΓ=d+d2R, while normalized rank-rrr projectors give Γ=dr+d2R\Gamma=dr+d^2RΓ=dr+d2R.
The main converse regularizes the center inside the ball, constructs square-root perturbations indexed by sign matrices, and combines neighboring-state testing with a spectrally weighted trace-norm witness that retains all spectral scales. A two-point argument supplies the confidence term. Achievability uses an existing purification/Hayashi measurement, analyzed through an exact Gaussian representation, together with returning ρ\rhoρ at small sample sizes. The paper explicitly identifies the upper rates as consequences of prior results.
The guarantees impose no computational or measurement restrictions and assume, rather than verify, the neighborhood promise. They do not locate the precise transition as ε/R\varepsilon/Rε/R approaches one. Local rates for restricted measurements, efficient implementations, and arbitrary nonuniform fixed-rank centers remain open.
Quantum state tomography provides a foundation for characterizing state preparation and predicting measurement outcomes. We characterize the minimax expected trace norm risk of quantum state tomography over classes with polynomial spectral decay under randomized nonadaptive single copy measurements. Under an explicit sufficient block size condition for the two layer periodic Clifford ensemble, we establish statewise expected trace norm oracle inequalities for operator norm minimum distance and measurement weighted projected least squares, with bounds that depend on each state's actual spectral tail, while the estimators require no prior knowledge of the state's structural characteristics, including its rank, eigenbasis, or spectral structure. Over these polynomial spectral decay classes, both estimators attain the minimax expected trace norm rates up to constants. As a direct consequence, the same estimators attain the minimax rate over every fixed rank constrained class, while remaining adaptive to the unknown structural characteristics of the state. For admissible logarithmic block sizes, the periodic Clifford measurements attain these guarantees with logarithmic elementary gate depth. The main technical ingredient is a uniform bound on the fourth moment of projectors for the periodic Clifford ensemble. The bound is sharp in dimension and holds for arbitrary test states, including those entangled across blocks. Covariance concentration and positivity yield adaptive oracle bounds, while a shared rotation information argument on spectral tail packings establishes matching lower bounds. We also provide polynomial time reconstruction algorithms, numerical comparisons, and Lean formalizations of all labeled theoretical results.
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.
A minimax estimator has the minimum possible error ("risk") in the worst case. We construct the first minimax estimators for quantum state tomography with relative entropy risk. The minimax risk of nonadaptive tomography scales as O(1/sqrt[N])-in contrast to that of classical probability estimation, which is O(1/N)-where N is the number of copies of the quantum state used. We trace this deficiency to sampling mismatch: future observations that determine risk may come from a different sample space than the past data that determine the estimate. This makes minimax estimators very biased, and we propose a computationally tractable alternative with similar behavior in the worst case, but superior accuracy on most states.
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.