Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.01433

Online Estimation of Partial Transpose Moments via Fast Classical Updates

Hyunho Cha, Jungwoo Lee

quant-phSubmitted May 2, 2026• Announced May 5, 2026• 1 citation
v1 · May 2, 2026v2 · Sep 2, 2026
arXivHTMLPDF

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.

Comments
6 pages

Related papers

An Online Approach for Entanglement Verification Using Classical Shadows

Marwa Marso, Sabrina Herbst, Jadwiga Wilkens +3 more

Quantum measurements are slow, while classical processors are fast, yet existing hybrid protocols never exploit this asymmetry. In this work, we propose an alternative formulation of classical estimators as online algorithms that are updated incrementally upon obtaining a new sample. Classical shadows are the natural fit for this approach: designed around the principle of measuring first and asking questions later, each snapshot is a self-contained classical description that can be processed immediately and independently. As a first demonstration, we focus on mixed state entanglement verification via PT-moments, moments of the partially transposed density matrix that provide experimentally accessible sufficient conditions for entanglement. We construct two unbiased online estimators that together characterize the fundamental challenge between memory footprint and per-shot computational cost: one scales to large systems at low moment order, the other handles high moment orders at the expense of memory exponential in system size. The online estimator certifies entanglement reliably and, by exploiting all $\binom{T}{m}$ combinations of snapshots, requires fewer samples than state-of-the-art baselines, turning entanglement detection from a purely offline diagnostic into a protocol that runs concurrently with the experiment.

quant-pharXiv:2603.26602•Mar 30, 2026•3 citations

Streaming the partial-transpose moment hierarchy with order-independent quantum memory

Junxiang Huang, Xiaoyang Wang, Xiao Yuan +1 more

Partial transposition reveals mixed-state entanglement through the spectrum of $ρ_{AB}^{T_B}$, but this operator is not generally a physical state. Its power moments are accessible through collective permutations, whose coherent width grows with moment order. Here we introduce a streaming protocol that processes fresh copies sequentially while retaining one copy and a reusable ancilla. By realizing opposite cyclic permutations on the two subsystems, each measurement record yields unbiased estimators of all moments $p_2,\ldots,p_K$ through successive outcome products. For an $n$-qubit state, the protocol uses $2n+1$ active qubits independent of $K$ and $O(K\log K/ε_{\rm mom}^2)$ copies, matching $Ω(K/ε_{\rm mom}^2)$ lower bounds up to a logarithmic factor, including a PT-specific isospectral construction. Higher-order moments strengthen thermal-state entanglement certification toward the exact PPT threshold. Simulations cover pure and mixed states, and a cloud quantum processor implements a three-qubit instance.

quant-pharXiv:2606.14204•Jun 15, 2026•1 citation

Compressed Sensing Shadow Tomography

Joseph Barreto, Daniel Lidar

Estimating many local expectation values over time is a central measurement bottleneck in quantum simulation and device characterization. We study the task of reconstructing the Pauli-signal matrix $S_{ij}=\text{Tr}(O_i ρ(t_j))$ for a collection of $M$ low-weight Pauli observables $\{O_i\}_{i=1}^M$ over $N$ timesteps $\{t_j\}_{j=1}^N$, while minimizing the total number of device shots. We propose a Compressed Sensing Shadow Tomography (CSST) protocol that combines two complementary reductions. First, local classical shadows reduce the observable dimension by enabling many Pauli expectation values to be estimated from the same randomized snapshots at a fixed time. Second, compressed sensing reduces the time dimension by exploiting the fact that many expectation-value traces are spectrally sparse or compressible in a unitary (e.g., Fourier) transform basis. Operationally, CSST samples $m\ll N$ timesteps uniformly at random, collects shadows only at those times, and then reconstructs each length-$N$ signal via standard $\ell_1$-based recovery in the unitary transform domain. We provide end-to-end guarantees that explicitly combine shadow estimation error with compressed sensing recovery bounds. For exactly $s$-sparse signals in a unitary transform basis, we show that $m=O \left(s\log^2 s \log N\right)$ random timesteps suffice (with high probability), leading to total-shot savings scaling as $\widetildeΘ(N/s)$ (i.e., up to polylogarithmic factors) relative to collecting shadows at all $N$ timesteps. For approximately sparse signals, the reconstruction error decomposes into a compressibility (tail) term plus a noise term. We present numerical experiments on noisy many-qubit dynamics that support strong Fourier compressibility of Pauli traces and demonstrate substantial shot reductions with accurate reconstruction.

quant-pharXiv:2602.12518•Physical Review A•Feb 16, 2026•1 citation

Optimal Entanglement Certification from Moments of the Partial Transpose

Xiao‐Dong Yu, Satoya Imai, Otfried Gühne

