Dimension-Free Polylogarithmic Quantum Shadow Tomography

Dimension-Free Polylogarithmic Quantum Shadow Tomography addresses a fundamental problem in quantum information theory: estimating expectation values of multiple observables from multiple copies of an unknown quantum state. The paper proposes two distinct protocols for shadow tomography that achieve a dimension-independent sample complexity, achieving the bound of

O log(M) log(M/δ) ε squared, which is polylogarithmic in the number of observables (M) and independent of the Hilbert-space dimension (d). This result answers an open question posed by Aaronson regarding dimension-independent sample complexity and provides an exponential improvement over prior best bounds.

The Core Problem and Goal

Shadow tomography seeks to estimate all expectation values Tr(E iρ) for a list of known observables E1,..., EM, given multiple copies of an unknown state ρ. The goal is to achieve additive accuracy ε with probability at least 1 − δ. The paper formalizes this using a T-copy shadow-tomography strategy involving a POVM and a decoder. A key challenge addressed is whether the sample complexity can be independent of the dimension H, which has been an open question in prior work. The proposed protocols aim to provide this dimension-free guarantee while maintaining polylogarithmic dependence on M, the number of observables.

Sequential Pretty-Good Measurement (PGM)

The first protocol develops a sequential pretty-good measurement (PGM) that repeatedly applies the measurement and updates the prior distribution based on outcomes. This is detailed in Algorithm 1, which involves an iterative process over r rounds, where each round uses a posterior distribution derived from previous measurements. The key mechanism is the update rule:

In each round, we perform a PGM on a new group of copies, but replace the original prior distribution by the posterior distribution obtained from the previous measurement outcomes.

This sequential approach leads to a dimension-independent sample complexity of O log 3(M/δ) ε squared for finite ensembles. The analysis relies on techniques like signed-coordinate minimax, independent averaging, and geometric precision refinement to yield the main theorem bound.

Averaged Recovery Label Measurement

The second protocol utilizes an averaged recovery label measurement (Algorithm 2). This method involves a fixed budget N and involves measuring only a prefix of copies based on a randomly chosen time step t from 0 to N-1. The effect of this measurement is aggregated as Dy,t, and the final result is the integrated effect Dy. This route achieves a conditional mean bias bound of O qlog M/N using N copies simultaneously over all observables. The analysis involves complex powers and an integral over a probability density function β0(u) to define the recovery map.

Minimax Framework and Worst-Case Guarantee

The transition from finite-prior guarantees to worst-case shadow tomography is achieved via a minimax argument, utilizing Sion’s theorem for finite-dimensional forms. The proof roadmap involves:

1. Developing two measurement procedures: the sequential PGM and the recovery measurement.

2. Using minimax and continuity arguments to convert these finite-prior guarantees into worst-case shadow-tomography guarantees that hold uniformly over all input states ρ.

3. For the recovery-measurement route, this leads to a preliminary bound of O log M log(M/δ) ε 4, which is then refined by an iterative refinement scheme to yield the main bound of O log M log(M/δ) ε squared.

State-Uniformity via Trace-Distance Nets

To extend the finite ensemble results to all states in D(H), the paper employs a trace-distance net. This technique lifts the conclusion from a finite family of states to unrestricted all states by leveraging Lemma 5.3, which relates trace distance contraction under quantum channels to state fidelity bounds. By applying this net within the minimax framework (Lemma 5.1), the authors show that for every prior p, there exists a POVM N(p) such that the maximum failure probability over all states ρ in a finite set F is bounded by β. Theorem 5.4 then extends this to all states, concluding with Theorem 5.8, which establishes the final dimension-free sample complexity of T = O log 3(2M/δ) ε 2!.

Geometric Precision Refinement

The final improvement on the accuracy dependence from ε-4 to ε-2 is achieved through geometric precision refinement (Algorithm 3). This iterative process involves:

1. Defining a block observable Fj,s based on the current estimate cj,s.

