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.
Originalsprog | Engelsk |
---|---|
Titel | Innovations in Theoretical Computer Science Conference |
Status | Accepteret/In press - feb. 2025 |