arXiv:2609.24132

Pauli-resolved virtual distillation

Si-Yuan Chen, Congcong Zheng, Kun Wang, Ming-Cheng Chen

quant-phSubmitted Sep 21, 2026• Announced Sep 22, 2026• 0 citations

Abstract

Learning the full Pauli profile of the virtually distilled quantum state $ρ^m/\text{tr}(ρ^m)$ has so far required exponentially many copies of $ρ$. We show that all $4^n$ squared Pauli moments $[\text{tr}(Pρ^m)]^2$ can be learned to additive error $\varepsilon$ with confidence $1-δ$ from one $2m$-replica measurement setting using $O(m[n+\log(1/δ)]/\varepsilon^2)$ copies. This is an exponential speedup in the system size $n$ over previous protocols. For $m = 2$, we propose the coherent Bell difference sampling circuit that realizes this measurement on current devices. The speedup originates from paired replicas that cancel the anticommutation signs of Pauli operators, collapsing the incompatibility of the Pauli family. We certify this collapse by introducing the quantum Bernstein norm, a computable incompatibility measure for nonlinear functionals. A further information-theoretic $m$-replica protocol recovers the signed moments $\text{tr}(Pρ^m)$ using $O(m[n+\log(1/δ)]/\varepsilon^4)$ copies. For fixed $m$ in the stated lower-bound regime, it attains the optimal replica number, since any protocol with fewer replicas requires exponentially many copies.

Comments: 50 pages, 4 figures,

Related papers

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Shuai Zeng

quant-pharXiv:2604.22627Apr 27, 20260 citations

Optimal Tradeoffs for Estimating Pauli Observables

Sitan Chen, Weiyuan Gong, Qi Ye

arXiv:2404.19105Annual Symposium on Foundations of Computer ScienceOct 27, 202416 citations

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

Zhenhuan Liu

quant-pharXiv:2609.37781Sep 30, 20260 citations

Error Mitigation in Bosonic Systems via Virtual Distillation

Leonardo Finocchiaro, Marco Robbio, Diogo Gomes +5 more

quant-pharXiv:2607.04914Jul 7, 20260 citations

Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices

Yukun Zhang, Yusen Wu, You Zhou +1 more

arXiv:2509.01571Sep 1, 20250 citations

Computational entanglement distillation beyond pure states: efficient protocols and fundamental limitations

Takeru Utsumi, Jacopo Rizzo, Ryuji Takagi +1 more

quant-pharXiv:2610.06787Oct 6, 20260 citations

arXiv:2609.24132

Pauli-resolved virtual distillation

Si-Yuan Chen, Congcong Zheng, Kun Wang, Ming-Cheng Chen

quant-phSubmitted Sep 21, 2026• Announced Sep 22, 2026• 0 citations

arXiv HTML PDF

Abstract

Learning the full Pauli profile of the virtually distilled quantum state

ρ^m/\text{tr}(ρ^m)

has so far required exponentially many copies of

ρ

. We show that all

4^n

squared Pauli moments

[\text{tr}(Pρ^m)]^2

can be learned to additive error

\varepsilon

with confidence

1-δ

from one

2m

-replica measurement setting using

O(m[n+\log(1/δ)]/\varepsilon^2)

copies. This is an exponential speedup in the system size

n

over previous protocols. For

m = 2

, we propose the coherent Bell difference sampling circuit that realizes this measurement on current devices. The speedup originates from paired replicas that cancel the anticommutation signs of Pauli operators, collapsing the incompatibility of the Pauli family. We certify this collapse by introducing the quantum Bernstein norm, a computable incompatibility measure for nonlinear functionals. A further information-theoretic

m

-replica protocol recovers the signed moments

\text{tr}(Pρ^m)

using

O(m[n+\log(1/δ)]/\varepsilon^4)

copies. For fixed

m

in the stated lower-bound regime, it attains the optimal replica number, since any protocol with fewer replicas requires exponentially many copies.

Comments: 50 pages, 4 figures,

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

Optimal Tradeoffs for Estimating Pauli Observables

Sitan Chen, Weiyuan Gong, Qi Ye

