Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.26028

A Spectral Proof of the Hypergraph Moore Bound

Alexander Schmidhuber, Matthew B. Hastings

math.COcs.DMquant-phSubmitted Jul 28, 2026• Announced Jul 29, 2026
arXivHTMLPDF

Abstract

A nonempty subfamily of a $k$-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for $k=2$ these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants $A$ and $C$ (independent of $k$) such that for every $k\ge3$ and every $1\le\ell\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C\,n^{k/2}/\ell^{k/2-1}$ hyperedges contains an even cover of size at most $A\,\ell\log(en/\ell)$. Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.

Comments
14 pages

Related papers

Magic Eulerian Hypergraphs

Stefan Trandafir

Motivated by the phenomenon of contextuality in quantum physics we study a particular family of proofs of the Kochen-Specker theorem.A proof is represented by a pair consisting of a hypergraph where each vertex has even degree, called an Eulerian hypergraph, and a labeling of its vertices.If a hypergraph admits a labeling constituting a proof, we say it is magic.We are interested in determining whether a given hypergraph is magic.Working with the duals of Eulerian hypergraphs, we develop the parity minor relation, which allows us to establish a concept of minimality for the magic property.We introduce a splitting operation to show that certain hypergraphs are not magic.We combine the parity minor relation and the splitting operation in order to search for minimally magic hypergraphs whose duals are grafts, hypergraphs with one edge of size four and all other edges of size two.

•May 8, 2017•0 citations

When the parity bound is tight for graph scenarios

Igor Postanovskyi

For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η*_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η*_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.

•Nov 9, 2026•0 citations

Three-uniform edge-ordered hypergraph quantum states: entanglement and its relation to hypergraph properties

N. A. Susulovska, Kh. P. Gnatenko

The encoding of 3-uniform edge-ordered weighted hypergraphs into multiqubit quantum states is proposed. We derive an analytical expression for the geometric measure of entanglement of hypergraph quantum states and establish its relation to hypergraph properties. The results establish a direct connection between the local structure of hypergraphs, hyperedge weights, and the entanglement of the corresponding quantum states. For equally weighted hypergraphs, it is shown that the entanglement depends explicitly on the vertex degree. The dependence of entanglement on hypergraph parameters is studied analytically and using quantum computing. Hypergraph states associated with chain, star, regular lattice, and binary-tree hypergraphs are examined, and their entanglement is quantified using quantum computing. These results open up the possibility of studying hypergraph properties with quantum programming.

quant-pharXiv:2609.30399•Sep 28, 2026•1 citation

Quantum Query Complexity of Subgraph Isomorphism and Homomorphism

Raghav Kulkarni, Supartha Podder

Let H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f_H(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha_H denote the cardinality of a maximum independent set of H. In this paper we show: Q(f_H) = Omega( sqrt{alpha_H * n}), where Q(f_H) denotes the quantum query complexity of f_H. As a consequence we obtain lower bounds for Q(f_H) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that Q(f_H) = Omega(n^{3/4}) for any H, improving on the previously best known bound of Omega(n^{2/3}) [M. Santha/A. Chi-Chih Yao, unpublished manuscript]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n^{3/4}) bound for Q(f_H) matches the square root of the current best known bound for the randomized query complexity of f_H, which is Omega(n^{3/2}) due to Groger. Interestingly, the randomized bound of Omega(alpha_H * n) for f_H still remains open. We also study the Subgraph Homomorphism Problem, denoted by f_{[H]}, and show that Q(f_{[H]}) = Omega(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n^{4/5}) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n^{3/4}) bound. For the Subgraph Homomorphism, we obtain an Omega(n^{3/2}) bound for the same.

