Fermionic-Adapted Shadow Tomography for dynamical correlation functions

This paper introduces Fermionic-Adapted Shadow Tomography (FAST), a new framework that reformulates dynamical correlation functions to enable their efficient calculation on quantum devices using at most two-copy measurements, thereby significantly reducing the required sample complexity and number of measurement circuits compared to traditional brute-force strategies.

The Gist

The Big Picture: Listening to the Quantum Orchestra

Imagine a quantum system (like a complex molecule or a new material) as a massive, chaotic orchestra playing a piece of music. You want to understand how the orchestra reacts when you tap a specific instrument (a "perturbation").

In physics, this reaction is called a Dynamical Correlation Function. It tells you: "If I hit the violin at time $t=0$, how does the cello respond at time $t=1$?"

The Problem:
Currently, to hear this reaction, scientists use a "brute force" method. It's like trying to understand the orchestra by asking every single musician, one by one, "Did you hear the violin?" and "Did you hear the cello?"

• If there are 100 musicians, you have to ask 10,000 pairs of questions.
• If there are 1,000 musicians, you have to ask 1,000,000 questions.
• This takes forever and requires a massive amount of data (samples) to get a clear answer.

The Solution (FAST):
The authors of this paper introduce a new method called FAST (Fermionic-Adapted Shadow Tomography). Instead of asking every pair of musicians individually, they use a clever "shadow" technique to listen to the whole orchestra at once.

---

The Core Idea: The "Shadow" Analogy

Imagine you are in a dark room with a complex sculpture (the quantum system). You want to know its shape.

• The Old Way (Brute Force): You shine a flashlight on every single inch of the sculpture from every possible angle, one inch at a time. It takes a million photos to build a 3D model.
• The FAST Way (Shadow Tomography): You shine a single, smart light that casts a "shadow" of the whole sculpture onto a wall. By analyzing the shape of that shadow, you can mathematically reconstruct the 3D object with far fewer photos.

In quantum computing, a "Shadow" is a snapshot of the system's state. The paper shows how to take these snapshots in a way that captures the relationship between different parts of the system (the "correlations") without needing to measure them one by one.

How FAST Works: The Two Strategies

The paper splits the problem into two types of musical interactions: Commutator (things that happen in a specific order) and Anti-commutator (things that happen simultaneously or in a specific quantum "dance").

1. The Commutator Case: The "Group Photo" Strategy

• The Scenario: You want to know how the violin affects the cello after the cello has already moved.
• The Old Way: You take a photo of the violin, then a photo of the cello, then a photo of them together. Repeat this for every pair.
• The FAST Way: The authors realized that the math behind this reaction can be rewritten. Instead of taking 10,000 separate photos, they can take just three special "group photos" of the whole orchestra.
  • Photo A: The orchestra in a normal state.
  • Photo B: The orchestra with a "twist" (a specific quantum operation).
  • Photo C: The orchestra with a different "twist."
  • By combining these three photos mathematically, they can calculate the reaction for all pairs of musicians at once.
• The Result: If you have 100 musicians, you don't need 10,000 circuits; you only need a few dozen. This is a massive speedup.

2. The Anti-Commutator Case: The "Magic Coin Flip" Strategy

• The Scenario: This is for the "Green's Function," a fundamental tool in physics. It's trickier because the quantum rules here are like a coin flip where the outcome changes the rules of the game.
• The Challenge: You can't just "prepare" the state you need easily. It's like trying to bake a cake where the recipe changes depending on whether the oven light is on or off.
• The FAST Way:
  • Step 1: They use a "Bell Sampling" technique (like a magic coin flip) to see which musicians are actually "loud" (important) and which are "quiet" (negligible). They ignore the quiet ones.
  • Step 2 (The Chain Reaction): For the loud ones, they use a "Chained Measurement." Imagine a line of dominoes. If you knock over the first one, you can infer the state of the second, then the third, and so on.
  • Instead of measuring every domino individually, they measure the connection between them.
• The Result:
  • For small systems, they save time by reducing the number of circuits needed.
  • For large systems, they save a huge amount of data (samples) by focusing only on the "loud" musicians and using the domino chain trick.

