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.ITCS.2025.11

Rank Lower Bounds on Non-Local Quantum Computation

Authors: Vahid R. Asadi, Eric Culf, and Alex May

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, f-routing and f-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y) in terms of the rank of a matrix g(x,y) whose entries are zero when f(x,y) = 0, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of f(x,y). Because of a relationship between f-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.

Cite as

Vahid R. Asadi, Eric Culf, and Alex May. Rank Lower Bounds on Non-Local Quantum Computation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{asadi_et_al:LIPIcs.ITCS.2025.11,
  author =	{Asadi, Vahid R. and Culf, Eric and May, Alex},
  title =	{{Rank Lower Bounds on Non-Local Quantum Computation}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.11},
  URN =		{urn:nbn:de:0030-drops-226399},
  doi =		{10.4230/LIPIcs.ITCS.2025.11},
  annote =	{Keywords: Non-local quantum computation, quantum position-verification, conditional disclosure of secrets}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2023.28

Rigidity for Monogamy-Of-Entanglement Games

Authors: Anne Broadbent and Eric Culf

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

In a monogamy-of-entanglement (MoE) game, two players who do not communicate try to simultaneously guess a referee’s measurement outcome on a shared quantum state they prepared. We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis and informs the players of her choice. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. That is, in order to win optimally, the players' strategy must be of a specific form, namely a convex combination of four unentangled optimal strategies generated by the Breidbart state. We extend this to show that strategies that win near-optimally must also be near an optimal state of this form. We also show rigidity for multiple copies of the game played in parallel. We give three applications: (1) We construct for the first time a weak string erasure (WSE) scheme where the security does not rely on limitations on the parties' hardware. Instead, we add a prover, which enables security via the rigidity of this MoE game. (2) We show that the WSE scheme can be used to achieve bit commitment in a model where it is impossible classically. (3) We achieve everlasting-secure randomness expansion in the model of trusted but leaky measurement and untrusted preparation and measurements by two isolated devices, while relying only on the temporary assumption of pseudorandom functions. This achieves randomness expansion without the need for shared entanglement.

Cite as

Anne Broadbent and Eric Culf. Rigidity for Monogamy-Of-Entanglement Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 28:1-28:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{broadbent_et_al:LIPIcs.ITCS.2023.28,
  author =	{Broadbent, Anne and Culf, Eric},
  title =	{{Rigidity for Monogamy-Of-Entanglement Games}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{28:1--28:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.28},
  URN =		{urn:nbn:de:0030-drops-175319},
  doi =		{10.4230/LIPIcs.ITCS.2023.28},
  annote =	{Keywords: Rigidity, Self-Testing Monogamy-of-Entanglement Games, Bit Commitment, Randomness Expansion}
}

Search Results

Documents authored by Culf, Eric

The Quantum Smooth Label Cover Problem Is Undecidable

Abstract

Cite as

Rank Lower Bounds on Non-Local Quantum Computation

Abstract

Cite as

Rigidity for Monogamy-Of-Entanglement Games

Abstract

Cite as

Thanks for your feedback!

Could not send message