Sketch Tomography: Hybridizing Classical Shadow and Matrix Product State

This paper introduces Sketch Tomography, a provably convergent quantum state tomography method that hybridizes classical shadow protocols with matrix product state assumptions to achieve quadratic sample complexity and superior accuracy in observable estimation compared to standard classical shadows and maximum likelihood estimation.

The Gist

Imagine you have a massive, intricate 3D puzzle that represents the state of a quantum computer. This puzzle is so complex that trying to look at every single piece individually to understand the whole picture would take forever and require an impossible amount of data. This is the problem of Quantum State Tomography: trying to figure out exactly what a quantum system looks like just by peeking at it.

The paper "Sketch Tomography" introduces a clever new way to solve this puzzle by combining two existing tools: Classical Shadows and Matrix Product States (MPS).

Here is how the authors' method works, using simple analogies:

1. The Problem: The "Shadow" is Too Fuzzy

First, there is a standard method called Classical Shadow. Imagine you are trying to recognize a friend in a dark room by taking a quick, blurry snapshot (a "shadow") of them.

• The Good News: You only need a few snapshots to get a general idea of who they are.
• The Bad News: If you want to know specific details about their entire outfit (especially if the outfit is a long, connected chain of items), the blurry snapshot is too noisy. The "shadow" might tell you the color of their shirt, but if you try to guess the pattern on a long scarf they are wearing, the guess might be wildly wrong because the noise adds up.

2. The Clue: The "Chain" Structure

The authors assume the quantum state they are studying isn't just random chaos; it has a specific structure called a Matrix Product State (MPS).

• The Analogy: Think of the quantum state not as a giant, tangled ball of yarn, but as a necklace. The beads (qubits) are connected in a line. The state of one bead is heavily influenced by its immediate neighbors, but not by beads far away on the other side of the room.
• Because of this "necklace" structure, the math describing the system can be broken down into a series of small, manageable links (called Tensor Trains).

3. The Solution: "Sketching" the Necklace

The new method, Sketch Tomography, acts like a smart detective who uses the blurry snapshots (Classical Shadows) to reconstruct the necklace, link by link, rather than trying to guess the whole thing at once.

Here is the step-by-step process:

• Step 1: Get the Blurry Photos.
  The team takes many "Classical Shadow" measurements. These are like taking many quick, noisy photos of the quantum system.
• Step 2: Break it Down.
  Instead of trying to solve the whole puzzle at once, they break the "necklace" into small segments. They ask: "What does the link between bead 1 and bead 2 look like? What about bead 2 and bead 3?"
• Step 3: The "Sketch" (The Magic Trick).
  This is the core innovation. To figure out what a specific link looks like, they don't need to see the whole necklace. They use a mathematical trick called sketching.
  • Imagine: You want to know the shape of a specific knot in a long rope. Instead of holding the whole rope, you take a "sketch" (a simplified measurement) of just the left side of the knot and a "sketch" of the right side.
  • By combining these sketches with the blurry photos from Step 1, they can solve a set of simple equations to figure out the exact shape of that specific link.
• Step 4: Reassemble.
  Once they have figured out every single link (tensor component) in the chain, they snap them back together. The result is a clean, high-definition reconstruction of the entire quantum state.

Why is this better?

The paper claims this method is superior for two main reasons:

1. It's Smarter with Global Details: If you want to know about a property that involves the entire necklace (a "global observable"), the standard "blurry photo" method gets very noisy and inaccurate. The "Sketch Tomography" method, because it rebuilds the structure piece-by-piece, stays accurate even for these big-picture questions.
2. It's Efficient: The math proves that the number of measurements needed to get a good answer grows only quadratically with the size of the system. This means even for large quantum computers, you don't need an infinite amount of data to get a good picture.

The Results

The authors tested this on simulated quantum systems (like magnetic chains of atoms). They found that:

• Their method was just as good as the standard method for simple, local questions.
• For complex, global questions, their method was significantly more accurate than the standard "Classical Shadow" method.
• It was also more accurate than other popular methods that try to "train" a model to guess the state (Maximum Likelihood Estimation).

Summary

Think of Classical Shadow as taking a quick, blurry photo of a long train. It's fast, but hard to read the text on the last car.
Sketch Tomography is like taking that same blurry photo but using a special blueprint (the "necklace" structure) to mathematically "sketch" and reconstruct the train car by car. The result is a clear, accurate picture of the whole train, built efficiently from limited data.

Technical Summary

Technical Summary: Sketch Tomography

Problem Statement

Quantum state tomography (QST) is essential for verifying quantum devices but faces scalability challenges due to the exponential growth of the Hilbert space. While the classical shadow protocol offers an efficient method for estimating quantum observables with limited measurements, it can suffer from high variance when estimating global observables or when the number of copies is insufficient for high-precision reconstruction.

This work addresses the specific scenario where the ground truth quantum state $|\psi\rangle$ is known to admit a Matrix Product State (MPS) representation. The goal is to reconstruct the density matrix $\rho = |\psi\rangle\langle\psi|$ accurately, leveraging the low-entanglement structure of MPS to improve upon standard classical shadow estimation, particularly for global observables and entanglement entropy prediction.

