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:2505.09206 · PRX Quantum

Optimal Randomized Measurements for a Family of Nonlinear Quantum Properties

Zhenyu Du, Yifan Tang, Andreas Elben, Ingo Roth, Jens Eisert, Zhenhuan Liu

Published Dec 12, 2025• 8 citations
arXivHTMLPDF

Abstract

Quantum learning encounters fundamental challenges when estimating nonlinear properties, owing to the inherent linearity of quantum mechanics. Although recent advances in single-copy randomized measurement protocols have achieved optimal sample complexity for specific tasks like state purity estimation, generalizing these protocols to estimate broader classes of nonlinear properties without sacrificing optimality remains an open problem. In this work, we introduce the observable-driven randomized measurement (ORM) protocol enabling the estimation of Tr ( O ρ 2 ) for an arbitrary observable O —an essential quantity in quantum computing and many-body physics. We establish an upper bound for ORM’s sample complexity and show its optimality for observables with a large trace-norm, including Pauli and local observables, closing a gap in the literature. For these observables, ORM admits an efficient implementation with Clifford circuits. Numerical experiments validate that ORM requires substantially fewer state samples to achieve the same precision compared to classical shadows. Additionally, we introduce a braiding randomized measurement protocol for multiple low-rank nonlinear observables, reducing circuit complexities in practical applications.

DOI
10.1103/4rkx-xkwy

Related papers

Quantum Nonlinear Properties from a Single Measurement Setting

Zihao Li, Datong Chen, Dayue Qin +2 more

Nonlinear properties of quantum states are essential to quantum information and many-body physics, but assessing them experimentally is challenging, as it typically requires multi-copy operations or a large number of measurement settings. To address this challenge, we develop a universal framework, collision-based nonlinear estimation (CBNE), for efficiently measuring nonlinear quantities of a quantum state $ρ$, such as the higher-order expectation value ${\rm tr}(Oρ^t)$ for some observable $O$, using single-copy randomized measurements. Strikingly, our protocol requires only a single measurement setting, provided that the system dimension is sufficiently large or a few ancillary qubits are available; this contrasts with the conventional expectation that multiple measurement bases are necessary for nonlinear estimation. In addition, CBNE is observable-independent at the experimental stage, which enables simultaneous estimation of multiple nonlinear functions. It further extends to broader tasks, including the estimation of principal component properties and partial-transpose moments of quantum states. Our results provide a practical and scalable route for measuring nonlinear state properties on near-term quantum devices.

quant-pharXiv:2605.09958•May 12, 2026•5 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•1 citation

Holographic classical shadow tomography

Shuhan Zhang, Xiaozhou Feng, Matteo Ippoliti +1 more

We introduce ``holographic shadows,'' a new class of randomized measurement schemes for classical shadow tomography that achieves the optimal scaling of sample complexity for learning geometrically local Pauli operators at any lengthscale, without the need for fine-tuning protocol parameters such as circuit depth or measurement rate. Our approach utilizes hierarchical quantum circuits, such as tree quantum circuits or holographic random tensor networks. Measurements within the holographic bulk correspond to measurements at different scales on the boundary (i.e., the physical system of interests), facilitating efficient quantum state estimation across observable at all scales. Considering the task of estimating stringlike Pauli observables supported on contiguous intervals of $k$ sites in a one-dimensional system, our method achieves an optimal sample complexity scaling of $\ensuremath{\sim}{d}^{k}\mathrm{poly}(k)$, with $d$ the local Hilbert space dimension. We present a holographic minimal cut framework to demonstrate the universality of this sample complexity scaling and validate it with numerical simulations, illustrating the efficacy of holographic shadows in enhancing quantum state learning capabilities.

arXiv:2406.11788•Physical review. B./Physical review. B•Feb 18, 2025•7 citations

Optimal Shadow Estimation with Minimal Measurement Settings

Zhiyao Yang, Datong Chen, Huangjun Zhu

Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While $3$-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that $Θ(d^2)$ measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state $2$-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable $2$-designs -- from mutually unbiased bases, cyclic measurements, or shallow $\mathcal{O}(\log n)$-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires $Θ(d^2)$ bases, whereas average-case performance requires only $Θ(d)$ bases, with broad implications for quantum information theory and near-term experiments.

quant-pharXiv:2606.20003•Physical Review Letters•Jun 19, 2026•2 citations

Optimal strategies for shadow tomography with limited resources

Zhen-Peng Xu, Qi Ye, Jie Wang +3 more

Shadow tomography addresses the task of efficiently predicting many expectation values of an unknown quantum state from randomized measurements on comparatively few copies. Existing analyses promise large scaling advantages, but the optimal strategies realizing these guarantees are not always known, and the required measurements are potentially challenging to implement on current hardware. We address this gap for Pauli observables by computing optimal sample-complexity parameters and constructing optimal measurement strategies under realistic resource constraints. We focus on memoryless protocols, where each copy is measured only once, and on measurements with bounded interaction range. Our approach reduces the problem to the analysis of graph parameters of the frustration graph encoding the Pauli anticommutation relations. We provide efficient numerical methods for the general case and analytically prove that Clifford measurements are optimal in many situations. This includes all perfect graphs, all single-qubit, all two-qubit measurement scenarios, and more. Applied to Hamiltonian energy estimation, our framework yields constructive strategies and improved variance bounds for molecular benchmarks.

quant-pharXiv:2608.08429•Aug 11, 2026•3 citations

Shallow Shadows: Expectation Estimation Using Low-Depth Random Clifford Circuits

Christian Bertoni, Jonas Haferkamp, Marcel Hinsche +3 more