2. Applying Corollary 5.7 to estimate the entire list of block observables simultaneously with a dimension-independent guarantee for each stage s.

Here are the specific improvements that can be made to AI systems based on the findings of this research, along with what those improved systems could achieve:

)1. Scalable Quantum State Estimation in Noisy or Open Systems:

The core contribution is a dimension-independent sample complexity bound for shadow tomography, specifically achieving an overall copy count of

T = O(ε −2 log(M) log(M/δ)) independent of the Hilbert space dimension (d).

• How it improves AI: Current quantum machine learning and state estimation often struggle with high dimensionality or require exponentially large resources to estimate expectation values of many observables. This result provides a theoretical guarantee that the number of required copies scales only with the complexity of the measurement list (M) and desired precision, not the intrinsic dimension of the quantum state space.

• What it can do: AI systems dealing with complex quantum data (e.g., in chemistry simulation or advanced quantum neural networks) could estimate thousands of different physical properties simultaneously with a manageable, polynomially growing number of copies, even if the underlying physical system is theoretically high-dimensional. This makes large-scale quantum characterization computationally feasible for near-term devices.

)2. Robust and Efficient Online/Sequential Inference:

The paper details two protocols: the sequential Pretty Good Measurement (PGM) and the averaged recovery measurement. The PGM updates its belief iteratively based on incoming data, while the recovery measurement uses a memory to perform an optimal estimation.

• How it improves AI: Many real-world AI tasks (like reinforcement learning in complex environments or continuous state tracking) are inherently sequential. The sequential PGM framework shows how to maintain high-accuracy estimates for unknown parameters as new data arrives, even when the underlying distribution changes.

• What it can do: An AI agent could operate in a real-time learning mode where it receives streaming sensor data (the history). Instead of re-running a full, expensive estimation protocol from scratch every time, the agent uses the sequential PGM to refine its internal model of the environment or its own hidden parameters with minimal new data acquisition, leading to faster adaptation and better long-term stability.

)3. Minimax Optimization for Adversarial Robustness:

The paper formalizes shadow tomography as a zero-sum game (minimax), allowing for the design of strategies that perform well against an adversary choosing the worst possible observables or state distributions.

• How it improves AI: This moves AI from merely optimizing performance under known conditions to robustly optimizing performance against unknown or adversarial inputs.

• What it can do: An AI model deployed in security-sensitive applications (e.g., quantum cryptography analysis) could be designed using the minimax framework to guarantee a minimum level of accuracy even if an attacker attempts to probe the system using non-ideal or strategically chosen measurement bases.

)4. Adaptive Precision Refinement:

The Geometric precision refinement section introduces an iterative process where measurements are strategically chosen based on current estimates to sequentially improve accuracy.

• How it improves AI: This suggests a dynamic, intelligent sampling strategy rather than a fixed one-shot measurement budget.

• What it can do: An AI system could implement an adaptive exploration strategy. If the current estimate is poor in a certain region of the parameter space, the system intelligently designs a new block observable (like those defined in Eq. 11) to gather targeted information precisely where it is needed most, leading to rapid convergence to high accuracy with minimal total resource expenditure.

)5. Universal State-Agnostic Estimation:

The final result (Theorem 5.8) proves a state-uniform shadow tomography strategy, meaning the required resources are independent of the specific unknown quantum state ρ in Hilbert space H.

• How it improves AI: This removes the curse of dimensionality barrier for estimation problems where the exact nature of the input data distribution is unknown or intractable to model perfectly.

• What it can do: It allows AI models to perform accurate inference on complex physical systems (like molecular Hamiltonians) without needing prior knowledge or explicit characterization of every possible state in that system's vast Hilbert space, making the estimation process universally applicable across different physical regimes.

Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown d-dimensional quantum state ρ and a known collection of observables E 1,,E M, the goal is to estimate all expectation values Tr(ρE i) i=1 M to additive accuracy epsilon with probability at least 1-δ. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on M, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O ((M) (M/δ) over epsilon squared), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.