arXiv:2609.37781

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

Zhenhuan Liu

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations

Abstract

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

Comments: 55 pages, 1 figure

Related papers

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Shuai Zeng

quant-pharXiv:2604.22627Apr 27, 20260 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

quant-pharXiv:2608.02600Aug 4, 20260 citations

Optimal spectrum estimation

Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

quant-pharXiv:2609.30171Sep 25, 20260 citations

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography

Sitan Chen, Jerry Zheng Li, Allen Liu

arXiv:2402.16353ACM Symposium on Theory of Computing (STOC)Jun 10, 202411 citations

Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank

Gye Jin Lee, Sunghyeon Jo

quant-pharXiv:2608.01770Aug 4, 20260 citations

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

Ashwin Nayak, Xingyu Zhou

quant-pharXiv:2609.10514Sep 10, 20260 citations

arXiv:2609.37781

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

Zhenhuan Liu

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations

arXiv HTML PDF

Abstract

\operatorname{Tr}(ρ^t)

, allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity

Θ(\sqrt d)

at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer

t\ge 2

: for any sufficiently small constant additive error, the optimal sample complexity is [ Θ!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) ] with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer

h\geq1

, all moment orders

2^{h-1}<t\leq2^h

share the same exponent. In particular, the third and fourth moments both require

Θ(d^{2/3})

copies. We also establish an

Ω(d^{1-1/t})

lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every

t\geq4

. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond

\sqrt d

Comments: 55 pages, 1 figure

Related papers

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Shuai Zeng

Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as $\operatorname{tr}(ρ^t)$ , but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order $t\ge 3$ , existing protocols show that $\lceil t/2\rceil$ replicas already suffice for polynomial-sample estimation of $\operatorname{tr}(ρ^t)$ , yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to $\lceil t/2\rceil-1$ replicas requires dimension-growing sample complexity, while $\lceil t/2\rceil$ replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is $\lceil t/2\rceil$ . Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments $\operatorname{tr}(Oρ^t)$ , including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as $\operatorname{tr}(ρ^t)$, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order $t\ge 3$, existing protocols show that $\lceil t/2\rceil$ replicas already suffice for polynomial-sample estimation of $\operatorname{tr}(ρ^t)$, yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to $\lceil t/2\rceil-1$ replicas requires dimension-growing sample complexity, while $\lceil t/2\rceil$ replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is $\lceil t/2\rceil$. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments $\operatorname{tr}(Oρ^t)$, including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.

quant-pharXiv:2604.22627Apr 27, 20260 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$ , where $ρ$ is an unknown $d$ -dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$ , combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is $Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right),$ and the sample complexity of spectrum estimation is $Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right).$ In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600Aug 4, 20260 citations

Optimal spectrum estimation

Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan

We prove that the spectrum of an unknown $d$ -dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using $O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right)$ copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

quant-pharXiv:2609.30171Sep 25, 20260 citations

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography

Sitan Chen, Jerry Zheng Li, Allen Liu

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.

arXiv:2402.16353ACM Symposium on Theory of Computing (STOC)Jun 10, 202411 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.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.01770Aug 4, 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

Optimal single-copy estimation of quantum state moments: why

\operatorname{Tr}(ρ^3)

and

\operatorname{Tr}(ρ^4)

are equally hard

\operatorname{Tr}(ρ^t)

, allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity

Θ(\sqrt d)

at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer

t\ge 2

h\geq1

, all moment orders

2^{h-1}<t\leq2^h

share the same exponent. In particular, the third and fourth moments both require

Θ(d^{2/3})

copies. We also establish an

Ω(d^{1-1/t})

lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every

t\geq4

\sqrt d

Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as

\operatorname{tr}(ρ^t)

, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order

t\ge 3

, existing protocols show that

\lceil t/2\rceil

replicas already suffice for polynomial-sample estimation of

\operatorname{tr}(ρ^t)

, yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to

\lceil t/2\rceil-1

replicas requires dimension-growing sample complexity, while

\lceil t/2\rceil

replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is

\lceil t/2\rceil

. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments

\operatorname{tr}(Oρ^t)

, including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form

\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d

, where

ρ

is an unknown

d

-dimensional quantum state and

φ

is a given function. A master theorem is established that derives sample complexity lower bounds for estimating

\mathcal{L}_φ(ρ)

from properties of

φ

, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is

Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right),

and the sample complexity of spectrum estimation is

Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right).

In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

We prove that the spectrum of an unknown

d

-dimensional quantum state can be estimated to error

\varepsilon

in total variation distance using

O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right)

copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of

d

in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

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

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

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.