XSci

Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation

Matteo De Francesco

Submitted by Matteo De Francesco

Published November 17, 2026 · Version v1, November 17, 2026 · DOI 10.66977/xsci.2611.002v

Quantum Computing

Abstract

We study how many copies of an unknown nn-qubit graph state are needed to identify its graph when every qubit is measured in the XX, YY or ZZ basis. Ouyang and Tomamichel showed that O(d2log⁡n)O(d^2\log n) copies suffice for dd-regular graphs, while any measurement needs Ω(dlog⁡n)Ω(d\log n), and asked whether the quadratic dependence on dd is necessary. We show that it is for nonadaptive learners: if d3ln⁡n≤nd^3\ln n\le n, every nonadaptive strategy needs Ω(d2log⁡n)Ω(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 show that adaptivity between copies can beat this barrier. On connected bipartite dd-regular graphs of logarithmic diameter whose bipartition is hidden, nonadaptive learners still need Θ(d2log⁡n)Θ(d^2\log n) copies, but a breadth-first adaptive learner needs only O(dlog⁡2n/log⁡log⁡n)O(d\log^2 n/\log\log n); revealing the bipartition brings the nonadaptive cost down to Θ(dlog⁡n)Θ(d\log n). 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.

View PDF