Pith. sign in

REVIEW 4 major objections 5 minor 43 references

Quantum Communication Advantage for Leader Election and Agreement

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Quantum communication gives a polynomial message-complexity advantage for leader election and agreement by letting a node address a coherent superposition of recipients.

desk verdict The complete-graph and agreement results are plausible and worth a serious look, but the diameter-2 protocol has a load-bearing gap on low-degree nodes that breaks the paper's headline claim. read the letter →

arxiv 2502.07416 v1 pith:A4N6KQL6 submitted 2025-02-11 cs.DC cs.DSquant-ph

Fabien Dufoulon , Frédéric Magniez , Gopal Pandurangan This is my paper · ORCID
classification cs.DCcs.DSquant-ph MSC 68W1568Q12
keywords quantumdistributedcomputingmessagecomplexityleaderelectionagreementGroversearchwalksCONGESTmodelnon-obliviouscommunication
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that quantum communication can break the message-complexity barriers that classical distributed algorithms hit for leader election and agreement. It introduces a model where a node may place the identity of the message recipient in a quantum superposition, and charges message complexity by the maximum over branches of the superposition. Within that model it presents protocols whose message counts drop polynomially below the tight classical bounds: $\tilde{O}(n^{1/3})$ for complete networks versus the classical $\tilde{\Omega}(\sqrt{n})$, $\tilde{O}(n^{2/3})$ for diameter-2 networks versus $\Theta(n)$, and $\tilde{O}(n^{1/5})$ expected for implicit agreement with shared randomness versus the best-known classical $\tilde{O}(n^{2/5})$. If the model is physically realizable, the same quantum search subroutines that speed up sequential computation would give distributed systems a genuine communication savings, not just faster rounds.

What carries the argument

The enabling object is the paper's new model of non-oblivious quantum routing: a node can prepare its emission register in a superposition of ports, so that one $O(\log n)$-qubit message queries several potential recipients coherently, and the round's message complexity is the maximum over branches of the superposition. On top of this model, the arguments are carried by distributed adaptations of three sequential quantum subroutines: Grover search, giving a quadratic speedup for finding a marked element; quantum approximate counting, giving a quadratic speedup for estimating a count; and search via quantum walks, used in the diameter-2 protocol to find a size-$k$ referee set inside a node's neighborhood and maintained through Setup, Update, and Checking procedures. The protocol designer's lever is a parameter $k$ that balances a classical phase contacting $k$ nodes against a quantum phase searching over $n/k$ candidates, which yields the optimized exponents $n^{1/3}$, $n^{2/3}$, and $n^{1/5}$.

What would settle it

Exhibit a concrete implementation of the superposition-of-recipients primitive and measure whether its physical cost scales with the number of branches; if the cost is, say, linear in the number of superposed recipients, the model's message accounting undercounts and the stated advantages disappear. Alternatively, run the diameter-2 protocol on a star graph with $n$ leaves: a leaf has degree 1, so the Johnson graph $J(\deg(v), n^{2/3})$ used by the quantum walk is empty, and the claimed $\tilde{O}(n^{2/3})$ bound would need a different argument to hold on that graph.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a framework for designing distributed algorithms whose message cost, not round cost, is the object being optimized quantumly. The load-bearing results are upper bounds: Corollary 5.3 gives leader election in complete networks with $\tilde{O}(n^{1/3})$ messages with high probability; Corollary 5.7 gives $\tilde{O}(n^{2/3})$ messages for diameter-2 networks; and Corollary 6.8 gives implicit agreement in complete networks with shared randomness using $\tilde{O}(n^{1/5})$ expected messages. Each beats the corresponding tight classical bound, and all are achieved by distributing Grover search, quantum counting, and, in the diameter-2 case, a quantum walk on a local Johnson graph of size-$k$ referee sets.

Load-bearing premise

The load-bearing premise is that a node can send a single $O(\log n)$-qubit message into a coherent superposition of recipients at no extra cost beyond the message itself; if that primitive cannot be implemented at that cost, the claimed quantum advantages over the classical lower bounds collapse.

Editorial extensions

