  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 $\epsilon$ must use at least $\exp (
\Omega (1/\sqrt{\epsilon} ))$ rounds of communication. This is a large
improvement over the previous best known lower bound of $\Omega ( \log \log
(1/\epsilon ))$ due to Ambainis from 2004. Our proof is based on a theoretical
construction (the two-variable profile function) which may find further
applications.
