The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem

@misc{mints2026quantum,
  title = {{The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem}},
  author = {Mikhail Mints and Eric R. Anschuetz},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.10838},
  eprint = {2609.10838},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10838},
}

TY  - UNPB
TI  - The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
AU  - Mikhail Mints
AU  - Eric R. Anschuetz
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.10838
UR  - https://arxiv.org/abs/2609.10838
AB  - 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 ∞. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.
ER  -