arXiv:2610.00270 · Statistics & Probability Letters

A Frame-Spread Lower Bound for Quantum Entropy Estimation under Fixed Rank-One Measurements

Xinyu Song

quant-phmath.STSubmitted Aug 25, 2026• Announced Aug 26, 2026• 0 citations

Abstract

We study estimation of the von Neumann entropy of a $d$-dimensional quantum state from independent outcomes of a fixed rank-one measurement. Let $κ_ν\in[1,d+1]$ denote the normalized trace-zero frame spread; $κ_ν=1$ for exact complex projective $2$-designs. For any fixed rank-one measurement and $n\le c_2d^2/κ_ν$, the minimax mean-squared error is at least $c_1\log^2\{d^2/(κ_νn)\}$. For bounded frame spread and every fixed $0<a<2$, the minimax risk is of order $\log^2 d$ throughout $n\lesssim d^{2-a}$; hence fixed uniform accuracy requires $Ω(d^2)$ observations. Existing tomography bounds give bounded risk from $O(d^3\log^3 d)$ observations for finite equal-weight exact designs and the Haar covariant measurement, while the intermediate minimax regime remains open. The results concern a fixed measurement repeated independently across copies; adaptive and collective protocols, and protocols that reuse common randomness across copies, are not covered.

Related papers

Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements

Xinyu Song

quant-pharXiv:2609.29485Aug 26, 20260 citations

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

quant-pharXiv:2608.06345Aug 7, 20260 citations

Minimax Quantum State Tomography in a Known Trace-Distance Ball

Yonglong Li

quant-pharXiv:2610.05374Oct 6, 20260 citations

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

Ashwin Nayak, Xingyu Zhou

quant-pharXiv:2609.10514Sep 10, 20260 citations

Spectrum Estimation is Almost as Hard as Tomography

Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa

quant-pharXiv:2607.29680Aug 3, 20260 citations

Lower Bounds for Learning Quantum States with Single-Copy Measurements

Angus Lowe, Ashwin Nayak

arXiv:2207.14438ACM Transactions on Computation TheoryFeb 13, 20258 citations

arXiv:2610.00270 · Statistics & Probability Letters

A Frame-Spread Lower Bound for Quantum Entropy Estimation under Fixed Rank-One Measurements

Xinyu Song

quant-phmath.STSubmitted Aug 25, 2026• Announced Aug 26, 2026• 0 citations

arXiv HTML PDF

Abstract

We study estimation of the von Neumann entropy of a

d

-dimensional quantum state from independent outcomes of a fixed rank-one measurement. Let

κ_ν\in[1,d+1]

denote the normalized trace-zero frame spread;

κ_ν=1

for exact complex projective

2

-designs. For any fixed rank-one measurement and

n\le c_2d^2/κ_ν

, the minimax mean-squared error is at least

c_1\log^2\{d^2/(κ_νn)\}

. For bounded frame spread and every fixed

0<a<2

, the minimax risk is of order

\log^2 d

throughout

n\lesssim d^{2-a}

; hence fixed uniform accuracy requires

Ω(d^2)

observations. Existing tomography bounds give bounded risk from

O(d^3\log^3 d)

observations for finite equal-weight exact designs and the Haar covariant measurement, while the intermediate minimax regime remains open. The results concern a fixed measurement repeated independently across copies; adaptive and collective protocols, and protocols that reuse common randomness across copies, are not covered.

Related papers

Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements

Xinyu Song

We establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least $(d/n)\log^2\{n/(4d)\}$ when $d\ge C$ and $n\ge Cd$ , without a projective-design assumption. We also characterize risk on an operator-norm ball of radius $r$ around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by $\varepsilon<1$ from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most $d^3r^2/n+d^4/n^2+d^6r^6$ . Lower bounds under the same frame control yield the local minimax rate $d^3r^2/n+d^4/n^2$ when $n\ge Cd^2$ and $r$ lies in an explicit matching range. For every fixed upper bound on $\varepsilon$ , approximation changes only the constants, not the powers of $d,n,r$ . At the critical radius $r=n^{-1/2}$ , the local risk is asymptotically negligible relative to the global risk when $n\log^2(n/d)\gg d^3$ . This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.We establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least $(d/n)\log^2\{n/(4d)\}$ when $d\ge C$ and $n\ge Cd$, without a projective-design assumption. We also characterize risk on an operator-norm ball of radius $r$ around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by $\varepsilon<1$ from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most $d^3r^2/n+d^4/n^2+d^6r^6$. Lower bounds under the same frame control yield the local minimax rate $d^3r^2/n+d^4/n^2$ when $n\ge Cd^2$ and $r$ lies in an explicit matching range. For every fixed upper bound on $\varepsilon$, approximation changes only the constants, not the powers of $d,n,r$. At the critical radius $r=n^{-1/2}$, the local risk is asymptotically negligible relative to the global risk when $n\log^2(n/d)\gg d^3$. This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.

quant-pharXiv:2609.29485Aug 26, 20260 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.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.06345Aug 7, 20260 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.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.05374Oct 6, 20260 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.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.10514Sep 10, 20260 citations

Spectrum Estimation is Almost as Hard as Tomography

Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa

We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$ -dimensional states, and for every $γ>0$ , we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$ -divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.

quant-pharXiv:2607.29680Aug 3, 20260 citations

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.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.14438ACM Transactions on Computation TheoryFeb 13, 20258 citations

We study estimation of the von Neumann entropy of a

d

-dimensional quantum state from independent outcomes of a fixed rank-one measurement. Let

κ_ν\in[1,d+1]

denote the normalized trace-zero frame spread;

κ_ν=1

for exact complex projective

2

-designs. For any fixed rank-one measurement and

n\le c_2d^2/κ_ν

, the minimax mean-squared error is at least

c_1\log^2\{d^2/(κ_νn)\}

. For bounded frame spread and every fixed

0<a<2

, the minimax risk is of order

\log^2 d

throughout

n\lesssim d^{2-a}

; hence fixed uniform accuracy requires

Ω(d^2)

observations. Existing tomography bounds give bounded risk from

O(d^3\log^3 d)

We establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least

(d/n)\log^2\{n/(4d)\}

when

d\ge C

and

n\ge Cd

, without a projective-design assumption. We also characterize risk on an operator-norm ball of radius

r

around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by

\varepsilon<1

from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most

d^3r^2/n+d^4/n^2+d^6r^6

. Lower bounds under the same frame control yield the local minimax rate

d^3r^2/n+d^4/n^2

when

n\ge Cd^2

and

r

lies in an explicit matching range. For every fixed upper bound on

\varepsilon

, approximation changes only the constants, not the powers of

d,n,r

. At the critical radius

r=n^{-1/2}

, the local risk is asymptotically negligible relative to the global risk when

n\log^2(n/d)\gg d^3

. This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.

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.

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.

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.

d

-dimensional states, and for every

γ>0

, we prove a sample complexity lower bound of

Ω(d^{2-γ})

for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an

f

-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.

\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.