Why This Matters: The "Efficiency" Boost

The paper proves that FAST is significantly better than the old methods in two ways:

1. Fewer Circuits: In the old method, if you double the size of the system, the work quadruples (or worse). With FAST, the work grows much slower. It's like going from driving a car that gets 1 mile per gallon to one that gets 100 miles per gallon.
2. Less Data Needed: To get a clear answer, the old method needed millions of "shots" (measurements). FAST needs thousands. This means experiments can be done faster and on smaller, less powerful quantum computers.

The "Real World" Test

The authors didn't just do the math; they simulated it on a computer using a model called the SSH Model (a toy model of a chain of atoms).

• The Result: As they made the system bigger (more atoms), the error in the old "Brute Force" method exploded. The error in the FAST method stayed low and manageable.
• The Takeaway: For small systems, both methods work. But for the large, complex systems we actually care about (like designing new drugs or superconductors), the old method breaks down, while FAST keeps working efficiently.

Summary in One Sentence

FAST is a new quantum recipe that lets scientists listen to the entire quantum orchestra at once by taking a few clever "shadow" snapshots, rather than asking every musician individually, saving massive amounts of time and computing power.

Technical Summary

1. Problem Statement

Dynamical correlation functions are fundamental for characterizing the response of quantum many-body systems to external perturbations and are essential for understanding experimental outcomes in condensed matter physics and quantum chemistry.

