QUSCOPE seminar

Speaker: Matthias Christandl, Department of Mathematical Sciences, University of Copenhagen,

Title: Clean quantum and classical communication protocols

Abstract:

To compute a two-party function cleanly , the players must not only correctly calculate the function's value but also return allregisters to their initial states at the end of the communication protocol. Such protocols provide methods for implementing distributed computations, can be safely run in coherent superposition and provide lower bounds on the communication complexity of their non-clean counterparts.

Here we present clean protocols for calculating the Inner Product of two n-bit strings, showing that (in the absence of pre-shared entanglement) at most n+O(√n) bits or n + 4 qubits of communication are required. These provide new methods for implementing distribute CNOT or controlled-Z gates in parallel whilst minimizing the amount of communication. While evaluating a function cleanly is harder to perform than just computing the function, it can always be done using at most 2 n bits of communication for functions of n-bit strings. In contrast to the Inner Product, we show that nearly all Boolean functions require close to the maximal 2 n bits of classical communication to compute cleanly.

There will be coffee, tea and cake from 15:00.