Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

The Impossibility of Efficient Quantum Weak Coin-Flipping

Published

Author(s)

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