If this is right

  • Leader election in complete networks can be solved with high probability using $\tilde{O}(n^{1/3})$ messages, and even at sub-$n^{1/3}$ round counts the message complexity remains below the classical $\tilde{\Omega}(\sqrt{n})$ barrier.
  • For diameter-2 networks, leader election needs $\tilde{O}(n^{2/3})$ messages, breaking the classical $\Theta(n)$ bound; this is, to the authors' knowledge, the first distributed application of quantum walks.
  • Implicit agreement in complete networks with shared randomness can be solved in $\tilde{O}(n^{1/5})$ expected messages, a quadratic improvement over the best classical $\tilde{O}(n^{2/5})$.
  • For arbitrary $m$-edge, $n$-node graphs, leader election can be done with $\tilde{O}(\sqrt{mn})$ messages, beating the classical $\Omega(m)$ bound whenever $m$ is large; the same Grover-based edge-finding technique adapts to minimum spanning tree.
  • The round-message tradeoff is tunable through the parameter $k$, so one can spend more rounds to lower the message count while still staying below the classical communication floor.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the same birthday-paradox-to-collision-finding speedup should apply to other symmetry-breaking and sampling-based distributed problems, not only leader election and agreement.
  • A natural test is whether the coherent-recipient primitive can be realized in physical hardware, such as a single photon routed in superposition through an optical switch; if real implementations only support incoherent mixtures, the message-complexity advantages would need to be re-examined.
  • The diameter-2 protocol's quantum walk requires each candidate to have at least $k=\Theta(n^{2/3})$ neighbors, so on star-like diameter-2 graphs, such as a plain star, the stated $\tilde{O}(n^{2/3})$ bound does not follow from the given argument without a more refined parameter choice or a different search structure.
  • The quadratic improvements mirror sequential query-complexity gains, suggesting that quantum message-complexity lower bounds might be provable by adapting quantum query lower bounds—a direction the authors explicitly leave open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper introduces a non-oblivious quantum message-passing model in which a node can place the recipient of an O(log n)-qubit message in a coherent superposition, with message complexity charged as the maximum over branches. Using distributed Grover search, approximate quantum counting, and a distributed search-via-quantum-walk subroutine, it presents leader election algorithms for complete graphs (O~(n^{1/3}) messages), for graphs with small mixing time, for diameter-2 networks (claimed O~(n^{2/3}) messages), and for general graphs (O~(sqrt{mn}) messages), plus an implicit agreement algorithm for complete networks with shared randomness (O~(n^{1/5}) expected messages). The results are compared against classical lower bounds from [KPP+15a], [KPP+15b], [CPR20], and [AMP18].

Significance. If correct, the paper would make a substantial conceptual advance: it is one of the first systematic treatments of message complexity in a quantum distributed setting, and the claimed asymptotic separations (n^{1/3} vs sqrt n for complete-graph leader election, n^{1/5} vs n^{2/5} for agreement) are significant. The complete-graph and agreement analyses are internally coherent, and the complexity comparisons use published classical lower bounds rather than bounds derived inside the paper, so I do not see a circularity problem. The decentralized-checking idea and the first distributed use of quantum walks for message complexity are also genuinely novel. However, the diameter-2 result, which is the most technically distinctive contribution, is not valid as stated, and the physical status of the new routing model needs a clearer justification; these issues are detailed below.

