{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{}}