01227nas a2200121 4500008004100000245006200041210005800103260001100161300001200172520081200184100001700996856009201013 2020 eng d00aThe impossibility of efficient quantum weak coin flipping0 aimpossibility of efficient quantum weak coin flipping c6/2020 a916-9293 a
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/√є )) 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.
1 aMiller, Carl uhttps://quics.umd.edu/publications/impossibility-efficient-quantum-weak-coin-flipping-0