arXiv · 12 Nov 2026
Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation
Matteo De Francesco
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenCitations0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
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 show that adaptivity between copies can beat this barrier. On connected bipartite $d$-regular graphs of logarithmic diameter whose bipartition is hidden, nonadaptive learners still need $Θ(d^2\log n)$ copies, but a breadth-first adaptive learner needs only $O(d\log^2 n/\log\log n)$; revealing the bipartition brings the nonadaptive cost down to $Θ(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.
What the data shows
- No database records a citation yet, as is usual for a paper this new.
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (0)
What it cites, from open citation data, with Crossref's record of each.