Miller, C.
(2020),
The Impossibility of Efficient Quantum Weak Coin-Flipping, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, IL, [online], https://doi.org/10.1145/3357713.3384276
(Accessed April 24, 2024)
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
Author(s)
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)
Pub Type
Conferences
Download Paper
Keywords
quantum cryptography, randomness, complex analysis
Citation
Created June 21, 2020, Updated August 20, 2020