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

Optimal lower bounds for quantum state tomography

Thilo Scharnhorst, Jack Spilecki, Wright, John

Published Oct 9, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2510.07699

Related papers

Lower Bounds for Learning Quantum States with Single-Copy Measurements

Angus Lowe, Ashwin Nayak

We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of \(\Omega (r^2 d/\epsilon ^2)\) and \(\Omega (r^2 d^2/\epsilon ^2)\) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of \(\exp (O(d))\) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.

arXiv:2207.14438•ACM Transactions on Computation Theory•Feb 13, 2025•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•0 citations

Sample-optimal tomography of quantum states

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji +2 more

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.

arXiv:1508.01797•IEEE Transactions on Information Theory•Jan 1, 2017•182 citations

Optimal cloning of mixed states

Marco Fanizza, Dmitry Grinko, Thilo Scharnhorst +1 more

We consider the problem of approximate cloning of quantum states: given $n$ copies of an unknown state $ρ\in \mathbb{C}^{d \times d}$, prepare an $(n+k)$-copy state with high fidelity to $ρ^{\otimes (n+k)}$. Werner's pure state cloner is the optimal channel for the pure state case, and shows that $n = Θ(kd/\varepsilon)$ copies are necessary and sufficient to clone $k$ additional copies of an unknown pure state to fidelity $1-\varepsilon$. The random purification channel gives a straightforward extension of Werner's cloner to mixed state inputs: given $n$ copies of a mixed state, randomly purify your input, apply Werner's channel in the larger Hilbert space, and then trace out the auxiliary registers. This gives a mixed state cloner using $n = O(krd/\varepsilon)$ copies to clone rank-$r$ states. Can one do any better? We show that the answer is no: one must use $n = Ω(krd/\varepsilon)$ copies. We prove our lower bound by studying the special case of projector cloning, in which the input state $ρ$ is promised to be of the form $P/r$, where $P$ is a rank-$r$ orthogonal projector. As a further application of our techniques, we consider the closely related problem of approximate transposition of quantum states, where one seeks to convert $ρ^{\otimes n}$ to a $k$-copy state with high fidelity to $(ρ^T)^{\otimes k}$. Here, we again show $n = Θ(krd/\varepsilon)$ copies are necessary and sufficient for this task.

quant-pharXiv:2608.27298•Aug 28, 2026•0 citations

Entangled measurements are necessary for optimal tomography of mixed fermionic Gaussian states and of bosonic Gaussian states near the vacuum

Ron Rubin

We prove that learning an unknown mixed fermionic Gaussian state on $m$ modes to trace distance $ε$ requires $Ω(m^3/ε^2)$ copies when measurements act on one copy at a time, even with arbitrary POVMs, fresh ancillas and classical adaptivity, but without quantum memory between copies. The bound holds for $0<ε\le1/3600$ and separates this model from the known collective rate $Θ(m^2/ε^2)$. It follows from a uniform single-copy Fisher-information budget and a dimension-independent comparison between trace distance and Gaussian parameters. On covariance matrices of operator norm at most $1-c$, we prove a Frobenius-to-trace-norm continuity bound with constant $[2c(2-c)]^{-1/2}$; matchgate shadows then attain $O(m^3/(cε^2))$ copies. This also gives explicit error certificates for thermal free-fermion states. For a class of mixed passive bosonic Gaussian states with total mean photon number at most one, a reduction to bounded-block qudit tomography gives a single-copy lower bound $Ω(m^3/(ε^2\sqrt{\log(m/ε)}))$, versus collective complexity $Θ(m^2/ε^2)$. These separations answer the mixed-state measurement-resource question posed by Chen et al. A two-mode example has optimal two-copy Fisher trace $5$, versus the separable ceiling $4$. An IBM replication gave a pre-registered witness lower bound $4.12$ at one-sided $95\%$ shot-noise confidence; its interpretation assumes the prescribed preparations and a common measurement channel and does not bound preparation systematics.

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

An Improved Sample Complexity Lower Bound for (Fidelity) Quantum State Tomography

Henry Yuen

