{"id":"arxiv/2609.10838","url":"https://arxiv.org/abs/2609.10838","tags":["quant-ph","cs.CC"],"score":0,"title":"The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem","domain":"quant-ph","source":"arxiv","authors":["Mikhail Mints","Eric R. Anschuetz"],"reviews":0,"subject":"quant-ph","summary":"In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}