



@article {2629,
	title = {The impossibility of efficient quantum weak coin flipping},
	journal = {STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing  },
	year = {2020},
	month = {6/2020},
	pages = {916-929},
	abstract = {<p>How can two parties with competing interests carry out a fair coin flip across a quantum communication 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/\&radic;є )) rounds of communication. This is a large improvement over the previous best known lower bound of Ω ( log log(1/є )) due to Ambainis from 2004. Our proof is based on a theoretical construction (the two-variable profile function) which may find further applications.</p>},
	doi = {https://doi.org/10.1145/3357713.3384276},
	author = {Carl Miller}
}
