A Quantum Unique Games Conjecture

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

After the NP-hardness of computational problems such as $3$SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum nonlocal games extensions of some of these problems are known to be hard—indeed undecidable—their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.
OriginalsprogEngelsk
TitelInnovations in Theoretical Computer Science Conference
StatusAccepteret/In press - feb. 2025

Citationsformater