We show that Ω(rd/ϵ) copies of an unknown rank- r , dimension- d quantum mixed state are necessary in order to learn a classical description with 1–ϵ fidelity. This improves upon the tomography lower bounds obtained by Haah, et al. and Wright (when closeness is measured with respect to the fidelity function).

arXiv:2206.11185•Quantum•Jan 3, 2023•23 citations
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.
We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2)\Omega (r^2 d/\epsilon ^2)Ω(r2d/ϵ2) and Ω(r2d2/ϵ2)\Omega (r^2 d^2/\epsilon ^2)Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp⁡(O(d))\exp (O(d))exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.
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.
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
We consider the problem of approximate cloning of quantum states: given nnn copies of an unknown state ρ∈Cd×dρ\in \mathbb{C}^{d \times d}ρ∈Cd×d, prepare an (n+k)(n+k)(n+k)-copy state with high fidelity to ρ⊗(n+k)ρ^{\otimes (n+k)}ρ⊗(n+k). Werner's pure state cloner is the optimal channel for the pure state case, and shows that n=Θ(kd/ε)n = Θ(kd/\varepsilon)n=Θ(kd/ε) copies are necessary and sufficient to clone kkk additional copies of an unknown pure state to fidelity 1−ε1-\varepsilon1−ε. The random purification channel gives a straightforward extension of Werner's cloner to mixed state inputs: given nnn copies of a mixed state, randomly purify your input, apply Werner's channel in the larger Hilbert space, and then trace out the auxiliary registers. This gives a mixed state cloner using n=O(krd/ε)n = O(krd/\varepsilon)n=O(krd/ε) copies to clone rank-rrr states. Can one do any better? We show that the answer is no: one must use n=Ω(krd/ε)n = Ω(krd/\varepsilon)n=Ω(krd/ε) copies. We prove our lower bound by studying the special case of projector cloning, in which the input state ρρρ is promised to be of the form P/rP/rP/r, where PPP is a rank-rrr orthogonal projector. As a further application of our techniques, we consider the closely related problem of approximate transposition of quantum states, where one seeks to convert ρ⊗nρ^{\otimes n}ρ⊗n to a kkk-copy state with high fidelity to (ρT)⊗k(ρ^T)^{\otimes k}(ρT)⊗k. Here, we again show n=Θ(krd/ε)n = Θ(krd/\varepsilon)n=Θ(krd/ε) copies are necessary and sufficient for this task.
We prove that learning an unknown mixed fermionic Gaussian state on mmm modes to trace distance εεε requires Ω(m3/ε2)Ω(m^3/ε^2)Ω(m3/ε2) copies when measurements act on one copy at a time, even with arbitrary POVMs, fresh ancillas and classical adaptivity, but without quantum memory between copies. The bound holds for 0<ε≤1/36000<ε\le1/36000<ε≤1/3600 and separates this model from the known collective rate Θ(m2/ε2)Θ(m^2/ε^2)Θ(m2/ε2). It follows from a uniform single-copy Fisher-information budget and a dimension-independent comparison between trace distance and Gaussian parameters. On covariance matrices of operator norm at most 1−c1-c1−c, we prove a Frobenius-to-trace-norm continuity bound with constant [2c(2−c)]−1/2[2c(2-c)]^{-1/2}[2c(2−c)]−1/2; matchgate shadows then attain O(m3/(cε2))O(m^3/(cε^2))O(m3/(cε2)) copies. This also gives explicit error certificates for thermal free-fermion states. For a class of mixed passive bosonic Gaussian states with total mean photon number at most one, a reduction to bounded-block qudit tomography gives a single-copy lower bound Ω(m3/(ε2log⁡(m/ε)))Ω(m^3/(ε^2\sqrt{\log(m/ε)}))Ω(m3/(ε2log(m/ε)​)), versus collective complexity Θ(m2/ε2)Θ(m^2/ε^2)Θ(m2/ε2). These separations answer the mixed-state measurement-resource question posed by Chen et al. A two-mode example has optimal two-copy Fisher trace 555, versus the separable ceiling 444. An IBM replication gave a pre-registered witness lower bound 4.124.124.12 at one-sided 95%95\%95% shot-noise confidence; its interpretation assumes the prescribed preparations and a common measurement channel and does not bound preparation systematics.