2026-07-28T00:20:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26460 2026-07-01T07:16:11Z ddc:004 open_access

The Quantum Smooth Label Cover Problem Is Undecidable Culf, Eric Mastel, Kieran Paddock, Connor Spirig, Taro Complexity Theory Constraint Satisfaction Problems Hardness of Approximation Quantum Computing We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP^* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige’s reduction from 3SAT to 3SAT5 (STOC'96) for BCS-MIP^*-protocols, which may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Culf and Kieran Mastel and Connor Paddock and Taro Spirig 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.71 urn:nbn:de:0030-drops-264602 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.71 eng https://creativecommons.org/licenses/by/4.0/legalcode