major comments (4)
  1. [Section 5.3, Algorithm 3 (line 4), Theorem 5.6] Algorithm 3, line 4, runs WalkSearch on the Johnson graph J(deg(v), k) with epsilon = k/deg(v). This is only defined when deg(v) >= k, since otherwise J has no vertices and epsilon > 1. Theorem 5.6 states the result for all diameter-2 networks, but a star graph has diameter 2 and leaves with deg(v)=1, while k = Theta(n^{2/3}); hence the algorithm cannot be executed on stars. The case is not a harmless boundary: if k is locally set to 1 for a leaf, the active leaf's referee set W can only be {center}, and the decentralized Checking step of a passive higher-ranked center sends the center's rank to the leaf rather than depositing it at the center, so the centralized step (line 9) finds no contradiction. Consequently multiple active leaves remain candidates and are elected, with probability that can exceed the allowed 1/n failure probability. Corollary 5.7 is therefore not established for all diameter-2 networks; the statement must be restricted (e.g., to graphs of minimum degree at least k) or the protocol must be redesigned.
  2. [Section 5.3.2, proof of Theorem 5.6] The complexity analysis in Theorem 5.6 uses epsilon = k/n and delta = 1/k, while Algorithm 3 line 4 uses epsilon = k/deg(v). These agree only when deg(v) = Theta(n). For a diameter-2 graph whose vertices have smaller degree, the Johnson graph parameters, the spectral gap, and the resulting message complexity must be re-derived; as written, the proof covers only high-degree nodes and leaves the claimed O~(k + n/sqrt{k}) bound unsupported for the stated domain.
  3. [Section 3.1 and Appendix A.1] The model's central accounting rule needs a physical or operational justification. A round in which several recipients appear in superposition is counted as carrying at most the maximum number of messages over branches, and all the upper bounds exploit this convention, for example in the Setup operation of Algorithm 3 line 5, which sends a rank to a superposition of k-subsets at cost O~(k). The formal register model in Appendix A.1 defines the operations but not their implementation cost. Since the claimed advantages are measured against classical CONGEST lower bounds that count point-to-point messages, the authors should either argue that superposed routing can be implemented with no additional resource overhead, or identify the concrete physical scenario in which this cost convention is valid.
  4. [Section 5.3, Algorithm 3, lines 7-9] The decentralized Checking step is underspecified. It is not stated whether every passive candidate runs its GroverSearch once per outer iteration or once per invocation of Checking by an active candidate, nor how the two phases of Checking are synchronized so that the centralized step observes the higher ranks sent in the decentralized step. Since the claimed MC = O~(sqrt n) in Theorem 5.6 depends on the number and cost of these executions, this gap makes the diameter-2 message bound unverifiable as written.
minor comments (5)
  1. [Section 4.3, Theorem 4.1] The statement says GroverSearch returns some x in X, but Algorithms 1, 3, and 4 use the result to conclude 'no solution' when epsilon_f = 0. Please specify that the returned element is verified and a distinguished 'none' output is produced; otherwise the decision rules are not well-defined in the zero-solution case.
  2. [Section 5.3.1] The sentence 'Run WalkSearch(P_v, delta, epsilon, alpha) (Theorem 5.2)' should refer to Theorem 4.4, not Theorem 5.2.
  3. [Section 5.1.2, proof of Fact 5.1] In the proof of Fact 5.1, 'By Theorem 5.1' should be 'By Fact 5.1'.
  4. [Section 6.1 and Algorithm 4] The termination behavior is not fully explicit when all candidates become decided in an iteration: the pseudocode only lets undecided nodes exit the loop, but line 13 claims all candidate nodes know the deciding value. Please clarify how non-candidate nodes terminate and how candidate nodes stop when no undecided node runs the Grover search.
  5. [Throughout] The text contains numerous OCR-type artifacts (for example, 'th at', 'Gro ver', 'first'); these should be cleaned up before a final version is submitted.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the quantum algorithms are derived from standard external quantum subroutines and benchmarked against independent external classical lower bounds; no parameter is fitted to the target result.

full rationale

The load-bearing claims are upper bounds for leader election and agreement in a newly introduced model of non-oblivious quantum CONGEST. The derivation chain is explicit: define the message-complexity accounting; prove distributed Grover search, quantum counting, and quantum-walk search from standard quantum algorithms; compose these into the leader-election and agreement protocols; and compare the resulting message bounds against external classical lower and upper bounds. The classical bounds from [KPP+15a, KPP+15b, CPR20, AMP18] are cited as published external results, not derived inside this paper; although some of those works share an author with the present paper, they are peer-reviewed, parameter-free, and do not depend on the present algorithms, so under the review rules they count as independent support and do not create circularity. The quantum-walk framework is imported from [MNRS11], an external standard result, and Theorem 4.4 explicitly refers to it for the phase-estimation step; this is a real external citation, not a self-citation chain. The model assumption that a message can be routed to a superposition of recipients while charging only the branch-wise maximum is a stipulated modelling choice, not a conclusion derived from itself; the protocols are proven within that model. I found no parameter fitted to the target message bound, no uniqueness theorem imported from the authors, and no renaming of a known result as a new framework. The main risks of the paper are physical validity of the routing model and a possible correctness gap in the diameter-2 protocol on star graphs, where Algorithm 3 requires deg(v) >= k; those are correctness and modeling concerns, not circularity.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

No new physical entities are introduced; the superposition-of-trajectories routing is a model choice, not an entity. The main dependencies are the model assumptions and the cited quantum subroutine bounds.

