EECS | Electrical Engineering and Computer Science


Quantum Info Processing Seminar

Quantum Weak Coin Flipping

Michael Newman


University of Michigan, Ann Arbor
 
Thursday, October 30, 2014
1:00pm - 2:30pm
4941 Beyster Bldg.

Add to Google Calendar
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.

About the Event

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 quantum setting, 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).

Additional Information

Contact: Carl Miller

Phone: 734-647-7127

Email: carlmi@umich.edu

Sponsor(s): EECS

Open to: Public

Web Page: http://eecs.umich.edu/qip