⚛️ quantum physics

An Online Approach for Entanglement Verification Using Classical Shadows

This paper proposes an online algorithmic framework for entanglement verification using classical shadows that incrementally processes measurement snapshots to efficiently certify mixed-state entanglement via PT-moments, offering a trade-off between memory and computational cost while requiring fewer samples than state-of-the-art offline methods.

Original authors: Marwa Marso, Sabrina Herbst, Jadwiga Wilkens, Vincenzo De Maio, Ivona Brandic, Richard Kueng

Published 2026-03-30

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Marwa Marso, Sabrina Herbst, Jadwiga Wilkens, Vincenzo De Maio, Ivona Brandic, Richard Kueng

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 running a high-stakes cooking competition. You have a Chef (the quantum computer) who is incredibly talented but moves in slow motion. Every time the Chef prepares a dish (a quantum measurement), it takes a long time. However, you also have a Judge (the classical computer) who is lightning-fast, capable of tasting and analyzing thousands of dishes in the time it takes the Chef to flip a single pancake.

In current quantum experiments, the process is inefficient:

The Chef cooks a dish.
The Judge sits on their hands, doing absolutely nothing, waiting for the Chef to finish the next one.
This repeats until the Chef has cooked everything.
Only then does the Judge start tasting and grading the entire batch at once.

This paper proposes a new way to run the competition: The Online Approach. Instead of waiting, the Judge tastes and grades every dish the moment it arrives, updating their final score in real-time.

The Problem: Finding "Entanglement"

In the quantum world, "entanglement" is like a secret handshake between two particles. If they are entangled, they are deeply connected in a way that classical physics can't explain. Detecting this connection is crucial for quantum computing, but it's hard because quantum states are "noisy" (like a radio with static).

To find this connection, scientists use a mathematical tool called Classical Shadows.

The Analogy: Imagine trying to describe a complex 3D sculpture by taking 2D photos of it from random angles. You don't need to see the whole sculpture to know its shape; you just need enough random snapshots.
The Challenge: To prove the particles are entangled, you need to combine these snapshots in very specific, complex ways (mathematically called "moments"). Doing this for millions of snapshots usually requires storing all the data first and crunching the numbers later, which is slow and memory-heavy.

The Solution: Two New "Online" Judges

The authors created two new algorithms (methods for the Judge) that work while the Chef is still cooking. They offer a choice between Memory and Speed, much like choosing between a backpack and a briefcase.

1. The "Backpack" Method (Memory Efficient)

How it works: The Judge keeps a simple list of every single photo (snapshot) taken. When a new photo arrives, the Judge quickly looks back at the list, picks a few random past photos, and combines them with the new one to update the score.
The Trade-off: This method is great for large systems (many particles) because it doesn't need a huge hard drive. However, as the list of photos grows, the Judge has to search through more and more of it to find the right combinations, which gets slower and slower over time.
Best for: Large quantum systems where you only need a simple check.

2. The "Briefcase" Method (Speed Efficient)

How it works: The Judge doesn't keep the photos. Instead, they carry a small, fixed set of "summary folders" (matrices). Every time a new photo arrives, the Judge instantly updates these folders and throws the photo away.
The Trade-off: This is incredibly fast because the Judge never has to search through a long list. However, the "summary folders" get huge if the quantum system is large, requiring a massive amount of memory (like trying to carry a library in a briefcase).
Best for: Smaller systems where you need to do very complex, high-level analysis quickly.

Why This Matters

The paper demonstrates that by using these online methods, the Judge can detect entanglement faster and with fewer samples than the old "wait-and-see" methods.

Efficiency: The online Judge uses every piece of data immediately. The old method wasted data by discarding correlations between different batches of shots.
Real-Time Results: Instead of waiting until the experiment is over to know if the quantum computer worked, you can know while it's running. If the "entanglement score" crosses a certain line, you know immediately that the particles are connected.

The Bottom Line

This research is about filling the silence. In the gap between quantum measurements, where classical computers used to sit idle, we can now do useful work. By treating quantum data like a live stream rather than a static file, we make quantum experiments faster, more efficient, and capable of solving harder problems.

It turns the quantum experiment from a "take a picture, develop it later" process into a "live broadcast" where the analysis happens as the story unfolds.

1. Problem Statement

The paper addresses a fundamental inefficiency in current hybrid quantum-classical protocols, particularly within the Noisy Intermediate-Scale Quantum (NISQ) regime.

The Asymmetry: Quantum measurements are slow (limited by device reset times and shot rates), while classical processors are fast and capable of parallelization.
The Bottleneck: Existing protocols treat data acquisition and post-processing as two separate phases. All measurement data is collected first, and classical processing (e.g., state reconstruction or entanglement verification) occurs only after the experiment concludes. This leaves the classical processor idle during the "slack time" between shots and creates a massive memory bottleneck when processing large datasets offline.
The Specific Challenge: Detecting entanglement in mixed states is difficult. While the Partial Transpose (PT) spectrum provides a rigorous condition for entanglement (NPT criterion), accessing it experimentally usually requires full state tomography. A practical alternative is using PT-moments ( $P^{(m)} = \text{Tr}[(\rho^{TB})^m]$ ), which can be estimated via randomized measurements (Classical Shadows). However, estimating these nonlinear moments unbiasedly involves a combinatorial cost that scales poorly with the number of shots ( $T$ ) and moment order ( $m$ ).

