Post-processing optimization and optimal bounds for non-adaptive shadow tomography

Technical Summary: Post-processing Optimization and Optimal Bounds for Non-adaptive Shadow Tomography

Problem Statement
Quantum state tomography faces prohibitive resource requirements, leading to the development of shadow tomography and classical shadows, which follow a "measure first, ask questions later" paradigm. While recent adaptations have focused on optimizing the "measure first" aspect (quantum operations), the "ask questions later" phase (classical post-processing) has received less systematic attention.

In linear tomography using informationally overcomplete Positive Operator-Valued Measures (POVMs), the mapping from observed frequencies to an estimator is not unique. Specifically, for a fixed POVM $\{E_j\}$ and a target observable $O$, there exist infinitely many unbiased linear reconstructions (sets of coefficients $\vec{x}$) satisfying $O = \sum_j x_j E_j$. Standard protocols typically employ a "canonical" choice of reconstruction coefficients, which is target-agnostic. However, this canonical choice is generally suboptimal for specific targets, leading to unnecessarily high estimator variance and, consequently, increased sampling complexity. The central problem addressed is how to systematically exploit the "gauge freedom" in post-processing to minimize the worst-case variance of the estimator without altering the underlying experimental measurement scheme.

Methodology
The authors formulate the selection of optimal reconstruction coefficients as a convex minimax optimization problem. The goal is to find a set of coefficients $\vec{x}$ that minimizes the maximum variance of the estimator $\hat{o}$ over all possible quantum states $\rho$.

1. Formulation: The problem is defined as:
   $$\min_{\vec{x} \in \mathcal{B}} \max_{\rho \in \mathcal{R}} f(\vec{x}, \rho) = \text{Var}[\hat{o} | \vec{x}, \rho]$$
   subject to the constraint $\sum_j x_j E_j = O$, where $\mathcal{B}$ is a bounded set of coefficients and $\mathcal{R}$ is the set of valid density matrices.
2. Convexity and Convergence: The authors demonstrate that for a fixed state, the variance is convex in $\vec{x}$, and for fixed coefficients, it is concave in $\rho$. Given the compact and convex nature of the set of density matrices, the minimax theorem applies. This guarantees the existence of a global saddle point and allows the inversion of the min/max operations, facilitating an efficient numerical solution.
3. Algorithm: The proposed algorithm iteratively solves for the optimal coefficients $\vec{x}^*(\rho)$ for a given state (which admits an analytical solution involving the inverse of a POVM coefficient matrix) and then maximizes the resulting variance function over the state space. This approach yields a tight, state-independent upper bound on the variance achievable by classical post-processing.

Key Results
The paper presents numerical examples demonstrating that variance-optimal post-processing can significantly outperform standard canonical reconstructions:

• Product Observables: For a restricted POVM (Pauli $X$ and $Z$ projectors) and tensor product target observables, the optimal coefficients do not necessarily follow the product structure of the canonical solution.
  • For specific target angles (e.g., projectors on the $Z$ eigenstate), the optimal variance exhibits sub-linear scaling with the number of qubits.
  • This contrasts sharply with the canonical estimator, which exhibits exponential scaling in the same regime.
  • The optimal solution is "entangled" in the sense that the global coefficients cannot be decomposed into a simple product of local coefficients, even though both the measurement and target are local.
• Sum of Local Observables: For the estimation of the sum of local Pauli observables on a spin chain (e.g., external magnetic field estimation), the optimal global coefficients again deviate from the linear composition of local canonical coefficients.
  • The sampling complexity scaling for the optimal estimator appears sub-exponential (suggesting quadratic scaling in some regimes), whereas the canonical estimator maintains a constant upper bound that implies a different, less favorable scaling behavior for certain parameters.

Significance and Claims
The paper claims that the sampling overhead often attributed to non-adaptive shadow tomography is not a fundamental limitation of the measurement scheme itself but often a consequence of suboptimal reconstruction.

• Operational Freedom: The work operationalizes the "freedom" in post-processing, showing that one can determine the ideal estimator construction after data acquisition without modifying the experiment.
• Tight Bounds: The proposed method provides the tightest state-independent variance bound achievable for a fixed POVM and observable, refining the standard "shadow norm" guarantees.
• Scaling Improvements: Crucially, the authors demonstrate that optimal post-processing can alter the qualitative scaling of sampling complexity with system size (e.g., moving from exponential to sub-exponential/sub-linear), not just improve constant prefactors.
• Task-Adaptive Design: The approach establishes a task-adaptive design problem where the estimator is optimized specifically for the target observable, moving the paradigm from "measure first, ask later" to "measure first, process later, but optimally."

The authors conclude that while the current algorithm relies on numerical optimization, the framework opens the door to understanding the structure of worst-case states and developing scalable, constrained variants of the optimization for broader applications, such as nonlinear properties or robust estimation under experimental noise.