Practical fermionic shadows enabled by improved sample-complexity bounds
Abstract
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 𝒪(n2k|O|∞2) to 𝒪(nk|O|∞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 ∼ 109 to ∼ 105. That is, the new bound reduces the required number of shots by approximately 99.98%.
Related
- Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States
- Verification Complexity and Extension of Classical Shadows
- Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
- Fermionic Gaussianity can be tested with mode-independent sample-complexity
- Quantum Complexity and Stabilizer-State Expansions: From Pairing to Deformation in Fermionic Systems
BibTeX
@misc{west2026practical,
title = {{Practical fermionic shadows enabled by improved sample-complexity bounds}},
author = {Maxwell West and Su Yeon Chang and Luke Coffman and Martin Larocca and M. Cerezo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40173},
eprint = {2609.40173},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40173},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Practical fermionic shadows enabled by improved sample-complexity bounds
AU - Maxwell West
AU - Su Yeon Chang
AU - Luke Coffman
AU - Martin Larocca
AU - M. Cerezo
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40173
UR - https://arxiv.org/abs/2609.40173
AB - 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 𝒪(n^2k|O|_∞^2) to 𝒪(n^k|O|_∞^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 ∼ 10^9 to ∼ 10^5. That is, the new bound reduces the required number of shots by approximately 99.98%.
ER -