2. Methodology

The authors propose reformulating Classical Shadow protocols as online algorithms. Instead of storing all snapshots and processing them later, the classical estimator is updated incrementally as each new measurement snapshot arrives.

Core Framework: Classical Shadows

Snapshot Generation: For each shot, a random local Clifford unitary is applied, followed by a computational basis measurement. The outcome $(U, b)$ is converted into a "snapshot" $\hat{\rho}_t = \mathcal{M}^{-1}(U^\dagger |b\rangle\langle b| U)$ .
Unbiased Estimation: The expectation of the snapshot equals the true state ( $\mathbb{E}[\hat{\rho}] = \rho$ ). Nonlinear quantities like PT-moments are estimated by taking products of independent snapshots.

Proposed Online Estimators

The paper introduces two complementary online algorithms to navigate the trade-off between memory footprint and per-shot computational cost:

A. Memory-Efficient Estimator (No Reconstruction)

Mechanism: This algorithm processes the raw measurement record (bit outcomes and Pauli axes) directly without ever constructing the full $2^N \times 2^N$ snapshot matrices.
Update Rule: It utilizes a recursive update formula derived from the U-statistic definition. When a new shot $T+1$ arrives, it updates the estimate by combining the new snapshot with all $(m-1)$ -tuples of previous shots.
Complexity:
- Memory: $O(TN)$ (linear in shots, storing raw data).
- Compute: $O(T^{m-1})$ per shot (combinatorial update).
Use Case: Suitable for large system sizes ( $N$ ) where storing density matrices is impossible, provided the moment order $m$ and shot count $T$ are moderate.

B. Data-Locality Estimator (With Reconstruction)

Mechanism: This algorithm maintains a fixed set of $m$ accumulated matrices ( $A_0, \dots, A_{m-1}$ ) that store the running sums of snapshot products.
Update Rule: Upon receiving a new snapshot $\hat{\rho}_{T+1}$ , the matrices are updated via simple matrix additions and multiplications: $A_k \leftarrow A_k + A_{k-1} \hat{\rho}_{T+1}$ . The raw snapshot is discarded immediately.
Complexity:
- Memory: $O(m \cdot 4^N)$ (exponential in system size $N$ , but independent of $T$ ).
- Compute: $O(m \cdot 8^N)$ per shot (constant with respect to $T$ ).
Use Case: Suitable for smaller systems where memory allows storing matrices, but high moment orders ( $m$ ) or massive shot counts ( $T$ ) are required.

3. Key Contributions

Online Paradigm Shift: The work redefines entanglement verification from a purely offline diagnostic to a protocol running concurrently with the experiment, exploiting the reset-latency window of NISQ devices.
Two Novel Estimators: The authors provide two unbiased online estimators that characterize the fundamental trade-off between memory and compute.
- One scales to large $N$ with low $m$ (low memory, high compute).
- One handles high $m$ with small $N$ (high memory, low compute).
Statistical Efficiency: Unlike "batched" shadow methods (which average shots into blocks and discard cross-block correlations), the online U-statistic utilizes all $\binom{T}{m}$ combinations of snapshots. This results in significantly lower variance and requires fewer total shots to detect entanglement.
Theoretical Derivation: The paper provides rigorous derivations for the online update rules, proving they remain unbiased and coinciding with the standard offline U-statistic.

4. Results

The authors validated their approach using Werner states (mixed states with tunable entanglement) across 2, 4, 6, and 8 qubits.

Entanglement Detection: The online estimators successfully detected entanglement (by observing negative values in the elementary symmetric polynomials of the PT spectrum) on-the-fly.
Sample Efficiency: Compared to the state-of-the-art "batched shadow" baseline, the online estimator required substantially fewer shots to cross the entanglement threshold. For example, in 6-qubit systems, the online method detected entanglement where the batched method failed entirely within the same shot budget due to higher variance.
Runtime Scaling:
- The reconstruction-free estimator scaled to 10 qubits for low moments ( $m=2$ ) but became computationally expensive for $m=3$ due to the polynomial growth in $T$ .
- The reconstruction-based estimator handled high moments ( $k=18$ ) on 8 qubits efficiently but was limited by memory to $N \lesssim 8$ .
Convergence: The estimators converged to stable negative values (certifying NPT entanglement) within reasonable shot counts (e.g., ~4,000 shots for 2 qubits, ~250,000 for 6 qubits with high-order moments).

5. Significance

Resource Optimization: The work demonstrates that the "idle time" between quantum shots is a valuable resource that can be utilized for real-time classical processing, effectively turning a bottleneck into an opportunity.
Scalability: By avoiding the need to store massive datasets before processing, the online approach makes entanglement verification feasible for larger systems and higher-order moments that were previously computationally prohibitive in an offline setting.
Architectural Model: The paper argues that the "offline" assumption is a design choice, not a fundamental limitation. It proposes that future hybrid quantum-classical architectures should interleave computation with data acquisition to maximize efficiency.
Practical Impact: This approach enables real-time feedback loops in quantum experiments, allowing researchers to verify entanglement or adjust parameters during the experiment rather than waiting for post-processing, which is critical for error mitigation and adaptive protocols in the NISQ era.