For the certification and benchmarking of medium-size quantum devices, efficient methods to characterize entanglement are needed. In this context, it has been shown that locally randomized measurements on a multiparticle quantum system can be used to obtain valuable information on the so-called moments of the partially transposed quantum state. This allows one to infer some separability properties of a state, but how to use the given information in an optimal and systematic manner has yet to be determined. We propose two general entanglement detection methods based on the moments of the partially transposed density matrix. The first method is based on the Hankel matrices and provides a family of entanglement criteria, of which the lowest order reduces to the known p_{3}-positive-partial-transpose criterion proposed in A. Elben et al. [Phys. Rev. Lett. 125, 200501 (2020)PRLTAO0031-900710.1103/PhysRevLett.125.200501]. The second method is optimal and gives necessary and sufficient conditions for entanglement based on some moments of the partially transposed density matrix.

arXiv:2103.06897•Physical Review Letters•Aug 4, 2021•79 citations

Many-Body Entropies and Entanglement from Polynomially Many Local Measurements

Benoît Vermersch, Marko Ljubotina, J. I. Cirac +3 more

Estimating global properties of many-body quantum systems such as entropy or bipartite entanglement is a notoriously difficult task, typically requiring a number of measurements or classical postprocessing resources growing exponentially in the system size. In this work, we address the problem of estimating global entropies and mixed-state entanglement via partial-transposed (PT) moments and show that efficient estimation strategies exist under the assumption that all the spatial correlation lengths are finite. Focusing on one-dimensional systems, we identify a set of approximate factorization conditions (AFCs) on the system density matrix, which allow us to reconstruct entropies and PT moments from information on local subsystems. This identification yields a simple and efficient strategy for entropy and entanglement estimation. Our method could be implemented in different ways, depending on how information on local subsystems is extracted. Focusing on randomized measurements providing a practical and common measurement scheme, we prove that our protocol requires only polynomially many measurements and postprocessing operations, assuming that the state to be measured satisfies the AFCs. We prove that the AFCs hold for finite-depth quantum-circuit states and translation-invariant matrix-product density operators and provide numerical evidence that they are satisfied in more general, physically interesting cases, including thermal states of local Hamiltonians. We argue that our method could be practically useful to detect bipartite mixed-state entanglement for large numbers of qubits available in today’s quantum platforms. Published by the American Physical Society 2024

arXiv:2311.08108•Physical Review X•Aug 26, 2024•23 citations

Sample Complexity for Embedded Multipartite Entanglement Witness via Pauli and Clifford Classical Shadows

Ziran Zhang

Detecting multipartite entanglement in many qubit systems is measurement-intensive, motivating protocols that estimate only selected observables with provable efficiency. In this work we use the classical shadow protocol to study the sample complexity required to estimate a family of subsystem $n$-partite entanglement witness embedded in an larger $N$-qubit system. We derive ensemble dependent variance bounds that lead to qualitatively distinct scaling for the snapshots cost at fixed additive error $ε$ with numerical simulations confirm these trends, exhibiting a clear crossover from Pauli favorable performance for local witness to Clifford favorable performance as the witness becomes more global.

