⚛️ quantum physics

Optimal randomized measurements for a family of non-linear quantum properties

This paper introduces the observable-driven randomized measurement (ORM) protocol, which achieves optimal sample complexity for estimating the non-linear quantity ${\rm Tr}(O\rho^2)$ for arbitrary observables, outperforming classical shadows in efficiency while offering an efficient Clifford circuit implementation and a complementary braiding protocol for multiple low-rank observables.

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

Published 2026-03-30

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out the secrets of a mysterious, invisible object (a quantum state). Usually, when you look at these objects, the laws of physics are very strict: you can only ask "Yes/No" questions about simple things, like "Is the object red?" or "Is it heavy?" These are linear questions, and we are pretty good at answering them.

But sometimes, you need to ask non-linear questions. These are trickier. Instead of asking "Is it red?", you might need to ask, "How much does the redness interact with the blueness?" or "How 'pure' is the object's color?" In the quantum world, these questions are crucial for things like fixing errors in quantum computers or simulating new materials.

The problem? The standard tools we have are like trying to measure the temperature of a cup of coffee by taking a single sip, spitting it out, and hoping to guess the temperature of the whole cup. It takes way too many sips (samples) to get an accurate answer, and the math gets messy.

This paper introduces a new, super-smart detective tool called ORM (Observable-Driven Randomized Measurement). Here is how it works, using some everyday analogies:

1. The Old Way: The "Blindfolded Taster" (Classical Shadows)

Imagine you want to know the flavor profile of a complex soup. The old method (called "Classical Shadows") is like a blindfolded taster who takes a spoonful, tastes it, writes down a generic note ("tastes salty"), and throws the spoon away. To figure out the exact balance of spices (the non-linear property), they have to take thousands of spoonfuls, write thousands of notes, and then use a supercomputer to guess the recipe. It's accurate, but it's incredibly slow and wasteful.

2. The New Way: The "Targeted Chef" (ORM)

The authors of this paper say, "Why are we tasting blindly? Let's look at the recipe first!"

Their new protocol, ORM, is like a chef who knows exactly which spice they are looking for (the "Observable").

The Setup: Instead of a random spoonful, the chef sets up a special sieve (a random unitary transformation) that separates the soup into two bowls based on the specific spice they care about.
The Magic: If the chef is looking for "spiciness," the sieve separates the spicy bits from the non-spicy bits. They then taste only the spicy bowl and the non-spicy bowl separately.
The Result: Because they are looking at the right parts of the soup, they need far fewer spoonfuls to get the same answer. In fact, for many common questions, they need the absolute minimum number of spoonfuls possible. It's like finding a needle in a haystack by knowing exactly what the needle looks like and using a magnet, rather than sifting through the whole haystack with a spoon.

3. The "Virtual Cooling" Trick

One of the coolest applications they show is called Virtual Cooling.
Imagine you have a hot cup of coffee (a noisy, imperfect quantum state). You want to know what the coffee would taste like if it were ice cold (a pure, perfect state).

Normally, you'd have to wait hours for it to cool down.
With ORM, you can mathematically "cool" the coffee instantly. By measuring the coffee in a specific, clever way, the math cancels out the "heat" (noise) and reveals the flavor of the cold coffee. It's like having a time machine for temperature!

4. The "Braiding" Technique (BRM)

The paper also introduces a second tool called BRM for when you have a lot of different questions to ask at once (like checking the soup for salt, pepper, garlic, and basil all at the same time).

Think of this as braiding your hair. Instead of combing each strand separately (which takes forever), you twist them together in a specific pattern.
This allows you to check multiple properties simultaneously without needing a separate "sieve" for every single question. It saves a massive amount of time and effort.

Why Does This Matter?

Efficiency: It uses significantly fewer resources (fewer "state copies" or samples). In the quantum world, every sample is expensive and hard to get.
Simplicity: The math required to process the data is much simpler. You don't need a supercomputer to figure out the answer; a regular laptop can do it quickly.
Versatility: It works for a huge variety of quantum problems, from fixing errors in quantum computers to detecting new phases of matter.

