Quantum communication complexity using the quantum Zeno effect

The quantum Zeno effect (QZE) is the phenomenon in which the unitary evolution of a quantum state is suppressed, e.g., due to frequent measurements. Here, we investigate the use of the QZE in a class of communication complexity problems (CCPs). Quantum entanglement is known to solve certain CCPs beyond classical constraints. However, recent developments have yielded CCPs for which superclassical results can be obtained using only communication of a single d-level quantum state (qudit) as a resource. In the class of CCPs considered here, we show quantum reduction of complexity in three ways: using (i) entanglement and the QZE, (ii) a single qudit and the QZE, and (iii) a single qudit. We have performed a proof of concept experimental demonstrations of three party CCP protocol based on single-qubit communication with and without QZE.