quant-pharXiv:2601.00859•Dec 31, 2025•0 citations
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.
Quantum measurements are slow, while classical processors are fast, yet existing hybrid protocols never exploit this asymmetry. In this work, we propose an alternative formulation of classical estimators as online algorithms that are updated incrementally upon obtaining a new sample. Classical shadows are the natural fit for this approach: designed around the principle of measuring first and asking questions later, each snapshot is a self-contained classical description that can be processed immediately and independently. As a first demonstration, we focus on mixed state entanglement verification via PT-moments, moments of the partially transposed density matrix that provide experimentally accessible sufficient conditions for entanglement. We construct two unbiased online estimators that together characterize the fundamental challenge between memory footprint and per-shot computational cost: one scales to large systems at low moment order, the other handles high moment orders at the expense of memory exponential in system size. The online estimator certifies entanglement reliably and, by exploiting all (Tm)\binom{T}{m}(mT​) combinations of snapshots, requires fewer samples than state-of-the-art baselines, turning entanglement detection from a purely offline diagnostic into a protocol that runs concurrently with the experiment.
Partial transposition reveals mixed-state entanglement through the spectrum of ρABTBρ_{AB}^{T_B}ρABTB​​, but this operator is not generally a physical state. Its power moments are accessible through collective permutations, whose coherent width grows with moment order. Here we introduce a streaming protocol that processes fresh copies sequentially while retaining one copy and a reusable ancilla. By realizing opposite cyclic permutations on the two subsystems, each measurement record yields unbiased estimators of all moments p2,…,pKp_2,\ldots,p_Kp2​,…,pK​ through successive outcome products. For an nnn-qubit state, the protocol uses 2n+12n+12n+1 active qubits independent of KKK and O(Klog⁡K/εmom2)O(K\log K/ε_{\rm mom}^2)O(KlogK/εmom2​) copies, matching Ω(K/εmom2)Ω(K/ε_{\rm mom}^2)Ω(K/εmom2​) lower bounds up to a logarithmic factor, including a PT-specific isospectral construction. Higher-order moments strengthen thermal-state entanglement certification toward the exact PPT threshold. Simulations cover pure and mixed states, and a cloud quantum processor implements a three-qubit instance.
Estimating many local expectation values over time is a central measurement bottleneck in quantum simulation and device characterization. We study the task of reconstructing the Pauli-signal matrix Sij=Tr(Oiρ(tj))S_{ij}=\text{Tr}(O_i ρ(t_j))Sij​=Tr(Oi​ρ(tj​)) for a collection of MMM low-weight Pauli observables {Oi}i=1M\{O_i\}_{i=1}^M{Oi​}i=1M​ over NNN timesteps {tj}j=1N\{t_j\}_{j=1}^N{tj​}j=1N​, while minimizing the total number of device shots. We propose a Compressed Sensing Shadow Tomography (CSST) protocol that combines two complementary reductions. First, local classical shadows reduce the observable dimension by enabling many Pauli expectation values to be estimated from the same randomized snapshots at a fixed time. Second, compressed sensing reduces the time dimension by exploiting the fact that many expectation-value traces are spectrally sparse or compressible in a unitary (e.g., Fourier) transform basis. Operationally, CSST samples m≪Nm\ll Nm≪N timesteps uniformly at random, collects shadows only at those times, and then reconstructs each length-NNN signal via standard ℓ1\ell_1ℓ1​-based recovery in the unitary transform domain. We provide end-to-end guarantees that explicitly combine shadow estimation error with compressed sensing recovery bounds. For exactly sss-sparse signals in a unitary transform basis, we show that m=O(slog⁡2slog⁡N)m=O \left(s\log^2 s \log N\right)m=O(slog2slogN) random timesteps suffice (with high probability), leading to total-shot savings scaling as Θ~(N/s)\widetildeΘ(N/s)Θ(N/s) (i.e., up to polylogarithmic factors) relative to collecting shadows at all NNN timesteps. For approximately sparse signals, the reconstruction error decomposes into a compressibility (tail) term plus a noise term. We present numerical experiments on noisy many-qubit dynamics that support strong Fourier compressibility of Pauli traces and demonstrate substantial shot reductions with accurate reconstruction.
For the certification and benchmarking of medium-size quantum devices, efficient methods to characterize entanglement are needed. In this context, it has been shown that locally randomized measurements on a multiparticle quantum system can be used to obtain valuable information on the so-called moments of the partially transposed quantum state. This allows one to infer some separability properties of a state, but how to use the given information in an optimal and systematic manner has yet to be determined. We propose two general entanglement detection methods based on the moments of the partially transposed density matrix. The first method is based on the Hankel matrices and provides a family of entanglement criteria, of which the lowest order reduces to the known p_{3}-positive-partial-transpose criterion proposed in A. Elben et al. [Phys. Rev. Lett. 125, 200501 (2020)PRLTAO0031-900710.1103/PhysRevLett.125.200501]. The second method is optimal and gives necessary and sufficient conditions for entanglement based on some moments of the partially transposed density matrix.
Estimating global properties of many-body quantum systems such as entropy or bipartite entanglement is a notoriously difficult task, typically requiring a number of measurements or classical postprocessing resources growing exponentially in the system size. In this work, we address the problem of estimating global entropies and mixed-state entanglement via partial-transposed (PT) moments and show that efficient estimation strategies exist under the assumption that all the spatial correlation lengths are finite. Focusing on one-dimensional systems, we identify a set of approximate factorization conditions (AFCs) on the system density matrix, which allow us to reconstruct entropies and PT moments from information on local subsystems. This identification yields a simple and efficient strategy for entropy and entanglement estimation. Our method could be implemented in different ways, depending on how information on local subsystems is extracted. Focusing on randomized measurements providing a practical and common measurement scheme, we prove that our protocol requires only polynomially many measurements and postprocessing operations, assuming that the state to be measured satisfies the AFCs. We prove that the AFCs hold for finite-depth quantum-circuit states and translation-invariant matrix-product density operators and provide numerical evidence that they are satisfied in more general, physically interesting cases, including thermal states of local Hamiltonians. We argue that our method could be practically useful to detect bipartite mixed-state entanglement for large numbers of qubits available in today’s quantum platforms. Published by the American Physical Society 2024
Detecting multipartite entanglement in many qubit systems is measurement-intensive, motivating protocols that estimate only selected observables with provable efficiency. In this work we use the classical shadow protocol to study the sample complexity required to estimate a family of subsystem nnn-partite entanglement witness embedded in an larger NNN-qubit system. We derive ensemble dependent variance bounds that lead to qualitatively distinct scaling for the snapshots cost at fixed additive error εεε with numerical simulations confirm these trends, exhibiting a clear crossover from Pauli favorable performance for local witness to Clifford favorable performance as the witness becomes more global.