{"id":"arxiv/2602.09049","url":"https://arxiv.org/abs/2602.09049","tags":["quant-ph","math.CO"],"score":0,"title":"Almost all graphs are vertex-minor universal","domain":"quant-ph","source":"arxiv","authors":["Ruben Ascoli","Bryce Frederickson","Sarah Frederickson","Caleb McFarland","Logan Post"],"reviews":0,"subject":"quant-ph","summary":"Answering a question of Claudet, we prove that the uniformly random graph $G\\sim \\mathbb G(n, 1/2)$ is $Ω(\\sqrt n)$-vertex-minor universal with high probability. That is, for some constant $α\\approx 0.911$, any graph on any $α\\sqrt n$ specified vertices of $G$ can be obtained as a vertex-minor of $G$. This has direct implications for quantum communications networks: an $n$-vertex $k$-vertex-minor universal graph corresponds to an $n$-qubit $k$-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any $k$ qubits using only local operations and…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-06","reactions":{}}