Abstract
After the NP-hardness of computational problems such as 3SAT 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.
| Original language | English |
|---|---|
| Title of host publication | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 |
| Editors | Raghu Meka |
| Number of pages | 16 |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publication date | 2025 |
| Article number | 76 |
| ISBN (Electronic) | 9783959773614 |
| DOIs | |
| Publication status | Published - 2025 |
| Event | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 - New York, United States Duration: 7 Jan 2025 → 10 Jan 2025 |
Conference
| Conference | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 |
|---|---|
| Country/Territory | United States |
| City | New York |
| Period | 07/01/2025 → 10/01/2025 |
| Series | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 325 |
| ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:© Hamoon Mousavi and Taro Spirig.
Keywords
- Fourier analysis
- hardness of approximation
- noncommutative constraint satisfaction problems
- quantum computing