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

Author: Mints, Mikhail

Year: 2026

Degree: Senior thesis (Major)

Advisors: Preskill, John P.; Anschuetz, Eric R.

Committee Member: None, None

Option: Computer Science; Mathematics

DOI: 10.7907/tgg7-nh54

Abstract

In this work, we analyze the average-case hardness of the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results: a weak hardness result for a wide class of stable quantum algorithms, and a strong hardness result for a much more restricted class of local quantum algorithms. We apply these results to establish concrete conditions under which known quantum algorithms fail to produce near-optimal solutions for this problem.

Files