Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation
Matteo De Francesco
Abstract
We study how many copies of an unknown -qubit graph state are needed to identify its graph when every qubit is measured in the , or basis. Ouyang and Tomamichel showed that copies suffice for -regular graphs, while any measurement needs , and asked whether the quadratic dependence on is necessary. We show that it is for nonadaptive learners: if , every nonadaptive strategy needs copies, even with an unrestricted classical decoder and even if a small constant fraction of the edges may be reported wrongly. We then show that adaptivity between copies can beat this barrier. On connected bipartite -regular graphs of logarithmic diameter whose bipartition is hidden, nonadaptive learners still need copies, but a breadth-first adaptive learner needs only ; revealing the bipartition brings the nonadaptive cost down to . The lower bounds rest on a simple fact: one copy reveals at most the binary nullity of a principal submatrix of the adjacency matrix. We control this nullity for random unions of perfect matchings through Fourier estimates and, in the bipartite case, a method-of-types argument.