Experimental demonstration of quantum advantage for one-way communication complexity surpassing best-known classical protocol

Abstract

The hidden matching communication problem features an exponential classical-quantum gap, but a demonstration is extremely challenging. Here, the authors define a more feasible variant called sampling matching problem, and realise a proof-of-principle implementation beating the best known classical protocol.