REVIEW
Practical fermionic shadows enabled by improved sample-complexity bounds
Quantum Physics · Submitted 30 Sep 2026 · 54 references
Pith's verdict: A genuinely new tight bound for matchgate shadows with a complete-looking proof; the load-bearing Lemma 1 constant deserves independent numerical verification before the 3/2 claim goes to print.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
For any fermionic observable of Majorana degree 2k, matchgate shadows estimate it with O(n^k) shots instead of O(n^{2k}), and the bound is asymptotically tight up to a factor 3/2.
The reading
What carries the argument
The proof turns on a single technical object: a signed function $w$ on the $2n$ Majorana indices whose Krawtchouk transform at degrees $4r$ reproduces the sequence $q_r = p_{k-r}/a_{n,k}$ governing the variance expansion, and whose positive part has total weight at most $3/2$. That weight control is what converts the variance formula into the operator-norm bound of Theorem 1. To construct $w$, the paper invokes Lemma 1, which builds a positive function $\rho_y$ with prescribed transform using Gaussian quadrature with respect to the Krawtchouk measure and the Hermite remainder formula; the delicate step is a walk-counting bijection bounding the weight of walks on a weighted chain from $0$ to $0$ that visit vertex $d$ by walks from $0$ to $2d$, capped by $B_{N,d}/\sqrt{\binom{N}{2d}}$. The matchgate 3-design property is what reduces the Haar average to this finite combinatorics.
Extended reading notes
Core claim
The central claim is Theorem 1: for any observable $O$ supported on a single homogeneous Majorana sector $L_{2k}$ of an $n$-mode system, the matchgate-shadow estimator satisfies $\mathrm{Var}[\hat{o}] \le \tfrac{3}{2} a_{n,k}^{-1}\|O\|_\infty^2$, where $a_{n,k} = \binom{n}{k}/\binom{2n}{2k}$. Since $a_{n,k}^{-1} \sim n^k$ for fixed $k$, this converts the prior sample complexity $\mathcal{O}(n^{2k}\|O\|_\infty^2)$ into $\mathcal{O}(n^k\|O\|_\infty^2)$, which the paper states is asymptotically tight up to the constant $3/2$. That constant is believed to be an artifact of the proof: the bound is saturated by a single Majorana monomial of degree $2k$, whose known optimal scaling this result reproduces for all homogeneous observables.
Load-bearing premise
Everything rests on a single bounding step inside Lemma 1: the claim that walks from $0$ to $0$ which visit vertex $d$ carry less total weight than walks from $0$ to $2d$, scaled by $B_{N,d}/\sqrt{\binom{N}{2d}}$; if that inequality is wrong, the constant $3/2$ and hence the theorem's stated form fails.
Editorial extensions
If this is right
- Estimating any homogeneous degree-$2k$ fermionic observable now costs $\mathcal{O}(n^k \|O\|_\infty^2)$ shots, matching the optimal scaling previously established only for a single Majorana monomial.
- For a 50-site open Hubbard chain with $t=1$, $V=4$ at additive precision $0.1$, the required shots drop from $\sim 10^9$ to $\sim 10^5$, a reduction of roughly 99.98%.
- For operators spread over several homogeneous sectors, Corollary 1 bounds the variance by $\tfrac{3}{2}\bigl(\sum_k \|O_{2k}\|_\infty/\sqrt{a_{n,k}}\bigr)^2$, and with at most $n/2$ sectors it merely weakens by a factor $K$.
- The bound is asymptotically tight up to the factor $3/2$, since it is saturated by a single Majorana string of degree $2k$.
Reading between the lines
- The constant $3/2$ is almost certainly removable: the authors' numerical checks point to the optimal constant being $1$, and the single-monomial case already achieves $1$.
- The Krawtchouk-transform weight construction may transfer to other classical shadow protocols whose measurement channels have known spectra, potentially tightening the generic bounds of Eqs. (11)-(12), although the paper does not show how.
- Combined with the separately known logarithmic-depth matchgate 3-design construction on all-to-all architectures, the improved sample complexity makes practical fermionic shadow tomography on trapped-ion or neutral-atom hardware a realistic near-term target, a step the paper mentions without making it the main claim.
Original 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 $\mathcal{O}(n^{2k}\|O\|_\infty^2)$ to $\mathcal{O}(n^{k}\|O\|_\infty^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 $\sim 10^9$ to $\sim 10^5$. That is, the new bound reduces the required number of shots by approximately $99.98\%$.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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 $\mathcal{O}(n^{2k}\|O\|_\infty^2)$ to $\mathcal{O}(n^{k}\|O\|_\infty^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 $\sim 10^9$ to $\sim 10^5$. That is, the new bound reduces the required number of shots by approximately $99.98\%$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Classical shadow tomography is widely touted as supplying a family of methods for extracting information from quantum systems with polynomially scaling sample-complexities. | background 1.00 | 0.04 | 0.02 | asserted 0.89 |
| s1 | In the current era of quantum computers possessing on the order of hundreds of qubits, however, polynomial scaling can nonetheless be prohibitive. | background 0.76 | 0.06 | 0.02 | asserted 0.96 |
| s2 | Thus, there is a strong practical need for obtaining sample-complexity bounds which are as tight as possible. | background 0.56 | 0.05 | 0.03 | asserted 0.97 |
| s3 | Here we address this in the case of fermionic (matchgate) shadows. | contribution 0.97 | 0.58 | 0.04 | asserted 0.82 |
| s4 | For an arbitrary observable $O$ of Majorana degree $2k$, we improve the previously known sample-complexity bound of $\mathcal{O}(n^{2k}\|O\|_\infty^2)$ to $\mathcal{O}(n^{k}\|O\|_\infty^2)$, which is asymptotically tight. | result 0.71 | 0.95 | 0.89 | asserted 1.00 |
| s5 | 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 $\sim 10^9$ to $\sim 10^5$. | result 0.96 | 0.83 | 0.11 | asserted 1.00 |
| s6 | That is, the new bound reduces the required number of shots by approximately $99.98\%$. | interpretation 0.51 | 0.81 | 0.12 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2609.40173 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.