The Impossibility of Efficient Quantum Weak Coin-Flipping

TitleThe Impossibility of Efficient Quantum Weak Coin-Flipping
Publication TypeJournal Article
Year of Publication2019
AuthorsMiller, CA
Date Published9/22/2019

How can two parties with competing interests carry out a fair coin flip, using only a noiseless quantum channel? This problem (quantum weak coin-flipping) was formalized more than 15 years ago, and, despite some phenomenal theoretical progress, practical quantum coin-flipping protocols with vanishing bias have proved hard to find. In the current work we show that there is a reason that practical weak quantum coin-flipping is difficult: any quantum weak coin-flipping protocol with bias ε must use at least exp(Ω(1/ε√)) rounds of communication. This is a large improvement over the previous best known lower bound of Ω(loglog(1/ε)) due to Ambainis from 2004. Our proof is based on a theoretical construction (the two-variable profile function) which may find further applications.