We provide practical and powerful schemes for learning properties of a quantum state using a small number of measurements. Specifically, we present a randomized measurement scheme modulated by the depth of a random quantum circuit in one spatial dimension. This scheme interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. We focus on the regime where depth scales logarithmically in the system size and provide evidence that this retains the desirable sample complexity properties of both extremal schemes while also being experimentally feasible. We present methods for two key tasks; estimating expectation values of certain observables from generated classical shadows and, computing upper bounds on the depth-modulated shadow norm, thus providing rigorous guarantees on the accuracy of the output estimates. We achieve our findings by bringing together tools from shadow estimation, random circuits, and tensor networks.

arXiv:2209.12924•Physical Review Letters•Jul 10, 2024•124 citations
Quantum learning encounters fundamental challenges when estimating nonlinear properties, owing to the inherent linearity of quantum mechanics. Although recent advances in single-copy randomized measurement protocols have achieved optimal sample complexity for specific tasks like state purity estimation, generalizing these protocols to estimate broader classes of nonlinear properties without sacrificing optimality remains an open problem. In this work, we introduce the observable-driven randomized measurement (ORM) protocol enabling the estimation of Tr ( O ρ 2 ) for an arbitrary observable O —an essential quantity in quantum computing and many-body physics. We establish an upper bound for ORM’s sample complexity and show its optimality for observables with a large trace-norm, including Pauli and local observables, closing a gap in the literature. For these observables, ORM admits an efficient implementation with Clifford circuits. Numerical experiments validate that ORM requires substantially fewer state samples to achieve the same precision compared to classical shadows. Additionally, we introduce a braiding randomized measurement protocol for multiple low-rank nonlinear observables, reducing circuit complexities in practical applications.
Nonlinear properties of quantum states are essential to quantum information and many-body physics, but assessing them experimentally is challenging, as it typically requires multi-copy operations or a large number of measurement settings. To address this challenge, we develop a universal framework, collision-based nonlinear estimation (CBNE), for efficiently measuring nonlinear quantities of a quantum state ρρρ, such as the higher-order expectation value tr(Oρt){\rm tr}(Oρ^t)tr(Oρt) for some observable OOO, using single-copy randomized measurements. Strikingly, our protocol requires only a single measurement setting, provided that the system dimension is sufficiently large or a few ancillary qubits are available; this contrasts with the conventional expectation that multiple measurement bases are necessary for nonlinear estimation. In addition, CBNE is observable-independent at the experimental stage, which enables simultaneous estimation of multiple nonlinear functions. It further extends to broader tasks, including the estimation of principal component properties and partial-transpose moments of quantum states. Our results provide a practical and scalable route for measuring nonlinear state properties on near-term quantum devices.
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​.
We introduce ``holographic shadows,'' a new class of randomized measurement schemes for classical shadow tomography that achieves the optimal scaling of sample complexity for learning geometrically local Pauli operators at any lengthscale, without the need for fine-tuning protocol parameters such as circuit depth or measurement rate. Our approach utilizes hierarchical quantum circuits, such as tree quantum circuits or holographic random tensor networks. Measurements within the holographic bulk correspond to measurements at different scales on the boundary (i.e., the physical system of interests), facilitating efficient quantum state estimation across observable at all scales. Considering the task of estimating stringlike Pauli observables supported on contiguous intervals of kkk sites in a one-dimensional system, our method achieves an optimal sample complexity scaling of $\ensuremath{\sim}{d}^{k}\mathrm{poly}(k)$, with ddd the local Hilbert space dimension. We present a holographic minimal cut framework to demonstrate the universality of this sample complexity scaling and validate it with numerical simulations, illustrating the efficacy of holographic shadows in enhancing quantum state learning capabilities.
Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While 333-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that Θ(d2)Θ(d^2)Θ(d2) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state 222-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable 222-designs -- from mutually unbiased bases, cyclic measurements, or shallow O(log⁡n)\mathcal{O}(\log n)O(logn)-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires Θ(d2)Θ(d^2)Θ(d2) bases, whereas average-case performance requires only Θ(d)Θ(d)Θ(d) bases, with broad implications for quantum information theory and near-term experiments.
Shadow tomography addresses the task of efficiently predicting many expectation values of an unknown quantum state from randomized measurements on comparatively few copies. Existing analyses promise large scaling advantages, but the optimal strategies realizing these guarantees are not always known, and the required measurements are potentially challenging to implement on current hardware. We address this gap for Pauli observables by computing optimal sample-complexity parameters and constructing optimal measurement strategies under realistic resource constraints. We focus on memoryless protocols, where each copy is measured only once, and on measurements with bounded interaction range. Our approach reduces the problem to the analysis of graph parameters of the frustration graph encoding the Pauli anticommutation relations. We provide efficient numerical methods for the general case and analytically prove that Clifford measurements are optimal in many situations. This includes all perfect graphs, all single-qubit, all two-qubit measurement scenarios, and more. Applied to Hamiltonian energy estimation, our framework yields constructive strategies and improved variance bounds for molecular benchmarks.
We provide practical and powerful schemes for learning properties of a quantum state using a small number of measurements. Specifically, we present a randomized measurement scheme modulated by the depth of a random quantum circuit in one spatial dimension. This scheme interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. We focus on the regime where depth scales logarithmically in the system size and provide evidence that this retains the desirable sample complexity properties of both extremal schemes while also being experimentally feasible. We present methods for two key tasks; estimating expectation values of certain observables from generated classical shadows and, computing upper bounds on the depth-modulated shadow norm, thus providing rigorous guarantees on the accuracy of the output estimates. We achieve our findings by bringing together tools from shadow estimation, random circuits, and tensor networks.