DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.71

The Quantum Smooth Label Cover Problem Is Undecidable

Authors: Eric Culf, Kieran Mastel, Connor Paddock, and Taro Spirig

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Eric Culf, Kieran Mastel, Connor Paddock, and Taro Spirig. The Quantum Smooth Label Cover Problem Is Undecidable. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 71:1-71:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{culf_et_al:LIPIcs.ICALP.2026.71,
  author =	{Culf, Eric and Mastel, Kieran and Paddock, Connor and Spirig, Taro},
  title =	{{The Quantum Smooth Label Cover Problem Is Undecidable}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{71:1--71:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.71},
  URN =		{urn:nbn:de:0030-drops-264602},
  doi =		{10.4230/LIPIcs.ICALP.2026.71},
  annote =	{Keywords: Complexity Theory, Constraint Satisfaction Problems, Hardness of Approximation, Quantum Computing}
}

Document

DOI: 10.4230/LIPIcs.TQC.2025.8

Self-Testing in the Compiled Setting via Tilted-CHSH Inequalities

Authors: Arthur Mehta, Connor Paddock, and Lewis Wooltorton

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract

This work investigates the family of extended tilted-CHSH inequalities in the single-prover cryptographic compiled setting. In particular, we show that a quantum polynomial-time prover can violate these Bell inequalities by at most negligibly more than the violation achieved by two non-communicating quantum provers. To obtain this result, we extend a sum-of-squares technique to monomials with arbitrarily high degree in the Bob operators and degree at most one in the Alice operators. We also introduce a notion of partial self-testing for the compiled setting, which resembles a weaker form of self-testing in the bipartite setting. As opposed to certifying the full model, partial self-testing attempts to certify the reduced states and measurements on separate subsystems. In the compiled setting, this is akin to the states after the first round of interaction and measurements made on that state. Lastly, we show that the extended tilted-CHSH inequalities satisfy this notion of a compiled self-test.

Cite as

Arthur Mehta, Connor Paddock, and Lewis Wooltorton. Self-Testing in the Compiled Setting via Tilted-CHSH Inequalities. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.TQC.2025.8,
  author =	{Mehta, Arthur and Paddock, Connor and Wooltorton, Lewis},
  title =	{{Self-Testing in the Compiled Setting via Tilted-CHSH Inequalities}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.8},
  URN =		{urn:nbn:de:0030-drops-240577},
  doi =		{10.4230/LIPIcs.TQC.2025.8},
  annote =	{Keywords: Compiled Bell scenarios, self-testing}
}

Search Results

Documents authored by Paddock, Connor

The Quantum Smooth Label Cover Problem Is Undecidable

Abstract

Cite as

Self-Testing in the Compiled Setting via Tilted-CHSH Inequalities

Abstract

Cite as

Thanks for your feedback!

Could not send message