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…
Lower bounds on non-local computation from controllable correlation
Richard Cleve, Alex May
Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely unchara…
Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
Vahid R. Asadi, Richard Cleve
The Tree Evaluation Problem () is a computational problem originally proposed as a candidate to prove a separation between complexity classes and $\…
Improved Clifford operations in constant commutative depth
Richard Cleve, Zhiqian Ding, Luke Schaeffer
The commutative depth model allows gates that commute with each other to be performed in parallel. We show how to compute Clifford operations in constant commutative depth more eff…
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…