⚛️ quantum physics

KrMM Recurrences: HPC-Enhanced Estimators for Nonlinear Classical Shadows

This paper introduces an HPC-enhanced method for estimating polynomial functions within the classical shadows framework by exploiting a specific computational kernel's structure to enable massive parallelization via row-wise partitioning and SIMD vectorization, thereby significantly reducing computational costs and achieving near-ideal scaling for otherwise intractable quantum state property estimation.

Original authors: Matthias Gruber, Sabrina Herbst, Ivona Brandic, Vincenzo De Maio

Published 2026-10-20

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthias Gruber, Sabrina Herbst, Ivona Brandic, Vincenzo De Maio

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

Quantum computers promise to solve problems that would take today's machines thousands of years to crack, but they are currently fragile and difficult to control. To make sense of these machines without breaking them, scientists use a technique called "classical shadows." Imagine trying to understand the shape of a complex object in a dark room by throwing a handful of flashlights at it from random angles and recording the shadows they cast. You cannot see the whole object at once, but by collecting enough of these random snapshots, you can mathematically reconstruct its most important features. This method allows researchers to estimate properties of quantum states, such as how entangled particles are or how sensitive a system is to changes, without needing to store the entire, impossibly large description of the quantum state in a computer's memory. However, as scientists try to measure more complex, non-linear properties, the number of snapshots required explodes, and the calculations needed to process them become so heavy that even the fastest supercomputers struggle to keep up.

In a recent study, researchers at TU Wien and the University of Leicester identified a hidden pattern within these difficult calculations that allows them to be solved much faster. They discovered that the mathematical engine driving these estimators, which involves multiplying many small matrices together in a specific chain, could be broken apart into independent rows. Instead of forcing a computer to process the entire massive calculation as a single, slow block, the team realized they could slice the work into thousands of tiny, independent tasks. Each task only needed to know the result of the previous step in its own specific line, meaning they could all be calculated simultaneously by different parts of a processor without getting in each other's way. By rewriting the software to exploit this structure and using specialized instructions built into modern computer chips to handle these tiny tasks in parallel, the team created a new way to process quantum data that is significantly more efficient than previous methods.

The researchers tested this new approach on two specific, challenging problems: verifying whether particles are entangled in a mixed state and estimating the Quantum Fisher Information, a measure of how precisely a quantum system can be used for sensing. They ran simulations using data that mimicked real quantum experiments, testing systems with up to twelve qubits, the basic units of quantum information. In these tests, their method demonstrated the ability to process data with a speed and efficiency that scales almost perfectly as more computer cores are added. For example, when they used a large number of measurements to estimate the properties of a system with ten qubits, their approach was hundreds of times faster than the standard software used by the community today. The team also showed that their method works well in an "online" setting, where data arrives continuously from a quantum device, allowing the computer to update its estimates in real-time and stop the experiment the moment it has gathered enough information, rather than waiting for a fixed number of measurements.

A key part of their success was how they managed the flow of data inside the computer's memory. By organizing the data so that the processor could grab and process it in a continuous, predictable stream, they avoided the bottlenecks that usually slow down complex calculations. This allowed the system to keep the processor's mathematical units busy almost all the time, achieving a level of performance that is very close to the theoretical maximum for the hardware they used. The study confirms that while the fundamental difficulty of these quantum problems remains, the way we calculate them can be radically improved. The researchers did not claim to have solved the problem of quantum measurement complexity, nor did they suggest that this method eliminates the need for massive amounts of data. Instead, they provided a practical, scalable tool that makes currently intractable problems solvable on existing hardware, opening the door for more detailed analysis of quantum systems as they continue to grow in size and complexity.

Technical Summary: KrMM Recurrences: HPC-Enhanced Estimators for Nonlinear Classical Shadows

Problem Statement

While classical shadows have become a standard framework for efficiently estimating linear properties of quantum states from randomized measurements, estimating nonlinear properties (such as purity, mixed-state entanglement, and Quantum Fisher Information) remains computationally prohibitive. These properties often require evaluating polynomial functions of the quantum state, typically formulated using U-statistics.

The core bottleneck is the combinatorial explosion inherent in these estimators. For a polynomial of order $k$ and $N$ measurements, the computational complexity scales as $O(N^k)$ . Even with "batch shadows" (which group measurements to reduce combinations), the requirement to store and manipulate exponentially large density matrices ( $2^n \times 2^n$ ) or perform massive numbers of matrix multiplications creates a severe bottleneck for systems with more than a few qubits. Existing methods struggle to scale to the system sizes ( $n \approx 10$ ) and measurement counts ( $N \approx 10^8$ ) required for practical verification tasks.

Methodology

The authors identify a recurring computational kernel within polynomial classical shadow estimators and reformulate it as a Kronecker-matrix-matrix (KrMM) recurrence.

1. The KrMM Recurrence Formulation