We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state $\rho$ , estimate Tr $(P\rho)$ for some set of Pauli operators $F$ to within additive error $\epsilon$ . This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate $\vert \text{Tr}(P\rho)$ for all $P$ using $O(n/\epsilon^{4})$ copies, but with $k\leq n$ qubits of memory, $\Omega(2^{(n-k)/3})$ copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on $\epsilon ?$ What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subset $A$ of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to $\log\vert A\vert$ factors. •We show any protocol that makes poly $(n)$ -copy measure-ments must make $\Omega(1/\epsilon^{4})$ measurements. •For any protocol that makes poly $(n)$ -copy measurements and only has $k < n$ qubits of memory, we show that $\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})$ copies are necessary and sufficient. The protocols we propose can also estimate the actual values $\text{Tr}(P\rho)$ , rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state$\rho$, estimate Tr$(P\rho)$for some set of Pauli operators$F$to within additive error$\epsilon$. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate$\vert \text{Tr}(P\rho)$for all$P$using$O(n/\epsilon^{4})$copies, but with$k\leq n$qubits of memory,$\Omega(2^{(n-k)/3})$copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on$\epsilon ?$What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subset$A$of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to$\log\vert A\vert$factors. •We show any protocol that makes poly$(n)$-copy measure-ments must make$\Omega(1/\epsilon^{4})$measurements. •For any protocol that makes poly$(n)$-copy measurements and only has$k < n$qubits of memory, we show that$\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})$copies are necessary and sufficient. The protocols we propose can also estimate the actual values$\text{Tr}(P\rho)$, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

arXiv:2404.19105Annual Symposium on Foundations of Computer ScienceOct 27, 202416 citations

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

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. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. 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$ .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. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. 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$.

quant-pharXiv:2609.37781Sep 30, 20260 citations

Error Mitigation in Bosonic Systems via Virtual Distillation

Leonardo Finocchiaro, Marco Robbio, Diogo Gomes +5 more

Virtual distillation is a promising error-mitigation technique that exploits multiple copies of a noisy quantum state to estimate observables as if measured on a purified state. Although originally introduced in the context of bosonic many-body systems under the name of virtual cooling, its development and applications have largely focused on qubit-based quantum computation. Here, we establish a framework for virtual distillation in bosonic quantum information processing and continuous-variable quantum computing. Building on a diagonalization of cyclic shift operators implemented with passive linear-optical interferometers, we derive experimentally accessible protocols for estimating virtually distilled expectation values of observables relevant to bosonic architectures. In particular, we show how to recover noise-mitigated expectation values of number operators, phase-shift operators, and arbitrary quadratures from multi-copy measurements. For number operators, we further demonstrate the estimation of virtually distilled correlators of arbitrary order through the characteristic function of the photon-number distribution. We apply the framework to states affected by photon loss and dephasing, two of the dominant noise mechanisms in bosonic quantum computation, and quantify the resulting suppression of noise contributions. Our results extend virtual distillation beyond its original setting and provide a practical route toward error-mitigated measurements in bosonic quantum processors using experimentally available linear-optical resources.Virtual distillation is a promising error-mitigation technique that exploits multiple copies of a noisy quantum state to estimate observables as if measured on a purified state. Although originally introduced in the context of bosonic many-body systems under the name of virtual cooling, its development and applications have largely focused on qubit-based quantum computation. Here, we establish a framework for virtual distillation in bosonic quantum information processing and continuous-variable quantum computing. Building on a diagonalization of cyclic shift operators implemented with passive linear-optical interferometers, we derive experimentally accessible protocols for estimating virtually distilled expectation values of observables relevant to bosonic architectures. In particular, we show how to recover noise-mitigated expectation values of number operators, phase-shift operators, and arbitrary quadratures from multi-copy measurements. For number operators, we further demonstrate the estimation of virtually distilled correlators of arbitrary order through the characteristic function of the photon-number distribution. We apply the framework to states affected by photon loss and dephasing, two of the dominant noise mechanisms in bosonic quantum computation, and quantify the resulting suppression of noise contributions. Our results extend virtual distillation beyond its original setting and provide a practical route toward error-mitigated measurements in bosonic quantum processors using experimentally available linear-optical resources.

quant-pharXiv:2607.04914Jul 7, 20260 citations

Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices

Yukun Zhang, Yusen Wu, You Zhou +1 more

A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $\mathrm{Tr}(ρ^k O)$ . Intuitively, one expects that computing a $k$ -th order quantity generally requires $O(k)$ copies of the state $ρ$ , and we rigorously establish this lower bound under sample access to $ρ$ . Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of $ρ$ , a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of $Θ(\sqrt{k})$ , and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory -- specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling, and evaluating other multiple nonlinear quantum observables with classical shadows.A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $\mathrm{Tr}(ρ^k O)$. Intuitively, one expects that computing a $k$-th order quantity generally requires $O(k)$ copies of the state $ρ$, and we rigorously establish this lower bound under sample access to $ρ$. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of $ρ$, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of $Θ(\sqrt{k})$, and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory -- specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling, and evaluating other multiple nonlinear quantum observables with classical shadows.

