Showing quant-phShow all
3 papers · 1 filter
quant-ph2025
The quantum smooth label cover problem is undecidable
Eric Culf, Kieran Mastel, Connor Paddock +1
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…
quant-ph2025
Gap-preserving reductions and RE-completeness of independent set games
Laura ManÄinska, Pieter Spaas, Taro Spirig +1
In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof…
quant-ph2024
A Quantum Unique Games Conjecture
Hamoon Mousavi, Taro Spirig
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…