Predicting properties of Scrooge ensembles with high accuracy and low sample complexity

Technical Summary: Predicting Properties of Scrooge Ensembles with High Accuracy and Low Sample Complexity

Problem Statement
The Scrooge ensemble associated with a density matrix $\rho$ is defined as the maximally random ensemble of pure states whose average density matrix is $\rho$. These ensembles are critical for understanding quantum many-body dynamics, deep thermalization, and quantum information processing tasks such as shadow tomography and simulator benchmarking. However, analyzing and preparing these ensembles is computationally challenging.

The intrinsic statistical properties of Scrooge ensembles are encoded in their higher-order moments, $\chi^{(k)}_{Sc}(\rho)$. Unlike Haar-random moments, which possess a clean analytical formulation, Scrooge moments involve a non-polynomial integrand containing a denominator term $\langle \psi | \rho | \psi \rangle^{k-1}$. This structure blocks the direct application of standard Haar integration machinery. Furthermore, existing physical mechanisms to sample from Scrooge ensembles—either via projected ensembles (measuring parts of entangled states) or temporal ensembles (time evolution)—are inefficient. Projected ensembles typically require costly postselection (with success probabilities scaling as $1/k!$), while temporal ensembles may require evolution over timescales inversely proportional to the minimum energy gap, rendering them impractical for large systems.

Methodology
The authors propose a two-pronged approach to overcome these barriers: a high-accuracy polynomial approximation of the moment operator and an efficient quantum algorithm for its implementation.

1. Polynomial Approximation of Scrooge Moments:
   The core difficulty lies in the denominator of the Scrooge moment definition:
   $$\chi^{(k)}_{Sc}(\rho) = \mathbb{E}_{\psi \sim \text{Haar}} \left[ \frac{D (\sqrt{\rho} |\psi\rangle\langle\psi| \sqrt{\rho})^{\otimes k}}{\langle \psi | \rho | \psi \rangle^{k-1}} \right]$$
   The authors observe that for Haar-random states, the quantity $r_\phi = D \langle \phi | \rho | \phi \rangle$ concentrates around 1 when $\rho$ has sufficiently low purity (i.e., small $\|\rho\|_\infty$). They replace the singular term $1/r_\phi^{k-1}$ with a tunable polynomial approximation $g_\lambda(x)$ derived from a truncated Taylor series expansion of $1/x$ around $x=1$.
   $$g_\lambda(x) = \sum_{j=0}^{\lambda-1} (1-x)^j$$
   This transforms the Scrooge moment into a linear combination of standard Haar moments, which are analytically tractable. The approximation error is shown to be tunable; by increasing the expansion order $\lambda$, the error can be reduced to be exponentially small in $1/\|\rho\|_\infty$, a significant improvement over previous results where error scaled polynomially.

2. Efficient Symmetric Subspace Projection:
   To implement the approximation on a quantum computer, the authors must prepare states of the form $\rho^{(k)}_{\text{sym}} = \rho^{\otimes k} \Pi^{(k)}_{\text{sym}} / p_{\text{sym}}$, where $\Pi^{(k)}_{\text{sym}}$ is the projector onto the $k$-fold symmetric subspace. Standard postselection is inefficient ($O(k!)$ cost).
   Instead, the authors utilize Schur-Weyl duality. They apply the Schur transform to $\rho^{\otimes m}$ (where $m \ge k$) to decompose the state into irreducible representation sectors labeled by Young diagrams $\gamma$. Within each sector, the state of the permutation register is known. The algorithm conditionally replaces the permutation register with the specific symmetric state required for that sector, effectively projecting onto the symmetric subspace without postselection. This procedure requires $O(k^3/\epsilon^2)$ samples of $\rho$.

3. Quantum Algorithm for Expectation Values:
   Combining the polynomial approximation and the efficient projection, the authors construct a quantum algorithm to estimate $\text{Tr}[\chi^{(k)}_{Sc}(\rho) O_k]$ for any observable $O_k$. The algorithm estimates the product of the normalization factor and the expectation value for each term in the polynomial expansion using a median-of-means estimator to ensure robustness.

Key Contributions and Results

• High-Accuracy Approximation: The paper introduces a polynomial approximation for Scrooge $k$-th moments that achieves an error scaling exponentially small in $1/\|\rho\|_\infty$. This extends the regime of valid states for accurate approximation beyond the highly mixed states required by previous methods.
• Efficient Quantum Algorithm: The authors present the first efficient quantum algorithm to estimate Scrooge moment expectation values. For a target error $\epsilon$ above the approximation threshold, the algorithm requires $\tilde{O}(k^3/\epsilon^5)$ copies of $\rho$.
• Postselection-Free Projection: A key subroutine is an efficient method to project $\rho^{\otimes k}$ onto the symmetric subspace using $O(k^3/\epsilon^2)$ samples, avoiding the prohibitive $k!$ cost of standard postselection.
• Block Encoding Construction: When a preparation circuit for a purification of $\rho$ is available, the authors construct a block encoding of the Scrooge $k$-th moment. This integrates Scrooge moments into the standard block-encoding framework, enabling their use in advanced quantum algorithms like Quantum Singular Value Transformation (QSVT).
• Numerical Validation: Numerical simulations on Gibbs states of the transverse-field Ising chain confirm that the approximation errors decrease rapidly with expansion order $\lambda$ and are often significantly smaller than the theoretical upper bounds.

Significance and Claims
The paper claims to provide the first efficient, high-accuracy tools for both the theoretical analysis and practical prediction of Scrooge ensemble properties. By replacing the non-polynomial integrand with a tunable polynomial and leveraging Schur-Weyl duality to bypass postselection, the work enables the study of deeply thermalized ensembles using only copies of the associated density matrices, which are often easier to prepare than the ensembles themselves.

The authors suggest potential applications in:

• Refining the characterization of information-theoretic quantities in many-body systems.
• Improving benchmarking protocols for quantum simulators.
• Potentially enhancing shadow tomography protocols by utilizing Scrooge moments for reweighting, though they note that concrete implementations and complexity guarantees for this specific application remain to be established.

The paper remains modest regarding high-purity states, acknowledging that the current approximation guarantees weaken as $\|\rho\|_\infty$ increases, and identifies the extension to arbitrary density matrices as an open question for future work.