free parameters (4)
  • k (subset / referee count) = Theta(n^{1/3}) in Cor 5.3; Theta(tau^{2/3} n^{1/3}) in Cor 5.5; Theta(n^{2/3}) in Cor 5.7
    Chosen by the authors to optimize the message complexity expression in each protocol; the central complexity bounds depend on this choice.
  • candidate probability p = 12 ln n / n
    Hand-chosen constant to get O(log n) candidates with high probability while keeping message overhead low.
  • rank range size = n^4
    Chosen large enough so that all candidate ranks are unique with high probability; any polynomial n^{2+Omega(1)} would suffice.
  • agreement tuning parameters epsilon and gamma = epsilon = 1/n^{1/5}, gamma = 2/15
    Chosen to balance estimation cost O(1/epsilon), classical message cost O(n^{1/3-gamma}), and quantum detection cost O(epsilon n^{1/3+gamma/2}); yields the claimed O~(n^{1/5}) expected message bound.
assumptions (7)
  • domain assumption The CONGEST model assumptions: synchronous rounds, O(log n)-bit messages per edge per round, KT0 clean network, nodes know n, private random bits, and shared randomness only in Section 6.
    Section 2.1 defines the model; all lower bounds and protocol analyses are relative to it.
  • ad hoc to paper Non-oblivious quantum routing is a valid quantum extension of CONGEST, with coherent superpositions of recipients and message complexity equal to the maximum over branches.
    Introduced in Section 3.1 and Appendix A.1; no prior validation or physical implementation is given, and the claimed quantum advantage depends on this accounting.
  • domain assumption Any randomized or quantum distributed algorithm with intermediate measurements can be simulated by a unitary algorithm with the same round and message complexities.
    Lemma 3.1 and Appendix B.1 give a purification argument; this is needed to make Grover and quantum walk subroutines reversible.
  • standard math Standard quantum subroutine complexity bounds hold in the distributed setting: Grover search (BBHT98), quantum counting (BHT98a), and search via quantum walks (MNRS11).
    Section 4 states these as theorems and adapts them to distributed Checking; correctness relies on the sequential bounds.
  • standard math The classical message lower bounds in [KPP+15a, KPP+15b, CPR20, AMP18] are correct.
    These are external published results used as the benchmark for quantum advantage.
  • domain assumption The graph mixing time tau is known to the nodes, and the random walk analysis uses a standard mixing-time definition.
    Section 5.2 explicitly assumes knowledge of tau; the paper does not formally define tau.
  • ad hoc to paper Every candidate node in the diameter-two protocol has degree at least k = Theta(n^{2/3}), so the Johnson graph J(deg(v),k) is nonempty and the quantum walk is defined.
    Unstated assumption in Section 5.3; false for star networks, where leaf nodes have degree 1, so the protocol as written is undefined for such nodes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Communication Advantage for Leader Election and Agreement." pith.science (2026). https://pith.science/paper/A4N6KQL6

@misc{pith2026250207416,
  author       = {Pith},
  title        = {Pith review of: Quantum Communication Advantage for Leader Election and Agreement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A4N6KQL6}},
  note         = {Machine review of arXiv:2502.07416}
}
read the original abstract