arXiv:2509.01571Sep 1, 20250 citations

Computational entanglement distillation beyond pure states: efficient protocols and fundamental limitations

Takeru Utsumi, Jacopo Rizzo, Ryuji Takagi +1 more

The information-theoretic approach to entanglement typically relies on arbitrarily many input copies and unboundedly complex operations; however, the available resources are constrained in reality. This motivates the study of entanglement theory with limited resources. One of its central questions is which quantities characterize entanglement manipulations, and so far, only the idealized case of pure states has been well explored. In this work, we address entanglement distillation from mixed states and identify the Rényi coherent information as the quantity determining the optimal rate in the worst case under two distinct resource constraints. We first characterize the sample-efficient regime, in which unbounded computational power is allowed. Our universal protocol achieves this rate without knowledge of the input state under certain polynomial rank constraints. This rate is optimal among universal protocols: we construct states whose distillable entanglement is nearly extensive, yet from which no universal sample-efficient protocol attains a rate above their Rényi coherent information. We then push this characterization to the computationally efficient frontier: the same bound holds for any efficient protocol even when the input state is known, and another universal protocol achieves this rate efficiently under additional polynomial constraints on the marginal ranks. Overall, our results give the Rényi coherent information a novel operational meaning in two computational settings: universal distillation with limited copies and efficient distillation even with knowledge of the input state.The information-theoretic approach to entanglement typically relies on arbitrarily many input copies and unboundedly complex operations; however, the available resources are constrained in reality. This motivates the study of entanglement theory with limited resources. One of its central questions is which quantities characterize entanglement manipulations, and so far, only the idealized case of pure states has been well explored. In this work, we address entanglement distillation from mixed states and identify the Rényi coherent information as the quantity determining the optimal rate in the worst case under two distinct resource constraints. We first characterize the sample-efficient regime, in which unbounded computational power is allowed. Our universal protocol achieves this rate without knowledge of the input state under certain polynomial rank constraints. This rate is optimal among universal protocols: we construct states whose distillable entanglement is nearly extensive, yet from which no universal sample-efficient protocol attains a rate above their Rényi coherent information. We then push this characterization to the computationally efficient frontier: the same bound holds for any efficient protocol even when the input state is known, and another universal protocol achieves this rate efficiently under additional polynomial constraints on the marginal ranks. Overall, our results give the Rényi coherent information a novel operational meaning in two computational settings: universal distillation with limited copies and efficient distillation even with knowledge of the input state.

quant-pharXiv:2610.06787Oct 6, 20260 citations

Learning the full Pauli profile of the virtually distilled quantum state

ρ^m/\text{tr}(ρ^m)

has so far required exponentially many copies of

ρ

. We show that all

4^n

squared Pauli moments

[\text{tr}(Pρ^m)]^2

can be learned to additive error

\varepsilon

with confidence

1-δ

from one

2m

-replica measurement setting using

O(m[n+\log(1/δ)]/\varepsilon^2)

copies. This is an exponential speedup in the system size

n

over previous protocols. For

m = 2

m

-replica protocol recovers the signed moments

\text{tr}(Pρ^m)

using

O(m[n+\log(1/δ)]/\varepsilon^4)

copies. For fixed

m

in the stated lower-bound regime, it attains the optimal replica number, since any protocol with fewer replicas requires exponentially many copies.

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 revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state

\rho

, estimate Tr

(P\rho)

for some set of Pauli operators

F

to within additive error

\epsilon

. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate

\vert \text{Tr}(P\rho)

for all

P

using

O(n/\epsilon^{4})

copies, but with

k\leq n

qubits of memory,

\Omega(2^{(n-k)/3})

copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on

\epsilon ?

What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subset

A

of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to

\log\vert A\vert

factors. •We show any protocol that makes poly

(n)

-copy measure-ments must make

\Omega(1/\epsilon^{4})

measurements. •For any protocol that makes poly

(n)

-copy measurements and only has

k < n

qubits of memory, we show that

\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})

copies are necessary and sufficient. The protocols we propose can also estimate the actual values

\text{Tr}(P\rho)

, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

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

: 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. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. 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

A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as

\mathrm{Tr}(ρ^k O)

. Intuitively, one expects that computing a

k

-th order quantity generally requires

O(k)

copies of the state

ρ

, and we rigorously establish this lower bound under sample access to

ρ

. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of

ρ

, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of

Θ(\sqrt{k})

, and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory -- specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling, and evaluating other multiple nonlinear quantum observables with classical shadows.