Few-qubit behaviour and noise-robustness of quantum-classical separations in communication complexity

Specialeforsvar ved Marco Ugo Gambetta

Titel: Few-qubit behaviour and noise-robustness of quantum-classical separations in communication complexity

Abstract:  The Hidden Matching Problem and the Vector in Subspace Problem are known to give an asymptotic exponential separation between classical and quantum protocol for the communication complexity. The two main goals of this dissertation are to study the actual behaviours of the classical lower bounds, by retrieving the constants that characterize them, and to analyze the error robustness of the best known quantum protocols. We will present under which circumstances the quantum protocols outperform the classical strategies and in particular whether this could, in principle, be demonstrated with present noisy quantum devices.

Vejledere: Matthias Christandl, Johannes Borregaard
Censor:      Wojciech Szymanski, SDU