Richard Cleve

Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on even most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, and typically lead to non-trivial lower bounds. Concretely, we give lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\SWAP}$, the XX interaction, Haar random two qubit gates, and many others, none of which previously had known lower bounds. For the CNOT gate one of our techniques gives a tight lower bound, fully resolving its entanglement cost. Our proof technique makes use of two new properties of unitaries that we introduce, called the \emph{controllable correlation} and \emph{controllable entanglement}. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting. The lower bound from controllable correlation has an elementary proof and applies to most unitaries, but does not appear to be tight for any of the unitaries we study. The lower bound from controllable entanglement is tight for CNOT but fails for generic unitaries. Its proof is less elementary; it requires the consideration of the i.i.d. setting and application of Shannon theory results, with the characterization of finite block length Schumacher compression being a key tool.

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.