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: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

47 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
Title of host publication	Proceedings of the 33rd annual ACM symposium on theory of computing
Publisher	Association for Computing Machinery (ACM)
Pages	134-142
Number of pages	9
ISBN (Print)	9781581133493
DOIs	https://doi.org/10.1145/380752.380788
Publication status	Published - 2001
Externally published	Yes
Event	33rd Annual ACM Symposium on Theory of Computing, STOC 2001 - Creta, Greece Duration: 6 Jul 2001 → 8 Jul 2001

Publication series

Name	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0734-9025

Conference

Conference	33rd Annual ACM Symposium on Theory of Computing, STOC 2001
Country/Territory	Greece
City	Creta
Period	6/07/01 → 8/07/01

Access to Document

10.1145/380752.380788

Cite this

@inproceedings{a71cc0a0cc7849b696130e4e6bfcf535,

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",

isbn = "9781581133493",

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

publisher = "Association for Computing Machinery (ACM)",

pages = "134--142",

booktitle = "Proceedings of the 33rd annual ACM symposium on theory of computing",

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

}

Ambainis, A 2001, A new protocol and lower bounds for quantum coin flipping. in Proceedings of the 33rd annual ACM symposium on theory of computing. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), pp. 134-142, 33rd Annual ACM Symposium on Theory of Computing, STOC 2001, Creta, Greece, 6/07/01. https://doi.org/10.1145/380752.380788

A new protocol and lower bounds for quantum coin flipping. / Ambainis, A.
Proceedings of the 33rd annual ACM symposium on theory of computing. Association for Computing Machinery (ACM), 2001. p. 134-142 (Conference Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

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 paper

AN - SCOPUS:0034826544

SN - 9781581133493

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

SP - 134

EP - 142

BT - Proceedings of the 33rd annual ACM symposium on theory of computing

PB - Association for Computing Machinery (ACM)

T2 - 33rd Annual ACM Symposium on Theory of Computing, STOC 2001

Y2 - 6 July 2001 through 8 July 2001

ER -

A new protocol and lower bounds for quantum coin flipping

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this