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 classical communications.
We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number $R_{\mathrm{vm}}(k)$ to be the smallest value $n$ such that every $n$-vertex graph contains an independent set of size $k$ as a vertex-minor. Supported by our main result, we conjecture that $R_{\mathrm{vm}}(k)$ is polynomial in $k$. We prove $Ω(k^2) \leq R_{\mathrm{vm}}(k) \leq 2^k - 1$.
Answering a question of Claudet, we prove that the uniformly random graph G∼G(n,1/2) is Ω(n)-vertex-minor universal with high probability. That is, for some constant α≈0.911, any graph on any α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 classical communications.
We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number Rvm(k) to be the smallest value n such that every n-vertex graph contains an independent set of size k as a vertex-minor. Supported by our main result, we conjecture that Rvm(k) is polynomial in k. We prove Ω(k2)≤Rvm(k)≤2k−1.
We study the notion of k-stabilizer universal quantum state, that is, an n-qubit quantum state, such that it is possible to induce any stabilizer state on any k qubits, by using only local operations and classical communications. These states generalize the notion of k-pairable states introduced by Bravyi et al., and can be studied from a combinatorial perspective using graph states and k-vertex-minor universal graphs. First, we demonstrate the existence of k-stabilizer universal graph states that are optimal in size with n=Θ(k2) qubits. We also provide parameters for which a random graph state on Θ(k2) qubits is k-stabilizer universal with high probability. Our second contribution consists of two explicit constructions of k-stabilizer universal graph states on n=O(k4) qubits. Both rely upon the incidence graph of the projective plane over a finite field Fq. This provides a major improvement over the previously known explicit construction of k-pairable graph states with n=O(23k), bringing forth a new and potentially powerful family of multipartite quantum resources.
Stabilizer states play a central role in quantum information theory, and understanding their entanglement has motivated a large body of work. A well-studied question in particular is when a stabilizer state ∣ψ⟩ can be transformed into another stabilizer state ∣φ⟩ using only single-qubit Clifford operations and Pauli measurements. If this is possible, we say that ∣φ⟩ is a vertex-minor of ∣ψ⟩. Assuming Geelen's weak structural conjecture on vertex-minors, we establish the following general statement. For any fixed stabilizer state ∣φ⟩, the entanglement in stabilizer states ∣ψ⟩ that do not contain ∣φ⟩ as a vertex-minor is asymptotically constrained. More concretely, we show that the distance of any sufficiently rank-connected ∣ψ⟩ not containing ∣φ⟩ as a vertex-minor grows as O(logn), and prove similar results for the so-called locally accessible information, a quantity that captures the amount of information that can be learned through single-qubit Pauli measurements. Our results rely on (i) connecting the above two entanglement measures to rank functions of multimatroids, (ii) connecting the rank functions of circle stabilizer states to rank functions on 4-regular multigraphs, which asymptotically constrains the entanglement of circle stabilizer states, and (iii) using Geelen's weak structural conjecture on vertex-minors to `lift' the previous result to sufficiently connected states in proper vertex-minor-closed families of stabilizer states. Our results establish a connection between asymptotic stabilizer entanglement and forbidden vertex-minors, with direct implications for the entanglement that can be generated in quantum devices.
A k-pairable n-qubit state is a resource state that allows Local Operations and Classical Communication (LOCC) protocols to generate EPR-pairs among any k-disjoint pairs of the n qubits. Bravyi et al. introduced a family of k-pairable n-qubit states, where n grows exponentially with k. Our primary contribution is to establish the existence of 'small' pairable quantum states. Specifically, we present a family of k-pairable n-qubit graph states, where n is polynomial in k, namely n=O(k3ln3k). Our construction relies on probabilistic methods. Furthermore, we provide an upper bound on the pairability of any arbitrary quantum state based on the support of any local unitary transformation that has the shared state as a fixed point. This lower bound implies that the pairability of a graph state is at most half of the minimum degree up to local complementation of the underlying graph, i.e., k(∣G⟩)≤⌈δloc(G)/2⌉. We also investigate the related combinatorial problem of k-vertex-minor-universality: a graph G is k-vertex-minor-universal if any graph on any k of its vertices is a vertex-minor of G. When a graph is 2k-vertex-minor-universal, the corresponding graph state is k-pairable. More precisely, one can create not only EPR-pairs but also any stabilizer state on any 2k qubits through local operations and classical communication. We establish the existence of k-vertex-minor-universal graphs of order O(k4lnk). Finally, we explore a natural extension of pairability in the presence of errors or malicious parties and show that vertex-minor-universality ensures a robust form of pairability.
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an N-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2 and N≥4K−1, finds and verifies a homogeneous K-set using O(2KKlogηK) edge queries with failure probability at most η. At the Ramsey scale N=2n, this yields a homogeneous set of order ⌊n/2⌋+1 using O(NlogNlog(logN/η)) queries, improving on the O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12) quantum lower bound by a reduction from collision finding.
The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/2) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2). On that distribution a greedy quantum search uses only O(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.
Graph states are fundamental objects in the theory of quantum information due to their simple classical description and rich entanglement structure. They are also intimately related to instantaneous quantum polynomial-time (IQP) circuits, which have applications in quantum pseudorandomness and quantum advantage. For us, they are a toy model to understand the relation between circuit connectivity, entanglement structure, and computational complexity. In the worst case, a strict dichotomy in the computational universality of such graph states appears as a function of the degree d of a regular graph state [Ghosh , Phys. Rev. Lett. 131, 030601 (2023)]. In this paper, we study the average-case complexity of simulating random graph states of varying degree when measured in random product bases and give distinct evidence that a similar complexity-theoretic dichotomy exists in the average case. Specifically, we consider random d -regular graph states and prove three distinct results: First, we show two families of IQP circuits of depth d and show that they anticoncentrate for any 2 < d = o ( n 1 / 2 ) when measured in a random X - Y plane product basis. This implies anticoncentration for random constant-regular graph states. Second, in the regime d = Θ ( n c ) with c ∈ ( 0 , 1 ) , we prove that random d -regular graph states contain polynomially large grid graphs as induced subgraphs with high probability. This implies that they are universal resource states for measurement-based computation. Third, in the regime of high degree ( d ∼ n / 2 ), we show that random graph states are not sufficiently entangled to be trivially classically simulable, unlike Haar-random states. Proving the three results requires different techniques—the analysis of a classical statistical-mechanics model using Krawtchouck polynomials, graph-theoretic analysis using the switching method, and analysis of the ranks of submatrices of random adjacency matrices, respectively.