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

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

Yukun Zhang, Yusen Wu, You Zhou, Xiao Yuan

Published Sep 1, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2509.01571

Related papers

Measuring Less to Learn More: Quadratic Speedup in Learning Nonlinear Properties of Quantum States

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 Tr(ρ^{k}O). Intuitively, one expects that computing a kth 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.

Physical Review Letters•Jan 20, 2026•0 citations

Learning Quantum States Without Entangled Measurements

Angus Lowe

How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.

•Oct 22, 2021•4 citations

Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States

Qi Ye, Zhenhuan Liu, Dong-Ling Deng

Inferring nonlinear features of quantum states is fundamentally important across quantum information science, but remains challenging due to the intrinsic linearity of quantum mechanics. It is widely recognized that quantum memory and coherent operations help avoid exponential sample complexity, by mapping nonlinear properties onto linear observables over multiple copies of the target state. In this work, we prove that such a conversion is not only sufficient but also necessary. Specifically, we prove that the estimation of $\mathrm{tr}(ρ^{k} O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements, whereas access to one additional replica reduces the complexity to a constant. These results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$, thereby introducing a fine-grained hierarchy of replica-based quantum advantage and resolving an open question in the literature. The technical core is a general indistinguishability principle showing that any ensemble constructed from large Haar random states via tensor products and mixtures is hard to distinguish from its average. Leveraging this principle, we further prove that $k$-replica joint measurements are also necessary for distinguishing rank-$k$ density matrices from rank-$(k-1)$ ones. Overall, our work delineates sharp boundaries on the power of joint measurements, highlighting resource-complexity trade-offs in quantum learning theory and deepening the understanding of quantum mechanics' intrinsic linearity.

arXiv:2509.24000•Sep 28, 2025•0 citations

Optimal 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$.

quant-pharXiv:2609.37781•Sep 30, 2026•0 citations

Sample-efficient estimation of nonlinear quantum state functions

Hongshun Yao, Yingjian Liu, Tengxiang Lin +1 more

Estimating nonlinear functions of quantum states is essential for quantum information processing tasks such as entropy quantification, fidelity estimation, and entanglement spectroscopy. Existing approaches based on quantum state tomography incur exponential resource overhead, while methods relying on purified query access impose significant practical constraints. Here, we introduce the quantum state function framework, which extends the swap test via a linear combination of unitaries and parameterized quantum circuits. The framework estimates any normalized degree-n polynomial function of a quantum state with precision ε using $${{{\mathcal{O}}}}(n/{\varepsilon }^{2})$$ copies, operating directly on identical copies without block-encoding or purified queries. Applied to von Neumann entropy, quantum relative entropy, and state fidelity, it achieves sample complexity $$\widetilde{{{{\mathcal{O}}}}}({\gamma }^{2}/({\varepsilon }^{2}\kappa ))$$, where κ is the minimal nonzero eigenvalue and γ a normalization factor. This framework establishes a unified paradigm for nonlinear quantum state processing, broadening the toolkit for practical quantum data analysis. Estimating nonlinear functions of quantum states is essential for quantum information processing but often computationally expensive. The quantum state function framework estimates a degree-n polynomial of a quantum state with $${{{\mathcal{O}}}}(n/{\varepsilon }^{2})$$ copies without purified query access, enabling practical entropy, fidelity, and eigenvalue estimation.

arXiv:2412.01696•Communications Physics•Jun 6, 2026•1 citation

Pauli-resolved virtual distillation

Si-Yuan Chen, Congcong Zheng, Kun Wang +1 more

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.

quant-pharXiv:2609.24132•Sep 22, 2026•0 citations
A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as Tr(ρkO)\mathrm{Tr}(ρ^k O)Tr(ρkO). Intuitively, one expects that computing a kkk-th order quantity generally requires O(k)O(k)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 Θ(k)Θ(\sqrt{k})Θ(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 Tr(ρ^{k}O). Intuitively, one expects that computing a kth 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.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
Inferring nonlinear features of quantum states is fundamentally important across quantum information science, but remains challenging due to the intrinsic linearity of quantum mechanics. It is widely recognized that quantum memory and coherent operations help avoid exponential sample complexity, by mapping nonlinear properties onto linear observables over multiple copies of the target state. In this work, we prove that such a conversion is not only sufficient but also necessary. Specifically, we prove that the estimation of tr(ρkO)\mathrm{tr}(ρ^{k} O)tr(ρkO) for a broad class of observables OOO is exponentially hard for any protocol restricted to (k−1)(k-1)(k−1)-replica joint measurements, whereas access to one additional replica reduces the complexity to a constant. These results establish, for the first time, an exponential separation between (k−1)(k-1)(k−1)- and kkk-replica protocols for any integer k>2k>2k>2, thereby introducing a fine-grained hierarchy of replica-based quantum advantage and resolving an open question in the literature. The technical core is a general indistinguishability principle showing that any ensemble constructed from large Haar random states via tensor products and mixtures is hard to distinguish from its average. Leveraging this principle, we further prove that kkk-replica joint measurements are also necessary for distinguishing rank-kkk density matrices from rank-(k−1)(k-1)(k−1) ones. Overall, our work delineates sharp boundaries on the power of joint measurements, highlighting resource-complexity trade-offs in quantum learning theory and deepening the understanding of quantum mechanics' intrinsic linearity.
Optimal single-copy estimation of quantum state moments: why Tr⁡(ρ3)\operatorname{Tr}(ρ^3)Tr(ρ3) and Tr⁡(ρ4)\operatorname{Tr}(ρ^4)Tr(ρ4) are equally hard
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 Tr⁡(ρt)\operatorname{Tr}(ρ^t)Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d)Θ(\sqrt d)Θ(d​) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2t\ge 2t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ ⁣(d⌈log⁡2t⌉1+⌈log⁡2t⌉) Θ\!\left(d^{\frac{\lceil\log_2 t\rceil}{1+\lceil\log_2 t\rceil}}\right) Θ(d1+⌈log2​t⌉⌈log2​t⌉​) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1h\geq1h≥1, all moment orders 2h−1<t≤2h2^{h-1}<t\leq2^h2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3)Θ(d^{2/3})Θ(d2/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 Ω(d1−1/t)Ω(d^{1-1/t})Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4t\geq4t≥4. 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 d\sqrt dd​.
Estimating nonlinear functions of quantum states is essential for quantum information processing tasks such as entropy quantification, fidelity estimation, and entanglement spectroscopy. Existing approaches based on quantum state tomography incur exponential resource overhead, while methods relying on purified query access impose significant practical constraints. Here, we introduce the quantum state function framework, which extends the swap test via a linear combination of unitaries and parameterized quantum circuits. The framework estimates any normalized degree-n polynomial function of a quantum state with precision ε using O(n/ε2){{{\mathcal{O}}}}(n/{\varepsilon }^{2})O(n/ε2) copies, operating directly on identical copies without block-encoding or purified queries. Applied to von Neumann entropy, quantum relative entropy, and state fidelity, it achieves sample complexity O~(γ2/(ε2κ))\widetilde{{{{\mathcal{O}}}}}({\gamma }^{2}/({\varepsilon }^{2}\kappa ))O(γ2/(ε2κ)), where κ is the minimal nonzero eigenvalue and γ a normalization factor. This framework establishes a unified paradigm for nonlinear quantum state processing, broadening the toolkit for practical quantum data analysis. Estimating nonlinear functions of quantum states is essential for quantum information processing but often computationally expensive. The quantum state function framework estimates a degree-n polynomial of a quantum state with O(n/ε2){{{\mathcal{O}}}}(n/{\varepsilon }^{2})O(n/ε2) copies without purified query access, enabling practical entropy, fidelity, and eigenvalue estimation.
Learning the full Pauli profile of the virtually distilled quantum state ρm/tr(ρm)ρ^m/\text{tr}(ρ^m)ρm/tr(ρm) has so far required exponentially many copies of ρρρ. We show that all 4n4^n4n squared Pauli moments [tr(Pρm)]2[\text{tr}(Pρ^m)]^2[tr(Pρm)]2 can be learned to additive error ε\varepsilonε with confidence 1−δ1-δ1−δ from one 2m2m2m-replica measurement setting using O(m[n+log⁡(1/δ)]/ε2)O(m[n+\log(1/δ)]/\varepsilon^2)O(m[n+log(1/δ)]/ε2) copies. This is an exponential speedup in the system size nnn over previous protocols. For m=2m = 2m=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 mmm-replica protocol recovers the signed moments tr(Pρm)\text{tr}(Pρ^m)tr(Pρm) using O(m[n+log⁡(1/δ)]/ε4)O(m[n+\log(1/δ)]/\varepsilon^4)O(m[n+log(1/δ)]/ε4) copies. For fixed mmm in the stated lower-bound regime, it attains the optimal replica number, since any protocol with fewer replicas requires exponentially many copies.