An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

# The Impossibility of Efficient Quantum Weak Coin-Flipping

Published

Carl A. Miller

### Abstract

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 ( \Ω (1/\sqrt{\epsilon} ))$ rounds of communication. This is a large improvement over the previous best known lower bound of $\Ω ( \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.
Proceedings Title
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Conference Dates
June 22-26, 2020
Conference Location
Chicago, IL
Conference Title
52nd Annual ACM Symposium on Theory of Computing (STOC 2020)

### Keywords

quantum cryptography, randomness, complex analysis
Created June 21, 2020, Updated August 20, 2020