Id: arxiv/2611.16456 Url: https://arxiv.org/abs/2611.16456 Tags: quant-ph Score: 0 Title: Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation Domain: quant-ph Source: arxiv Authors: Matteo De Francesco Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-12 Page: https://delphi.science/r/arxiv/2611.16456 We study how many copies of an unknown $n$-qubit graph state are needed to identify its graph when every qubit is measured in the $X$, $Y$ or $Z$ basis. Ouyang and Tomamichel showed that $O(d^2\log n)$ copies suffice for $d$-regular graphs, while any measurement needs $Ω(d\log n)$, and asked whether the quadratic dependence on $d$ is necessary. We show that it is for nonadaptive learners: if $d^3\ln n\le n$, every nonadaptive strategy needs $Ω(d^2\log n)$ copies, even with an unrestricted classical decoder and even if a small constant fraction of the edges may be reported wrongly. We then…