• Computational Challenge: Calculating these functions classically is generally intractable for large systems.
• Limitations of Current Quantum Methods: Existing quantum algorithms typically rely on "brute-force" measurement strategies. These methods evaluate one pair of one-body observables per circuit. Consequently, the number of required measurement circuits and the total sample complexity scale poorly with system size $n$ (e.g., $O(n^2)$ to $O(n^4)$), making the estimation of multiple correlation functions (like Green's functions or density-density responses) inefficient.
• Goal: The authors aim to develop a framework that simultaneously estimates multiple dynamical correlation functions with significantly improved sample efficiency and reduced circuit counts, specifically tailored for fermionic systems.

2. Methodology: Fermionic-Adapted Shadow Tomography (FAST)

The core innovation is the Fermionic-Adapted Shadow Tomography (FAST) protocol. The methodology involves reformulating correlation functions into forms compatible with shadow tomography techniques, avoiding the need for controlled time evolution (which is costly) in many cases.

A. Reformulation of Correlation Functions

The authors decompose the target correlation functions into direct measurement forms:

• Commutator Case: $C(A, B, t) = \text{tr}(\rho[A(t), B])$.
  • The authors derive an identity (Eq. 9) that expresses the commutator as a linear combination of three expectation values involving states evolved by $e^{-iHt}$ and Pauli rotations $e^{\pm i \frac{\pi}{4} B}$. This allows estimation using standard shadow tomography without controlled gates.
• Anti-commutator Case: $C(A, B, t) = \text{tr}(\rho\{A(t), B\})$.
  • Since the required projection operators $(I \pm B)/2$ are non-unitary, the authors introduce a probabilistic measurement strategy. By using an ancilla qubit and controlled Pauli gates, they prepare states $\rho_+$ or $\rho_-$ probabilistically.
  • A majority rule is applied: based on ancilla measurement statistics, the protocol selects the appropriate representation (Eq. 12 or 13) to estimate the correlation function.

B. Regime-Dependent Protocols

The efficiency of FAST depends on the relationship between system size $n$ and precision $\epsilon$. The authors distinguish two regimes:

1. Small System / High Precision Regime ($n \leq 1/\epsilon^2$):
   • Strategy: Utilizes Classical Shadows combined with Dynamic Circuits.
   • Mappings: Optimized for Jordan-Wigner (JW), Bravyi-Kitaev (BK), and Ternary Tree (TT) mappings.
   • Key Technique: For TT mapping, the locality of Pauli strings is reduced ($\log_3(2n)$), allowing the use of random Pauli measurements with dynamic circuits to estimate 1-body observables using a single circuit structure.
2. Large System / Low Precision Regime ($n \geq 1/\epsilon^2$):
   • Strategy: Utilizes Bell Sampling and Chained Measurement Strategies.
   • Technique:
     • Bell Sampling: Used to threshold and discard observables with negligible expectation values (reducing the number of active observables to $O(1/\epsilon^2)$).
     • Chained Measurement (JW specific): For the JW mapping, the authors propose a novel "chained" strategy. Instead of measuring independent observables, they measure products of adjacent Pauli strings ($P_i \otimes P_{i+1}$) which mutually commute. This allows inferring the signs of all remaining observables from a single initial measurement, drastically reducing circuit counts.

3. Key Contributions

• New Framework (FAST): Introduced a unified framework for estimating both commutator and anti-commutator dynamical correlation functions using shadow tomography.
• Identity Derivations: Derived specific algebraic identities (Eqs. 9, 12, 13) that map fermionic correlation functions to forms suitable for shadow tomography without controlled time evolution.
• Regime-Specific Optimization:
  • Commutator Case: Achieves a reduction in sample complexity and circuit count by one to two orders of magnitude compared to brute force.
    • For $n \leq 1/\epsilon^2$ (TT mapping): Reduces circuit count from $O(n^2)$ to $O(n)$.
    • For $n \geq 1/\epsilon^2$: Reduces sample complexity to $O(n^2 \log n / \epsilon^4)$ and circuit count to $O(n^2/\epsilon^2)$.
  • Anti-commutator Case (Green's Functions):
    • For $n \leq 1/\epsilon^2$: Reduces circuit count by an order of magnitude (using TT mapping).
    • For $n \geq 1/\epsilon^2$: Introduces a novel two-copy measurement strategy for JW mapping that reduces the circuit count by a factor of $1/\epsilon^2$ compared to previous shadow methods, requiring only $O(1)$ circuits.
• Dynamic Circuit Integration: Demonstrated how dynamic circuits (mid-circuit measurement and feedback) can be integrated to perform random Pauli measurements with $O(1)$ circuit depth and count.

4. Results

• Complexity Analysis:
  • Green's Function (Commutator): The proposed method reduces the number of circuits from $O(n^2)$ (brute force) to $O(n)$ (TT mapping) or $O(n^2)$ (JW/BK) in the small system regime. In the large system regime, it improves sample complexity from $O(n^2)$ to $O(n^2/\epsilon^2)$ while maintaining low circuit counts.
  • Density-Density Response: Reduces sample complexity from $O(n^4)$ (brute force) to $O(n^3)$ or $O(n^2)$ depending on the mapping and regime.
• Numerical Simulations:
  • Simulations on the Su-Schrieffer-Heeger (SSH) model validated the theoretical scaling.
  • Error Scaling: The error for the FAST protocol scales as $O(\sqrt{n} \log n)$, whereas brute-force methods scale as $O(n \sqrt{\log n})$.
  • Performance: For a fixed total shot budget, FAST significantly outperforms brute-force methods as system size increases, demonstrating superior variance reduction.
• Resource Efficiency: The protocols generally require fewer ancilla qubits (0 to 2) and avoid controlled Pauli operations, which are error-prone on near-term hardware.

5. Significance

• Scalability: FAST addresses the "measurement bottleneck" in quantum simulation, enabling the efficient calculation of extensive sets of correlation functions (e.g., full Green's function matrices) that were previously too costly to compute.
• Hardware Compatibility: By minimizing the need for controlled time evolution and leveraging dynamic circuits, the protocols are well-suited for future fault-tolerant quantum computers and potentially advanced NISQ devices.
• Broad Applicability: The framework is applicable to various fermion-to-qubit mappings (JW, BK, TT) and can be extended to two-particle correlation functions and momentum-space Green's functions.
• Theoretical Advancement: The work bridges the gap between shadow tomography theory and specific fermionic many-body problems, providing a concrete path toward practical quantum advantage in materials science and quantum chemistry.

In summary, the paper presents a robust, mathematically rigorous, and practically viable protocol (FAST) that significantly lowers the resource overhead for computing dynamical correlation functions, marking a substantial step forward in the quantum simulation of fermionic systems.