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(2^2n)$ 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(n) quantum messages.
%0 Generic
%1 citeulike:366719
%A Chuang, Isaac
%D 2000
%K algorithm clock fdistributed quantum synchronization
%T Quantum algorithm for distributed clock synchronization
%U http://arxiv.org/abs/quant-ph/0005092
%X 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(2^2n)$ 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(n) quantum messages.
@misc{citeulike:366719,
abstract = {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(2^{2n})$ 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(n) quantum messages.},
added-at = {2007-08-18T13:22:24.000+0200},
author = {Chuang, Isaac},
biburl = {https://www.bibsonomy.org/bibtex/25cc162e73dbad770c53360d83ccdebac/a_olympia},
citeulike-article-id = {366719},
description = {citeulike},
eprint = {quant-ph/0005092},
interhash = {a96ac51047b4ec6b3b1682ea72a73379},
intrahash = {5cc162e73dbad770c53360d83ccdebac},
keywords = {algorithm clock fdistributed quantum synchronization},
month = May,
priority = {2},
timestamp = {2007-08-18T13:22:42.000+0200},
title = {Quantum algorithm for distributed clock synchronization},
url = {http://arxiv.org/abs/quant-ph/0005092},
year = 2000
}