The clock synchronization problem is to determine the time difference $\Delta$ between two spatially separated clocks. When message delivery times between the two clocks are uncertain, $O\left(2^{2n}\right)$ classical messages must be exchanged between the clocks to determine $n$ digits of $\Delta$. On the other hand, as we show, there exists a quantum algorithm to obtain $n$ digits of $\Delta$ while communicating only $O\left(n\right)$ quantum messages.

• Received 3 May 2000

DOI:https://doi.org/10.1103/PhysRevLett.85.2006