5 papers
XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
Richard Cleve, Eric Culf, Aviv Taller
It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynom…
Quantum polymorphism characterisation of commutativity gadgets in all quantum models
Eric Culf, Josse van Dobben de Bruyn, Peter Zeman
Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal g…
Almost perfect strategies for projection games are approximately tracial
Eric Culf
Projection games constitute an important class of nonlocal games where, for any answer from the first player, there is a unique correct answer for the second player. This class of…
Rank lower bounds on non-local quantum computation
Vahid R. Asadi, Eric Culf, Alex May
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 c…
Linear gate bounds against natural functions for position-verification
Vahid Asadi, Richard Cleve, Eric Culf +1
A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with…