Practical fermionic shadows enabled by improved sample-complexity bounds

Classical shadow tomography can be significantly improved for fermionic (matchgate) shadows, reducing the required sample-complexity bound from an order of O(n 2kO 2∞) to an asymptotically tight O(n kO 2∞). This improvement is crucial for making shadow tomography practical on large quantum computers with hundreds of qubits by substantially decreasing the number of required shots for estimating observables.

The gist

The research derives an asymptotically optimal upper bound on the variance of estimators obtained by matchgate shadows for observables fully supported on a homogeneous subspace, finding that Var[ˆo] ⩽ 3/2an,kO 2∞. This result reduces the experimental cost by a factor of roughly 104 compared to previous bounds for certain physical systems like the Hubbard model.

Theoretical Framework and Notation

The work establishes notation for an n-mode system using Majorana operators and defines the Majorana monomial as ΓS, which is central to understanding observables. The study focuses on the group of fermionic Gaussian unitaries, known as the matchgate group MG(n), whose elements are generated by quadratic combinations of Majoranas. This group acts on the Hilbert space H in a way that decomposes it into subspaces Lk, where Lk is the homogeneous sector of order k.

The Shadow Protocol and Variance Bound

The classical shadow protocol involves evolving copies of an unknown state under unitaries sampled from a set E and measuring the resulting state. The variance of the estimator is bounded by the shadow norm O 2sh, which itself bounds Var[ˆo] for every state ρ. The main result, Theorem 1, provides a bound for observables O in L2k: Var[ˆo] ⩽ 3/2an,kO 2∞. This bound is shown to be asymptotically optimal up to a factor of 3/2.

Proof Strategy and Key Derivations

The proof relies on exploiting the fact that Clifford matchgates form a matchgate 3-design, allowing the replacement of Haar random matchgates with finite averages over Clifford matchgates. The core derivation involves expanding the observable O into its degree-4r components (Eq. 18) and relating these to a function w: [2n] → R that satisfies specific conditions derived from Krawtchouk polynomials. Through technical lemmas, the authors construct an ansatz for w that ensures both P j: w j > 0 and P j: w j ≤ 3/2, leading directly to the final bound.

Application to Physical Models

The results are applied to estimate the energy of states in the spin-1/2 Hubbard model. The Hamiltonian is decomposed into H = H2 + H4, where H2 resides in L2 and has a variance bound related to h2∞, and H4 resides in L4 with h4∞ = V/8. For specific parameters of the Hubbard chain (e.g., n=100, L=50), the derived bound improves upon previous bounds by a factor of roughly 104 for the target additive precision ε = 0.1, demonstrating substantial experimental savings in regimes relevant to quantum chemistry simulations.

Experimental Feasibility and Future Directions

While the sample-complexity bound is improved, experimental implementation faces challenges related to circuit depth required to implement matchgate 3-designs. The paper notes that on one-dimensional nearest-neighbour architectures, sublinear-depth ensembles of matchgates cannot form matchgate 3-designs. However, the authors suggest that on all-to-all connected architectures, optimal logarithmic depth designs can be formed from ensembles intersecting the matchgate and Clifford groups, which may be achievable in systems like trapped ions or neutral atom processors. The paper also suggests that a simpler proof might remove the factor of 3/2 present in current bounds.

Corollary Generalization

The results are generalized to observables O = P k sum O 2k, where O 2k ∈ L2k for all k. Corollary 1 states that Var(ˆo) ≤ 3/2 X K sum O 2k∞ √an,K! squared if K ≤ n/2, and a related bound holds if K > n/2. This shows how the variance scales with the degree of homogeneity of the observable. The analysis also provides bounds for observables that are products of single Majorana strings (Corollary 1).

Appendix Details

Appendix A details the combinatorics, showing that joint survival probabilities pj depend on S∩T = 2j, and Appendix B provides the detailed proof sketch for Theorem 1, including the construction of the function w using Krawtchouk transform properties. Appendix C supplies the proof for Lemma 1, which is critical for controlling the mass of w.

Based on the provided scientific paper, here are the specific improvements that can be made to AI systems, along with what those improved systems could achieve:

)1. Improve Sample-Complexity for Quantum State Estimation in NISQ Regimes: The primary improvement is a theoretical reduction in the sample complexity required for classical shadow tomography of fermionic observables from the previously known upper bound of

O(n 2k∥O∥2∞) to the asymptotically tight bound of O(n k∥O∥2∞).

• The improved AI system (a quantum state estimator utilizing these shadows) can estimate expectation values of complex, high-degree fermionic observables with significantly fewer required measurements (shots).

• For a specific example, the paper demonstrates that for an open fermionic 50-site Hubbard chain with given parameters and a target additive precision of 0.1, the number of required shots is reduced by approximately 99.98% (from 10 9 to 10 5).

• This means AI systems designed for quantum chemistry or condensed matter simulations on near-term quantum hardware (NISQ) can achieve higher accuracy estimations much faster and with less computational cost, making complex molecular simulations practically feasible on current or near-future devices.

2. Enhance Robustness of Quantum Machine Learning Algorithms: The results provide tighter bounds for the variance of estimators derived from matchgate shadows, moving beyond loose general bounds to a result that scales optimally with the observable's structure.

• The improved AI system can perform more reliable learning tasks on quantum states by minimizing estimation error variance.

• Specifically, when estimating observables composed of multiple components (Corollary 1), the variance bound is refined to depend on the individual norms of those components (e.g., Var[ˆo] ⩽ 3/2 X K k=1 O 2k∞ √an,k!2).

• This leads to more stable and less noisy quantum machine learning models that are crucial for tasks like variational quantum eigensolver (VQE) optimization or quantum kernel methods.

3. Enable Practical Implementation on Near-Term Hardware: The theoretical work provides a roadmap for implementing useful fermionic shadow tomography on near-term hardware by showing that optimal sample complexities can be achieved even with specific constraints on circuit depth.

• The improved AI system can be designed to leverage the structure of matchgate 3-designs (which are achievable in logarithmic depth on all-to-all connected architectures).

• This allows for the development of experimental protocols that are both theoretically optimal (in terms of sample complexity) and experimentally feasible on hardware like trapped ions or neutral atom processors, dramatically increasing the prospects for real quantum simulation experiments.

4. Optimize Quantum Simulation for Many-Body Systems: The application to the Hubbard model shows a massive practical speedup in estimating crucial physical quantities like energy per mode.

• AI systems performing quantum simulations of correlated electron dynamics (like the Hubbard model) can estimate ground state energies with high precision using classical shadows, achieving improvements of roughly a factor of 10 4 over previous bounds.

• This capability allows for more accurate characterization of material properties and electronic structure in complex many-body systems, which is a cornerstone of materials science and quantum computing applications.

Classical shadow tomography is widely touted as supplying a family of methods for extracting information from quantum systems with polynomially scaling sample-complexities. In the current era of quantum computers possessing on the order of hundreds of qubits, however, polynomial scaling can nonetheless be prohibitive. Thus, there is a strong practical need for obtaining sample-complexity bounds which are as tight as possible. Here we address this in the case of fermionic (matchgate) shadows. For an arbitrary observable O of Majorana degree 2k, we improve the previously known sample-complexity bound of O(n 2k|O| infinity 2) to O(n k|O| infinity 2), which is asymptotically tight. For example, for the estimation of the energy per mode of an open fermionic 50-site Hubbard chain with hopping and on site strenghts respectively given by t=1, V=4, and for a target additive precision of 0.1, this reduces the number of required shots from about 10 9 to about 10 5. That is, the new bound reduces the required number of shots by approximately 99.98%.