The prospect of interactive quantum communication leads to stunning advantages over its classical counterpart: some specifically crafted problems have provable exponential quantum advantage. However, the underlying protocols assume perfect quantum communication as well as local processing. What about more restricted models of quantum computation and communication which are closer to what is achievable in the near future? Can we still obtain substantial quantum advantages with such?

 

We propose a protocol based on coherent states and linear optics operations for solving the appointment-scheduling problem. Our main protocol leaks strictly less information about each party’s input than the optimal classical protocol, even when considering experimental errors. Along with the ability to generate constant amplitude coherent states over two modes, this protocol requires the ability to transfer these modes back-and-forth between the two parties multiple times with low coupling loss. The implementation requirements are thus still challenging. Along the way, we develop new tools to study quantum information cost of interactive protocols in the finite regime.