In a nutshell:
The authors found a way to stop guessing and start targeting. By tailoring their measurement tools to the specific question they want to answer, they can extract deep, complex information from quantum systems with the same ease as asking a simple question. It's a massive leap forward in making quantum computers actually useful for solving real-world problems.

1. Problem Statement

Quantum learning faces a fundamental challenge in estimating non-linear properties of quantum states, such as the state purity $\text{Tr}(\rho^2)$ or the non-linear expectation value $\text{Tr}(O\rho^2)$ for an arbitrary observable $O$ .

The Limitation of Linear Methods: Standard quantum learning protocols (like Classical Shadows) are optimized for linear properties ( $\text{Tr}(O\rho)$ ). When applied to non-linear properties using single-copy measurements, they often require $O(d)$ state copies (where $d$ is the Hilbert space dimension), which is sub-optimal.
The Gap: While optimal protocols exist for purity estimation ( $\text{Tr}(\rho^2)$ ) using Randomized Measurements (RM) with $O(\sqrt{d})$ sample complexity, it was an open question whether this optimality could be extended to general observables $O$ without requiring quantum memory or entangled measurements across multiple copies.
The Goal: Develop a single-copy protocol that estimates $\text{Tr}(O\rho^2)$ with optimal sample complexity $O(\sqrt{d})$ for a broad class of observables, while maintaining experimental feasibility.

2. Methodology

The authors propose the Observable-Driven Randomized Measurement (ORM) protocol, which integrates information about the target observable $O$ directly into the measurement strategy.

A. Core Concept: Observable-Driven Randomized Measurement (ORM)

The protocol generalizes the RM approach for purity by decomposing the target observable and tailoring the random unitary ensemble to its structure.

Decomposition: Any observable $O$ is decomposed into a sum of dichotomic observables (observables with eigenvalues $\pm 1$ ). For general observables, this is achieved via a binary expansion (Lemma 3).
Block-Diagonal Unitaries: For a dichotomic observable $O$ $O$ with eigenspaces $\Pi_+$ $Π_{+}$ and $\Pi_-$ $Π_{-}$ , the protocol uses block-diagonal random unitaries $U = \tilde{U}_+ \oplus \tilde{U}_-$ $U = \tilde{U}_{+} \oplus \tilde{U}_{-}$ .
- $\tilde{U}_+$ acts randomly on the subspace $\Pi_+$ .
- $\tilde{U}_-$ acts randomly on the subspace $\Pi_-$ .
Estimation Strategy:
- The state is rotated into the eigenbasis of $O$ .
- Block-diagonal unitaries are applied.
- Measurements are performed in the computational basis.
- Post-processing: Measurement outcomes are classified based on which eigenspace they belong to. The protocol estimates the purity of the projected states within each subspace ( $\text{Tr}(\tilde{\rho}_+^2)$ and $\text{Tr}(\tilde{\rho}_-^2)$ ) and computes their weighted difference to estimate $\text{Tr}(O\rho^2)$ .
Theoretical Optimality: The authors prove that for observables with a large trace norm ( $\|O\|_1 = \Omega(d)$ ), including all Pauli and local observables, the sample complexity is $O(\sqrt{d})$ . This matches the fundamental lower bound for single-copy schemes, closing the gap between theoretical limits and achievable protocols.

B. Efficient Circuit Implementations

To address the practical difficulty of implementing arbitrary block-diagonal unitaries, the paper introduces several optimizations:

Pauli Observables: For Pauli operators, the diagonalization circuit is a simple Clifford circuit. The block-diagonal unitaries can be implemented as independent random unitaries on $n-1$ qubits, or even as tensor products of local single-qubit unitaries.
Clifford Circuits: The protocol can be implemented using random Clifford unitaries (which form a 3-design) instead of exact 4-designs, preserving the $O(\sqrt{d})$ scaling with only a constant factor overhead in precision dependence.
Pauli Sampling: For general physical observables (e.g., local Hamiltonians), the authors propose a Pauli sampling scheme. The observable is decomposed into Pauli strings, and the protocol samples these strings according to their coefficients (importance sampling). This allows estimating $\text{Tr}(O\rho^2)$ for local Hamiltonians and stabilizer fidelities with $O(\sqrt{d})$ complexity.

C. Braiding Randomized Measurement (BRM)

For low-rank observables (where the rank is constant or small), the authors introduce the Braiding Randomized Measurement (BRM) protocol.

Hybrid Approach: BRM combines the data acquisition of standard RM (global random unitaries) with the post-processing logic of Classical Shadows.
Mechanism: It virtually implements higher-order permutation operators (e.g., 3rd order for $\text{Tr}(\rho^3)$ ) by replacing one instance of the state density matrix in the estimator with the observable $O$ (computed classically).
Advantage: BRM achieves the same $O(\sqrt{d})$ sample complexity as ORM for low-rank observables but requires only global random unitaries (simpler to implement than block-diagonal ones) and significantly fewer measurement bases than Classical Shadows when estimating multiple observables simultaneously.

3. Key Results

Optimal Sample Complexity: The ORM protocol achieves a sample complexity of $O(\sqrt{d})$ for estimating $\text{Tr}(O\rho^2)$ for any observable with bounded operator norm and large trace norm. This is provably optimal for single-copy schemes.
Comparison with Classical Shadows:
- Classical Shadows require $O(d)$ samples for general observables and $O(\sqrt{d})$ only for specific cases, but often require $O(\sqrt{d})$ distinct measurement bases.
- ORM requires only $O(1)$ measurement bases (constant number of settings) regardless of system size, significantly reducing experimental overhead.
Numerical Validation:
- Virtual Cooling: Simulations on a 6-qubit Heisenberg XX model show that ORM accurately estimates $\text{Tr}(O\rho^2)/\text{Tr}(\rho^2)$ (equivalent to cooling the state) with far fewer state copies than Classical Shadows.
- Scalability: As system size $L$ increases, the number of copies required by Classical Shadows grows exponentially, while ORM remains nearly flat (scaling as $\sqrt{d}$ ).
Low-Rank Efficiency: The BRM protocol demonstrates that for low-rank observables, one can achieve optimal scaling without observable-dependent unitaries, bridging the gap between RM and Classical Shadows.

4. Significance and Applications

Error Mitigation (Virtual Distillation): The ability to efficiently estimate $\text{Tr}(O\rho^2)$ is crucial for virtual cooling and error mitigation. By estimating the second-order moment, the protocol suppresses noise from mixed states, effectively accessing properties of a "cleaner" state at a lower temperature without physical cooling.
Mixed-State Phase Detection: The protocol enables the detection of quantum phases in mixed states (e.g., symmetry-protected topological phases) using non-linear correlators, which are more robust to decoherence than linear correlation functions.
Entropic Quantities: The method facilitates the estimation of Renyi entropies and quantum Fisher information, which are vital for characterizing quantum resources and thermodynamics.
Experimental Feasibility: By reducing the requirement to constant measurement bases and utilizing Clifford circuits (compatible with current NISQ devices), the protocol makes the estimation of non-linear properties practical for near-term quantum hardware.

5. Conclusion

This work resolves a key open problem in quantum learning by demonstrating that observable information can be leveraged to achieve optimal sample complexity for non-linear property estimation. The proposed ORM and BRM protocols provide a unified, efficient, and experimentally viable framework for estimating $\text{Tr}(O\rho^2)$ , outperforming existing methods like Classical Shadows in both sample efficiency and measurement overhead. This advancement is a critical step toward scalable verification and characterization of noisy quantum systems.