Scalable quantum consensus for crash failures

Bogdan S. Chlebus; Dariusz R. Kowalski; Michał Strojnowski

doi:10.1007/978-3-642-15763-9_24

Scalable quantum consensus for crash failures

Bogdan S. Chlebus, Dariusz R. Kowalski, Michał Strojnowski

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

We present a scalable quantum algorithm to solve binary consensus in a system of n crash-prone quantum processes. The algorithm works in O(polylog n) time sending O(n polylog n) qubits against the adaptive adversary. The time performance of this algorithm is asymptotically better than a lower bound Ω(√n/log n) on time of classical randomized algorithms against adaptive adversaries. Known classical randomized algorithms having each process send O(polylog n) messages work only for oblivious adversaries. Our quantum algorithm has a better time performance than deterministic solutions, which have to work in Ω(t) time for t < n failures.

Original language	English (US)
Title of host publication	Distributed Computing - 24th International Symposium, DISC 2010, Proceedings
Pages	236-250
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-15763-9_24
State	Published - Dec 13 2010
Externally published	Yes
Event	24th International Symposium on Distributed Computing, DISC 2010 - Cambridge, MA, United States Duration: Sep 13 2010 → Sep 15 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6343 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Symposium on Distributed Computing, DISC 2010
Country/Territory	United States
City	Cambridge, MA
Period	9/13/10 → 9/15/10

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-15763-9_24

Cite this

Chlebus, B. S., Kowalski, D. R., & Strojnowski, M. (2010). Scalable quantum consensus for crash failures. In Distributed Computing - 24th International Symposium, DISC 2010, Proceedings (pp. 236-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6343 LNCS). https://doi.org/10.1007/978-3-642-15763-9_24

Scalable quantum consensus for crash failures. / Chlebus, Bogdan S.; Kowalski, Dariusz R.; Strojnowski, Michał.
Distributed Computing - 24th International Symposium, DISC 2010, Proceedings. 2010. p. 236-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6343 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chlebus, BS , Kowalski, DR & Strojnowski, M 2010, Scalable quantum consensus for crash failures. in Distributed Computing - 24th International Symposium, DISC 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6343 LNCS, pp. 236-250, 24th International Symposium on Distributed Computing, DISC 2010, Cambridge, MA, United States, 9/13/10. https://doi.org/10.1007/978-3-642-15763-9_24

@inproceedings{04eab91f314d48cbaa02fc5b6d30d5fe,

title = "Scalable quantum consensus for crash failures",

abstract = "We present a scalable quantum algorithm to solve binary consensus in a system of n crash-prone quantum processes. The algorithm works in O(polylog n) time sending O(n polylog n) qubits against the adaptive adversary. The time performance of this algorithm is asymptotically better than a lower bound Ω(√n/log n) on time of classical randomized algorithms against adaptive adversaries. Known classical randomized algorithms having each process send O(polylog n) messages work only for oblivious adversaries. Our quantum algorithm has a better time performance than deterministic solutions, which have to work in Ω(t) time for t < n failures.",

author = "Chlebus, {Bogdan S.} and Kowalski, {Dariusz R.} and Micha{\l} Strojnowski",

year = "2010",

month = dec,

day = "13",

doi = "10.1007/978-3-642-15763-9_24",

language = "English (US)",

isbn = "3642157629",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "236--250",

booktitle = "Distributed Computing - 24th International Symposium, DISC 2010, Proceedings",

note = "24th International Symposium on Distributed Computing, DISC 2010 ; Conference date: 13-09-2010 Through 15-09-2010",

}

TY - GEN

T1 - Scalable quantum consensus for crash failures

AU - Chlebus, Bogdan S.

AU - Kowalski, Dariusz R.

AU - Strojnowski, Michał

PY - 2010/12/13

Y1 - 2010/12/13

N2 - We present a scalable quantum algorithm to solve binary consensus in a system of n crash-prone quantum processes. The algorithm works in O(polylog n) time sending O(n polylog n) qubits against the adaptive adversary. The time performance of this algorithm is asymptotically better than a lower bound Ω(√n/log n) on time of classical randomized algorithms against adaptive adversaries. Known classical randomized algorithms having each process send O(polylog n) messages work only for oblivious adversaries. Our quantum algorithm has a better time performance than deterministic solutions, which have to work in Ω(t) time for t < n failures.

AB - We present a scalable quantum algorithm to solve binary consensus in a system of n crash-prone quantum processes. The algorithm works in O(polylog n) time sending O(n polylog n) qubits against the adaptive adversary. The time performance of this algorithm is asymptotically better than a lower bound Ω(√n/log n) on time of classical randomized algorithms against adaptive adversaries. Known classical randomized algorithms having each process send O(polylog n) messages work only for oblivious adversaries. Our quantum algorithm has a better time performance than deterministic solutions, which have to work in Ω(t) time for t < n failures.

UR - http://www.scopus.com/inward/record.url?scp=78649814410&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649814410&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15763-9_24

DO - 10.1007/978-3-642-15763-9_24

M3 - Conference contribution

AN - SCOPUS:78649814410

SN - 3642157629

SN - 9783642157622

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 236

EP - 250

BT - Distributed Computing - 24th International Symposium, DISC 2010, Proceedings

T2 - 24th International Symposium on Distributed Computing, DISC 2010

Y2 - 13 September 2010 through 15 September 2010

ER -

Scalable quantum consensus for crash failures

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this