This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies. While prior works have studied and analyzed quantum distributed algorithms in the context of (improving) round complexity, a key conceptual contribution of our work is positing a framework to design and analyze the message complexity of quantum distributed algorithms. We present and show how quantum algorithmic techniques such as Grover search, quantum counting, and quantum walks can make distributed algorithms significantly message-efficient. In particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity. To the best of our knowledge, this is the first such application of quantum walks in distributed computing.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 38 canonical work pages

  1. [1]

    Addressable quantum gates

    Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse R\' e mond, and Beno\^ t Valiron. Addressable quantum gates. ACM Transactions on Quantum Computing , 4(3), apr 2023

    work page 2023

  2. [2]

    Scalable and secure computation among strangers: Message-competitive byzantine protocols

    John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and secure computation among strangers: Message-competitive byzantine protocols. In 34th International Symposium on Distributed Computing (DISC) , volume 179 of LIPIcs , pages 31:1--31:19, 2020

    work page 2020

  3. [3]

    Quantum walk algorithm for element distinctness

    Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing , 37(1):210--239, 2007

    work page 2007

  4. [4]

    Sublinear message bounds for randomized agreement

    John Augustine, Anisur Rahaman Molla, and Gopal Pandurangan. Sublinear message bounds for randomized agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) , page 315–324, 2018

    work page 2018

  5. [5]

    Distributed quantum advantage for local problems

    Alkida Balliu, Sebastian Brandt, Xavier Coiteux - Roy, Francesco D'Amore, Massimo Equi, Fran c ois Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc - Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. Distributed quantum advantage for local problems. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STO...

    arXiv 2025

  6. [6]

    Tight bounds on quantum searching

    Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik , 46(4–5):493–505, June 1998. arXiv:quant-ph/9605034

    arXiv 1998

  7. [7]

    Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing , 18(4):766--776, 1989

    work page 1989

  8. [8]

    Quantum counting

    Gilles Brassard, Peter H yer, and Alain Tapp. Quantum counting. In 25th International Colloquium on Automata, Languages and Programming (ICALP) , volume 1443 of Lecture Notes in Computer Science , pages 820--831. Springer, 1998

    work page 1998

