Richard Cleve

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. These are well studied in the context of position-verification, where they are leading candidates for feasible and secure verification schemes. Both settings require an honest prover implement only O(1) quantum operations. We prove that a dishonest prover must use linear quantum resources to attack the same scheme. First, we give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Our bound can be stated in terms of the quantum non-deterministic communication complexity of f. For the equality, non-equality, and greater-than functions we obtain linear lower bounds on entanglement for f-routing and f-BB84 in the perfect setting. In a second result, which applies in the robust setting, we give a new lower bound on the number of quantum gates and measurements needed to attack these verification schemes. We lower bound the gates plus measurements linearly in the simultaneous message passing cost of the function f. This leads to a linear bound against the inner product function. This gives a clear separation between the difficulty of implementing these tasks in the honest and dishonest settings, and does so in a noise robust and loss tolerant setting.

We investigate various aspects of the nonlocal effects that can occur when entangled quantum information is shared between two parties. We explain how these effects can significantly affect the soundness of two-prover interactive proof systems--which raises new questions about the expressive power of these systems. We then embark on a program to establish bounds on what nonlocal effects can do. These bounds can be regarded as generalizations of the so-called Tsirelson inequality. We also consider the amount of entanglement required to achieve optimal nonlocal effects. This is joint work with Peter Hoyer, Ben Toner, and John Watrous.

Recent advances in communication complexity in a setting where quantum information is available are reviewed. Holevo's Theorem implies that n qubits cannot convey more classical information than n bits. Nevertheless, there are information processing tasks that require communication and for which using qubits instead of bits results in substantial savings.