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 wid
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 k-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where k is independent of L, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order \infty. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.