A similar problem is God's Coin Toss as described in Scott Aaronson's excellent lecture series (and book) "Quantum Computing Since Democritus":

http://www.scottaaronson.com/democritus/lec17.html