arXiv:1509.06361•Leibniz international proceedings in informatics•Sep 21, 2015•7 citations

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$-qubit Pauli operator $P$ and an angle $θ\in [0,2π)$, both uniformly at random, and apply $e^{\mathrm i θP}$. (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ (including central phases of the parent group) independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the gap bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary $t$-designs after $\mathcal{O}(nt)$ steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be $\mathcal{O}(2^{cn})$ for some $c < 1$. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal $t$-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for $t=2$.

quant-pharXiv:2607.20919•Jul 24, 2026•8 citations

Almost all graphs are vertex-minor universal

Ruben Ascoli, Bryce Frederickson, Sarah Frederickson +2 more

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$.

quant-pharXiv:2602.09049•Feb 10, 2026
A nonempty subfamily of a kkk-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for k=2k=2k=2 these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants AAA and CCC (independent of kkk) such that for every k≥3k\ge3k≥3 and every 1≤ℓ≤n1\le\ell\le n1≤ℓ≤n, any kkk-uniform hypergraph on nnn vertices with more than C nk/2/ℓk/2−1C\,n^{k/2}/\ell^{k/2-1}Cnk/2/ℓk/2−1 hyperedges contains an even cover of size at most A ℓlog⁡(en/ℓ)A\,\ell\log(en/\ell)Aℓlog(en/ℓ). Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.
Motivated by the phenomenon of contextuality in quantum physics we study a particular family of proofs of the Kochen-Specker theorem.A proof is represented by a pair consisting of a hypergraph where each vertex has even degree, called an Eulerian hypergraph, and a labeling of its vertices.If a hypergraph admits a labeling constituting a proof, we say it is magic.We are interested in determining whether a given hypergraph is magic.Working with the duals of Eulerian hypergraphs, we develop the parity minor relation, which allows us to establish a concept of minimality for the magic property.We introduce a splitting operation to show that certain hypergraphs are not magic.We combine the parity minor relation and the splitting operation in order to search for minimally magic hypergraphs whose duals are grafts, hypergraphs with one edge of size four and all other edges of size two.
For a k-regular graph of odd order n we study the edge-ray scenario (contexts = vertices, rays = edges, uniform one-hot rows, each outcome bit flipped with probability η/2). A parity argument gives η*_F ≥ η_par = 1 − (1 − 2/n)^(1/k); we ask when it is tight. We prove tightness, even in the strong form (every S_k-symmetric row law on the parity slice), for locally set-transitive graphs containing all (a, b)-subgraphs, among them the odd graph K(7, 3) (for odd cycles this also follows from the complete set of n-cycle noncontextuality inequalities of Araújo et al.). For vertex-transitive graphs we reduce tightness to reachability of k/2 explicit staircase vertices of a weight polytope, show that the first one is reachable iff a balancing condition on perfect matchings holds, and prove this condition for every connected vertex-transitive graph of odd order; the proof uses the theorem of Zhang and Sun that such graphs of degree ≥ 4 are 3-factor-critical. Since the last staircase vertex is always reachable, tightness follows for every connected vertex-transitive graph of odd order and degree 4; for the middle staircase vertices we give a reduction to random regular spanning subgraphs with uniform rows and an odd-cut condition. Among the 406 connected vertex-transitive graphs of odd order n ≤ 21 we certify tightness exactly for 312, including all 287 of degree k ≤ 10; without vertex transitivity the bound can fail. An exact matching criterion shows that the strong form fails for 163 of the 406 graphs. For the edge scenario of K_n we prove η*_F = 1 − (2⌈n/2⌉ − 1)^(−1/2) for all n ≥ 2 (formalised in Lean), and show that the sufficient condition of our earlier paper (paper 6, 10.5281/zenodo.23481180) fails for n ≥ 6 and for the two-qubit doily, although equality holds there.
The encoding of 3-uniform edge-ordered weighted hypergraphs into multiqubit quantum states is proposed. We derive an analytical expression for the geometric measure of entanglement of hypergraph quantum states and establish its relation to hypergraph properties. The results establish a direct connection between the local structure of hypergraphs, hyperedge weights, and the entanglement of the corresponding quantum states. For equally weighted hypergraphs, it is shown that the entanglement depends explicitly on the vertex degree. The dependence of entanglement on hypergraph parameters is studied analytically and using quantum computing. Hypergraph states associated with chain, star, regular lattice, and binary-tree hypergraphs are examined, and their entanglement is quantified using quantum computing. These results open up the possibility of studying hypergraph properties with quantum programming.
Let H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f_H(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha_H denote the cardinality of a maximum independent set of H. In this paper we show: Q(f_H) = Omega( sqrt{alpha_H * n}), where Q(f_H) denotes the quantum query complexity of f_H. As a consequence we obtain lower bounds for Q(f_H) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that Q(f_H) = Omega(n^{3/4}) for any H, improving on the previously best known bound of Omega(n^{2/3}) [M. Santha/A. Chi-Chih Yao, unpublished manuscript]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n^{3/4}) bound for Q(f_H) matches the square root of the current best known bound for the randomized query complexity of f_H, which is Omega(n^{3/2}) due to Groger. Interestingly, the randomized bound of Omega(alpha_H * n) for f_H still remains open. We also study the Subgraph Homomorphism Problem, denoted by f_{[H]}, and show that Q(f_{[H]}) = Omega(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n^{4/5}) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n^{3/4}) bound. For the Subgraph Homomorphism, we obtain an Omega(n^{3/2}) bound for the same.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n)\mathsf{SU}(2^n)SU(2n) on nnn qubits. (i) Random Pauli Rotation: choose an nnn-qubit Pauli operator PPP and an angle θ∈[0,2π)θ\in [0,2π)θ∈[0,2π), both uniformly at random, and apply eiθPe^{\mathrm i θP}eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1n-1n−1 unitaries UiU_{i}Ui​ uniformly at random from SU(4)\mathsf{SU}(4)SU(4) (including central phases of the parent group) independently, and apply U2j−1U_{2j-1}U2j−1​ on two qubits 2j−1,2j2j-1, 2j2j−1,2j and then U2jU_{2j}U2j​ on two qubits 2j,2j+12j, 2j+12j,2j+1. Importantly, the gap bounds are independent of nnn and apply for all finite dimensional unitary representations of SU(2n)\mathsf{SU}(2^n)SU(2n) uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary ttt-designs after O(nt)\mathcal{O}(nt)O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn)\mathcal{O}(2^{cn})O(2cn) for some c<1c < 1c<1. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal ttt-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2t=2t=2.
Answering a question of Claudet, we prove that the uniformly random graph G∼G(n,1/2)G\sim \mathbb G(n, 1/2)G∼G(n,1/2) is Ω(n)Ω(\sqrt n)Ω(n​)-vertex-minor universal with high probability. That is, for some constant α≈0.911α\approx 0.911α≈0.911, any graph on any αnα\sqrt nαn​ specified vertices of GGG can be obtained as a vertex-minor of GGG. This has direct implications for quantum communications networks: an nnn-vertex kkk-vertex-minor universal graph corresponds to an nnn-qubit kkk-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any kkk 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)R_{\mathrm{vm}}(k)Rvm​(k) to be the smallest value nnn such that every nnn-vertex graph contains an independent set of size kkk as a vertex-minor. Supported by our main result, we conjecture that Rvm(k)R_{\mathrm{vm}}(k)Rvm​(k) is polynomial in kkk. We prove Ω(k2)≤Rvm(k)≤2k−1Ω(k^2) \leq R_{\mathrm{vm}}(k) \leq 2^k - 1Ω(k2)≤Rvm​(k)≤2k−1.