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.
| Originalsprog | Engelsk |
|---|---|
| Titel | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 |
| Redaktører | Raghu Meka |
| Antal sider | 16 |
| Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publikationsdato | 2025 |
| Artikelnummer | 76 |
| ISBN (Elektronisk) | 9783959773614 |
| DOI | |
| Status | Udgivet - 2025 |
| Begivenhed | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 - New York, USA Varighed: 7 jan. 2025 → 10 jan. 2025 |
Konference
| Konference | 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 |
|---|---|
| Land/Område | USA |
| By | New York |
| Periode | 07/01/2025 → 10/01/2025 |
| Navn | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Vol/bind | 325 |
| ISSN | 1868-8969 |
Bibliografisk note
Funding Information:Hamoon Mousavi: Supported by a Simons-CIQC postdoctoral fellowship through NSF QLCI Grant No. 2016245. Taro Spirig: Supported by the European Union under the Grant Agreement No 101078107, QInteract and VILLUM FONDEN via Villum Young Investigator grant (No 37532) and the QMATH Centre of Excellence (Grant No 10059). We thank Henry Yuen for valuable discussions on the topics explored in this paper. We thank Eric Culf and Michael Chapman for helpful discussions.
Publisher Copyright:
© Hamoon Mousavi and Taro Spirig.