Optimal Randomized Measurements for a Family of Nonlinear Quantum Properties

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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mi>Tr</a:mi> <a:mo stretchy="false">(</a:mo> <a:mi>O</a:mi> <a:msup> <a:mi>ρ</a:mi> <a:mn>2</a:mn> </a:msup> <a:mo stretchy="false">)</a:mo> </a:math> for an arbitrary observable <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"> <e:mi>O</e:mi> </e:math> —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.