arXiv:2605.01433
Online Estimation of Partial Transpose Moments via Fast Classical Updates
Hyunho Cha, Jungwoo Lee
Abstract
Partial-transpose (PT) moments are among the most practically relevant nonlinear quantities accessible from local Pauli classical shadows, because they directly underpin mixed-state entanglement certification and recent PT-moment-based phase diagnostics. The online framework of Marso \emph{et al.} rewrote the exact PT-moment statistic into a fixed-memory recurrence that updates a small collection of accumulated matrices after each new shadow snapshot. Its update cost is independent of the shot number, but each step treats the incoming partially transposed snapshot as a generic dense matrix. Therefore, the arithmetic cost scales cubically with the dimension of the Hilbert space. We show that the same estimator can be updated exactly in subcubic time per shot while retaining the same memory. The key point is that the accumulated matrices become dense, but the fresh partially transposed snapshot still factorizes into local factors. Right-multiplication by that factorized snapshot can therefore be executed by exact column-pair sweeps. For the second PT moment, we further optimize the process by utilizing a Pauli basis update.
AI Summary
The paper addresses the classical per-shot cost of fixed-memory online estimation of partial-transpose (PT) moments from local Pauli shadows. It retains an existing unbiased estimator and its recurrence over accumulated dense matrices, but changes how each incoming partially transposed snapshot is applied. Although accumulated matrices become dense, each fresh snapshot remains a tensor product of single-qubit factors; partial transpose only changes signs of appropriate $Y$ components. Applying these factors through successive column-pair sweeps computes dense-matrix–snapshot products exactly in $O(d^2\log d)$ time. For moments through order $m$, this reduces per-shot arithmetic from the standard dense-multiplication baseline $O(md^3)$ to $O(md^2\log d)$, retaining $O(md^2)$ memory, where $d=2^n$. For the second moment, a separate algorithm maintains the squared norm of accumulated Pauli coefficients. Each snapshot has only $d$ nonzero coefficients, giving $O(d)$ per-shot work and $O(d^2)$ memory. Single-threaded NumPy benchmarks cover $9$–$12$ qubits, moment orders $2$–$5$, and ten shots. At $12$ qubits and order five, reported runtime decreases from $302.0$ to $19.68$ seconds; the specialized second-moment implementation takes $0.006564$ seconds versus $76.18$ seconds for the baseline. The stated limitations are exponential dense-storage requirements, no acceleration of the complementary reconstruction-free estimator, and no established extension to arbitrary measurement ensembles or nonlinear shadow functionals. Optimality and lower bounds remain open. The estimator itself and its statistical properties are unchanged.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 6 pages