A new protocol and lower bounds for quantum coin flipping

A. Ambainis

doi:10.1145/380752.380788

A new protocol and lower bounds for quantum coin flipping

A. Ambainis^*

^*Corresponding author for this work

University of California at Berkeley

Research output: Contribution to journal › Conference article › peer-review

46 Citations (Scopus)

Abstract

We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols. For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most ε, it must use at least Ω(log log 1/ε) rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel).

Original language	English
Pages (from-to)	134-142
Number of pages	9
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/380752.380788
Publication status	Published - 2001
Externally published	Yes
Event	33rd Annual ACM Symposium on Theory of Computing - Creta, Greece Duration: 6 Jul 2001 → 8 Jul 2001

Access to Document

10.1145/380752.380788

Cite this

@article{73e845d2eb97474b93080e525f360fa3,

title = "A new protocol and lower bounds for quantum coin flipping",

abstract = "We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols. For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most ε, it must use at least Ω(log log 1/ε) rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel).",

author = "A. Ambainis",

year = "2001",

doi = "10.1145/380752.380788",

language = "English",

pages = "134--142",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery ",

note = "33rd Annual ACM Symposium on Theory of Computing ; Conference date: 06-07-2001 Through 08-07-2001",

}

TY - JOUR

T1 - A new protocol and lower bounds for quantum coin flipping

AU - Ambainis, A.

PY - 2001

Y1 - 2001

N2 - We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols. For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most ε, it must use at least Ω(log log 1/ε) rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel).

AB - We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols. For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most ε, it must use at least Ω(log log 1/ε) rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel).

UR - https://www.scopus.com/pages/publications/0034826544

U2 - 10.1145/380752.380788

DO - 10.1145/380752.380788

M3 - Conference article

AN - SCOPUS:0034826544

SN - 0734-9025

SP - 134

EP - 142

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 33rd Annual ACM Symposium on Theory of Computing

Y2 - 6 July 2001 through 8 July 2001

ER -

A new protocol and lower bounds for quantum coin flipping

Abstract

Access to Document

Other files and links

Fingerprint

Cite this