Quantum Science Seminar
Quantum Weak Coin Flipping
An interdisciplinary group of faculty & students studies problems in the theory of quantum information processing. A brief review of the most recent publications will be followed by a presentation on a specific paper or set of papers. All faculty and students are welcome.
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 cheating. 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 quantumsetting, protocols exist in which an adversarial party can bias the coin flip in their direction by no more than __ for every __ > 0. In this talk, I will begin to outline the nonconstructive proof of this result (which is optimal) due to Mochon in 2007. In particular, the talk will highlight the role of "point games", a formalism introduced for the proof that might have applications to more general two party computation. Time permitting, we will finish the entire proof, though more likely the end of the proof and related topics (like how to get a fair shot at that room) may be relegated to a later talk. Reference: "A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias" thanks to D. Aharonov, A. Chailloux, M. Ganz, I. Kerenidis, and L. Magnin (2014).