Methodology: Sketch Tomography

The authors propose Sketch Tomography, a post-processing procedure that converts a classical shadow approximation $\hat{\rho}$ into a Tensor Train (TT) approximation $\tilde{\rho}$. The method operates under the assumption that the coefficient tensor of $\rho$ in the Pauli basis is a Tensor Train.

The procedure involves the following steps:

1. Input: A collection of classical shadow approximations $\{\hat{\rho}_1, \dots, \hat{\rho}_W\}$ obtained via random Pauli measurements.
2. Tensor Representation: The density matrix $\rho$ is represented as a contraction of Pauli matrices with a coefficient tensor $C$. Under the MPS assumption, $C$ decomposes into a sequence of tensor components $(G_k)_{k=1}^n$.
3. Linear System Formulation: The recovery of each tensor component $G_k$ is formulated as a linear equation involving the "left" and "right" parts of the tensor network ($C_{<k}$ and $C_{>k}$).
4. Sketching: To make the linear system tractable for large $n$, the authors introduce "sketch tensors" ($S_{<k}, S_{>k}$) that contract the over-determined system into a smaller, solvable linear system. These sketches correspond to specific local observables.
5. Estimation via Classical Shadow:
   • The terms in the sketched linear system (specifically $B_k$, $Z_k$) are estimated using the classical shadow protocol.
   • $B_k$ is estimated directly as an observable expectation value.
   • $Z_k$ (a contraction of the full tensor) is estimated and then subjected to a truncated Singular Value Decomposition (SVD) to determine the gauge and the tensor components $A_{<k}$ and $A_{>k}$.
6. Reconstruction: Solving the sketched linear equations yields the estimated tensor components $\hat{G}_k$, which are assembled to form the final density matrix approximation $\tilde{\rho}$.

Key Contributions

• Hybrid Protocol: The paper introduces a hybrid approach that combines the sample efficiency of classical shadows with the structural constraints of Tensor Networks (specifically MPS/TT).
• Convergence Guarantee: The authors provide a non-asymptotic convergence bound (Proposition 1). They prove that the Frobenius norm error $\|\rho - \tilde{\rho}\|_F$ scales quadratically with the system size $n$ and inversely with the number of measurements $B$. Specifically, $B \ge O(n^2 \log(n/\delta)\epsilon^{-2})$ measurements suffice to achieve error $\epsilon$ with probability $1-\delta$.
• Information-Theoretic Lower Bound: The paper establishes a lower bound (Proposition 2) showing that estimating an MPS state to error $\epsilon$ requires at least $O(n/\epsilon^2)$ measurements, suggesting the quadratic dependence on $n$ in the upper bound is close to optimal, though a gap remains.
• Improved Global Observable Estimation: The method demonstrates that $\tilde{\rho}$ provides more accurate estimates for global observables compared to the raw classical shadow estimator $\hat{\rho}$, which suffers from large variance in such tasks.

Numerical Results

The authors conducted experiments on three models: 1D Heisenberg, 1D Transverse Field Ising Model (TFIM), and 2D Heisenberg.

• Local Observables: Sketch tomography achieves accuracy comparable to the standard classical shadow protocol for local two-point correlation functions.
• Global Observables: For $k$-local observables with large $k$ (global observables), Sketch Tomography significantly outperforms both the classical shadow protocol (using median-of-means) and Maximum Likelihood Estimation (MLE) trained MPS models.
• Entanglement Entropy: The method accurately predicts Renyi entanglement entropy for subsystems. In the 1D Heisenberg model, the mean prediction error was 0.002, outperforming the MLE benchmark (0.004).
• Scalability: In the 2D Heisenberg model ($n=64$), the method successfully reconstructed the state despite the high bond dimension of the true state ($a=200$), using a computational bond dimension of $r_{max}=50$ for efficiency. The mean prediction error for two-point functions was comparable to classical shadow (0.018 vs 0.013).
• MLE Comparison: The authors note that while MLE can fit the likelihood of the data, it does not necessarily guarantee accurate observable prediction, especially when sample sizes are limited or the model is prone to overfitting. Sketch tomography offers a more robust alternative in these regimes.

Significance and Claims

The paper claims that Sketch Tomography is a provably convergent, efficient procedure for quantum state tomography when the target state is an MPS. Its primary significance lies in:

1. Accuracy: It provides a more accurate approximation of the density matrix in the Frobenius norm than standard classical shadows, leading to superior performance in estimating global observables.
2. Efficiency: It avoids the computational complexity of training variational models (like MLE) by using a direct, non-iterative post-processing of classical shadow data.
3. Theoretical Foundation: It bridges the gap between classical shadow protocols and tensor network methods, offering rigorous error bounds that scale polynomially with system size.

The authors conclude that while the method is currently tailored to MPS, the framework could potentially be extended to other tensor network structures, such as hierarchical Tucker networks. They explicitly state that the quadratic dependence on $n$ in their sample complexity bound is a result of their current analysis and conjecture that using the output as a warm start for tensor network training could improve this scaling.