3 papers
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
Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states
Connor Paddock
We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint syst…
quant-ph2025
Satisfiability problems and algebras of boolean constraint system games
Connor Paddock, William Slofstra
Mermin and Peres showed that there are boolean constraint systems (BCSs) which are not satisfiable, but which are satisfiable with quantum observables. This has led to a burgeoning…