Title: Dining Philosophers, Leader Election and Ring Size problems, in the quantum setting,
Abstract: We provide the first quantum (exact) protocol for the Dining Philosophers
problem (DP), a central problem in distributed algorithms. It is well known
that the problem cannot be solved exactly in the classical setting. We then use
our DP protocol to provide a new quantum protocol for the tightly related
problem of exact leader election (LE) on a ring, improving significantly in
both time and memory complexity over the known LE protocol by Tani et. al. To
do this, we show that in some sense the exact DP and exact LE problems are
equivalent; interestingly, in the classical non-exact setting they are not.
Hopefully, the results will lead to exact quantum protocols for other important
distributed algorithmic questions; in particular, we discuss interesting
connections to the ring size problem, as well as to a physically motivated
question of breaking symmetry in 1D translationally invariant systems.