Quantum Science Seminar

Quantum Weak Coin Flipping

Michael NewmanUniversity of Michigan, Ann Arbor

Suppose you are a new student enrolling at the University of Michigan set to move into
an apartment with a roommate. The apartment has one large bedroom and one small bedroom,
so you and your roommate agree via telephone to flip a coin for the larger room. Your roommate
promises you over the phone that he has a coin in his hand, he has flipped it, and you lost. Filled
with suspicion, you wish that there was some way to guarantee that your roommate didn't win by
It turns out that in the classical setting, no matter what protocol you agree to, an adversarial
party will always be able convince you of their victory given unbounded computational resource.
Such a procedure is called a weak coin flipping protocol, and it turns out that in the quantum
setting, protocols exist in which an adversarial party can bias the coin flip in their direction by no
more than x, for every x > 0.
Last time, we spoke about the equivalence between EBM point games and weak coin flipping
protocols. We noted that although this equivalence was nice, it was still difficult to write down a
point game. In this talk, we will discuss how the well-studied class of operator monotone functions
can be used to get a real handle on point games, and finish outlining the proof of existence.
Reference: "A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias,"
by D. Aharonov, A. Chailloux, M. Ganz, I. Kerenidis, and L. Magnin (2014)

Sponsored by