The estimation of polynomial quantities is expressed as a chain of recurrences:
$C_t = \alpha_t A_t F_t + \beta_t C_{t-1}$
where $F_t$ possesses a Kronecker structure ( $F_t = \bigotimes_{j=1}^n G_{tj}$ ), composed of $n$ small $2 \times 2$ complex matrices. This structure is intrinsic to classical shadows due to the tensor product nature of qubit systems.

2. Row-Wise Decomposition and Parallelism

The key insight is that the Kronecker structure allows the recurrence to be decomposed row-wise. Instead of computing the full matrix product at each step, the computation can be split into $M$ (where $M=2^n$ ) independent row kernels, $\mathcal{K}_i$ .

Independence: Each row kernel $\mathcal{K}_i$ computes the $i$ -th row of the result based only on the previous timestep's row state and shared input data.
Parallelization: This independence allows for massive parallelization across CPU cores or nodes. Each worker processes a subset of rows, aggregating results only at the final step.

3. Execution Model and SIMD Vectorization

To maximize efficiency on High-Performance Computing (HPC) hardware, the authors implement a custom execution model:

Sliced-Row Multiply (SRM): They adopt the SRM operation (from the FastKron algorithm) to apply Kronecker factors without materializing the full $2^n \times 2^n$ matrix. This reduces the cost of matrix-vector products from $O(M^3)$ to $O(M \log M)$ .
Fused Row Kernels: The recurrence is treated as a single fused computation. Intermediate states are kept in vector registers, avoiding intermediate memory writes and reducing memory traffic.
Custom SIMD Vectorization: A specialized data layout and SIMD (Single Instruction, Multiple Data) strategy using architecture-specific intrinsics (e.g., AVX-512) are employed to handle complex arithmetic and data shuffling efficiently. This is critical for maintaining high throughput on modern AMD EPYC processors.

Key Contributions

Identification of a Computational Kernel: The paper identifies that polynomial classical shadow estimators (both online and batched) share a common KrMM recurrence structure.
Row-Wise Decomposition: The authors demonstrate that this structure permits a decomposition into independent row-wise calculations, enabling massive parallelism without inter-worker communication during the kernel execution.
HPC-Optimized Implementation: They provide a custom implementation featuring:
- A fused execution model to minimize memory access.
- A custom SIMD vectorization scheme tailored for complex Kronecker operations.
- Scalability to distributed HPC environments with near-ideal strong scaling.

Experimental Results

The approach was evaluated on two practical applications: Mixed-State Entanglement Verification (using Werner states) and Quantum Fisher Information (QFI) estimation (using random rank states).

Scalability and Speedup:
- The method achieves near-ideal parallel scaling (efficiency > 0.95) on multi-node clusters (up to 16 nodes) because communication is limited to a final reduction step.
- Significant speedups are observed compared to the state-of-the-art baseline (RandomMeas.jl). For $n=10$ qubits and $N=10^6$ measurements, the approach yields a 516x speedup, while for $n=8$ qubits and $N=10^8$ measurements, the speedup is 1.66x.
- On single nodes, the method achieves high hardware utilization (up to ~75% of peak FMA throughput on Zen 4/5 architectures) by keeping data buffers within L1/L2 caches.
Accuracy and Convergence:
- The parallelized estimators maintain the same statistical accuracy as the sequential baselines.
- Online Algorithms: The implementation supports online estimators that update estimates on-the-fly, allowing for convergence monitoring and early stopping. This provides a "truly hybrid" workflow where classical processing keeps pace with quantum data acquisition.
- Batch Algorithms: For offline settings, the batched approach significantly outperforms the baseline, reducing runtimes from hours/days to minutes for 8-qubit systems.
Hardware Performance:
- The custom SIMD vectorization consistently outperforms auto-vectorized baselines, particularly on AVX-512 architectures (Zen 4, Zen 5), where specific permutation intrinsics are crucial for performance.

Significance and Claims

The paper claims that this work provides a practical pathway to solving inherently difficult nonlinear estimation problems in quantum information that were previously intractable due to computational costs.

Practical Advantages: By exploiting the Kronecker structure, the authors enable the estimation of high-order moments and properties for system sizes ( $n \approx 10$ ) and measurement counts relevant to current and near-term quantum hardware.
Hybrid Workflows: The ability to run these estimators in an online fashion allows for real-time monitoring of quantum system convergence, a feature previously difficult to implement efficiently.
Limitations: The authors modestly note that while their method drastically improves the constant factors and parallel efficiency, it does not eliminate the fundamental exponential sample complexity ( $N$ ) or memory requirements dictated by the physics of the problem. The approach extends the feasible range of problem sizes but remains bounded by the exponential scaling of the underlying quantum state space.

In summary, the work transforms a combinatorially difficult estimation problem into a highly parallelizable linear algebra task, leveraging modern HPC architectures to make nonlinear classical shadow tomography a viable tool for quantum hardware verification and metrology.