Show all 43 references
  1. [9]

    Quantum cryptanalysis of hash and claw-free functions

    Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In Latin American Symposium on Theoretical Informatics (LATIN) , pages 163--169, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg

    1998

  2. [10]

    No distributed quantum advantage for approximate graph coloring

    Xavier Coiteux - Roy, Francesco D'Amore, Rishikesh Gajjala, Fabian Kuhn, Fran c ois Le Gall, Henrik Lievonen, Augusto Modanese, Marc - Olivier Renou, Gustav Schmid, and Jukka Suomela. No distributed quantum advantage for approximate graph coloring. In Proceedings of the 56th A...

    1901

  3. [11]

    Quantum distributed algorithms for detection of cliques

    Keren Censor - Hillel, Orr Fischer, Fran c ois Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum distributed algorithms for detection of cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS) , volume 215 of LIPIcs , pages 35:1--35:25, 2022

    2022

  4. [12]

    Quantum shannon theory with superpositions of trajectories

    Giulio Chiribella and Hlér Kristjánsson. Quantum shannon theory with superpositions of trajectories. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 475(2225):20180903, May 2019

    2019

  5. [13]

    The complexity of leader election in diameter-two networks

    Soumyottam Chatterjee, Gopal Pandurangan, and Peter Robinson. The complexity of leader election in diameter-two networks. Distributed Comput. , 33(2):189--205, 2020

    2020

  6. [14]

    Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

    R Cole and U Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC) , page 206–219. ACM, 1986

    1986

  7. [15]

    Quantum query complexity of some graph problems

    Christoph D \" u rr, Mark Heiligman, Peter H yer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM J. Comput. , 35(6):1310--1328, 2006

    2006

  8. [16]

    Denchev and Gopal Pandurangan

    Vasil S. Denchev and Gopal Pandurangan. Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News , 39(3):77--95, 2008

    2008

  9. [17]

    Pemmaraju, and Peter Robinson

    Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson. The message complexity of distributed graph optimization. In 15th Innovations in Theoretical Computer Science Conference (ITCS) , volume 287 of LIPIcs , pages 41:1--41:26, 2024

    2024

  10. [18]

    Can quantum communication speed up distributed computation? In ACM Symposium on Principles of Distributed Computing (PODC) , pages 166--175

    Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In ACM Symposium on Principles of Distributed Computing (PODC) , pages 166--175. ACM , 2014

    2014

  11. [19]

    Even-cycle detection in the randomized and quantum CONGEST model

    Pierre Fraigniaud, Ma \" e l Luce, Fr \' e d \' e ric Magniez, and Ioan Todinca. Even-cycle detection in the randomized and quantum CONGEST model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC) , pages 209--219. ACM , 2024

    2024

  12. [20]

    Gallager, Pierre A

    Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. , 5(1):66--77, 1983

    1983

  13. [21]

    What can be observed locally? In Distributed Computing, 23rd International Symposium (DISC) , volume 5805 of Lecture Notes in Computer Science , pages 243--257

    Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In Distributed Computing, 23rd International Symposium (DISC) , volume 5805 of Lecture Notes in Computer Science , pages 243--257. Springer, 2009. We refer to the full version in arXiv:0903.1133

    2009 arXiv

  14. [22]

    Sublinear-time quantum computation of the diameter in CONGEST networks

    Fran c ois Le Gall and Fr \' e d \' e ric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC) , pages 337--346. ACM , 2018

    2018

  15. [23]

    Quantum advantage for the LOCAL model in distributed computing

    Fran c ois Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS) , volume 126 of LIPIcs , pages 49:1--49:14, 2019

    2019

  16. [24]

    Eliminating intermediate measurements using pseudorandom generators

    Uma Girish and Ran Raz. Eliminating intermediate measurements using pseudorandom generators. In 13th Innovations in Theoretical Computer Science Conference (ITCS) , volume 215 of LIPIcs , pages 76:1--76:18, 2022

    2022

  17. [25]

    Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC) , pages 212--219. ACM , 1996

    1996

  18. [26]

    Bounds on oblivious multiparty quantum communication complexity

    Fran c ois Le Gall and Daiki Suruga. Bounds on oblivious multiparty quantum communication complexity. In 15th Latin American Symposium on Theoretical Informatics (LATIN) , volume 13568 of Lecture Notes in Computer Science , pages 641--657. Springer, 2022

    2022

  19. [27]

    Vassos Hadzilacos and Joseph Y. Halpern. Message-optimal protocols for byzantine agreement. Math. Syst. Theory , 26(1):41--102, 1993

    1993

  20. [28]

    Hegeman, Gopal Pandurangan, Sriram V

    James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST . In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) , pages 91...

    2015

  21. [29]

    On the complexity of universal leader election

    Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On the complexity of universal leader election. J. ACM , 62(1):7:1--7:27, 2015

    2015

  22. [30]

    Sublinear bounds for randomized leader election

    Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. Sublinear bounds for randomized leader election. Theoretical Computer Science , 561:134--143, 2015

    2015

  23. [31]

    Nancy A. Lynch. Distributed Algorithms . Morgan Kaufmann, 1996

    1996

  24. [32]

    Search via quantum walk

    Fr\' e d\' e ric Magniez, Ashwin Nayak, J\' e r\' e mie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing , 40(1):142--164, 2011

    2011

  25. [33]

    Probability and Computing: Randomized Algorithms and Probabilistic Analysis

    Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press, Cambridge CB2 8BS, United Kingdom, 2^ nd edition, 2017

    2017

  26. [34]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition . Cambridge University Press, 2010

    2010

  27. [35]

    Time-optimal leader election in general networks

    David Peleg. Time-optimal leader election in general networks. J. Parallel Distributed Comput. , 8(1):96--99, 1990

    1990

  28. [36]

    Distributed computing: a locality-sensitive approach

    David Peleg. Distributed computing: a locality-sensitive approach . Society for Industrial and Applied Mathematics, USA, 2000

    2000

  29. [37]

    Pemmaraju, and Peter Robinson

    Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson. Can we break symmetry with o(m) communication? In ACM Symposium on Principles of Distributed Computing (PODC) , pages 247--257. ACM , 2021

    2021

  30. [38]

    Message lower bounds via efficient network synchronization

    Gopal Pandurangan, David Peleg, and Michele Scquizzato. Message lower bounds via efficient network synchronization. Theor. Comput. Sci. , 810:82--95, 2020

    2020

  31. [39]

    Reed and Jack J

    Daniel A. Reed and Jack J. Dongarra. Exascale computing and big data. Commun. ACM , 58(7):56--68, 2015

    2015

  32. [40]

    Design and analysis of distributed algorithms

    Nicola Santoro. Design and analysis of distributed algorithms . Wiley series on parallel and distributed computing. Wiley, 2007

    2007

  33. [41]

    Introduction to Distributed Algorithms

    Gerard Tel. Introduction to Distributed Algorithms . Cambridge University Press, 2 edition, 2000

    2000

  34. [42]

    A framework for distributed quantum queries in the CONGEST model

    Joran van Apeldoorn and Tijn de Vos. A framework for distributed quantum queries in the CONGEST model. In ACM Symposium on Principles of Distributed Computing (PODC) , pages 109--119. ACM , 2022

    2022

  35. [43]

    Routed quantum circuits

    Augustin Vanrietvelde, Hl \' e r Kristj \' a nsson, and Jonathan Barrett. Routed quantum circuits. Quantum , 5:503, July 2021

    2021

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.