Pith. sign in

REVIEW 1 major objections 4 minor 40 references

Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries

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

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

Pith's one-line read Quantum communication can replace public randomness in multi-party simultaneous protocols, via a compiler that turns equality-query decision trees into private-coin quantum protocols.

desk verdict First multi-player positive results for quantum SMP without public coins; the main compiler is sound and the applications are real, though one lemma's proof is omitted and one depth expression has a harmless typo. read the letter →

arxiv 2412.08091 v1 pith:TJB6A6O2 submitted 2024-12-11 quant-ph cs.DC

François Le Gall , Oran Nadler , Harumichi Nishimura , Rotem Oshman This is my paper · ORCID
classification quant-phcs.DC MSC 68Q12
keywords SMPmodelquantumcommunicationcomplexitypublicrandomnessmodifiedequalityqueriesfingerprintingneighborhooddiversitydistance-hereditarygraphsisolatedcliques
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

The paper shows that quantum communication can replace public randomness in the multi-party simultaneous message-passing model, without entanglement, for any number of players; previously this was known only for two players, and for three players a negative result was known. The main technical contribution is a compiler that takes any classical public-coin protocol expressed as a decision tree of modified equality queries and converts it into a quantum protocol with no public coins, using only $O(k(\log D + \log(1/\delta))\log n)$ qubits for depth $D$ and error $\delta$. The authors apply the compiler to obtain efficient private-coin quantum protocols for frequency moments, neighborhood diversity, enumeration of isolated cliques, and reconstruction of distance-hereditary graphs. If correct, these are the first multi-player problems for which quantum communication replaces public randomness, and their communication cost matches classical public-coin protocols while improving exponentially over classical private-coin protocols.

What carries the argument

The load-bearing object is the linear quantum fingerprint family: states $|\Psi_x\rangle$ of $O(\log n)$ qubits whose inner products are small for distinct strings and for which $|\Psi_{x\oplus y}\rangle$ is obtained from $|\Psi_x\rangle$ by a known unitary. The SWAP test turns these fingerprints into a measurement that detects inequality; converting the test to a projective measurement and amplifying its success probability makes it gentle enough to be applied sequentially to the same stored messages. The quantum union bound then controls the total error over all queries, so the communication cost grows with the logarithm of the decision-tree depth rather than with the depth itself.

What would settle it

Run a computer search over all small graphs and the initial representation $\{(e_v,\nu_v)\}$: if any application of update rules (I), (II), or (III) yields $a'$ vectors that are linearly dependent over $\mathbb{F}_2$, or a $b'_v$ that differs from the neighbor-sum computed from the updated graph, then Lemma 14 is false and Theorem 16's reconstruction protocol fails on that instance.

Watch

Extended reading notes

Core claim

The central claim is that a referee who holds quantum fingerprints of all players' inputs can answer many modified equality queries of the form 'is $x_i \oplus y = x_j \oplus z$?' on the same stored fingerprints, one after another, without destroying them. Each player sends $O(\log(1/\varepsilon))$ copies of a linear quantum fingerprint of its input, and the referee uses the linearity of the fingerprint family to transform a player's fingerprint into the fingerprint of $x_i \oplus y$ whenever $y$ is known. Each query is implemented as a projective SWAP-style measurement whose success probability is amplified to $1-\delta/(4D)$; because these measurements are 'gentle' when their outcomes are nearly certain, the quantum union bound guarantees that after $D$ sequential queries the accumulated disturbance is small. This yields Theorem 2: any $MEQ_{k,n}$ decision tree of depth $D$ can be implemented by a $k$-party quantum SMP protocol with $O(k(\log D+\log(1/\delta))\log n)$ qubits, error at most $\delta$, and no public randomness.

Load-bearing premise

The protocol for reconstructing distance-hereditary graphs assumes that the update rules of Lemma 14 always preserve the validity of the vector representation after removing a pendant or twin node; the paper omits the proof of this lemma, saying it is similar to earlier work, and if the rules ever break linear independence the application fails.

Editorial extensions

If this is right

  • Grouping players by equal inputs, and therefore solving AllEQ, ExistsEQ, and all frequency moments, requires $O(k\log k\log n)$ qubits and no public randomness (Theorem 8).
  • Neighborhood diversity of a graph in the number-in-hand model is computable with $O(k\log^2 k)$ qubits (Theorem 10).
  • Distance-hereditary graphs can be reconstructed, or rejected if not distance-hereditary, with $O(k\log^2 k)$ qubits by simulating a pendant-twin decomposition (Theorem 16).
  • All max-$d$-isolated cliques can be enumerated with $O(kd\log^2 k)$ qubits (Theorem 20).
  • These costs match the best classical public-coin protocols and improve exponentially over classical private-coin protocols, whose lower bound is $\Omega(\sqrt{n})$ for two-party equality.

Reading between the lines

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

  • The compiler suggests a general recipe: any problem that admits a depth-$D$ MEQ decision tree inherits a private-coin quantum protocol with only $O(k\log D\log n)$ qubits, so the list of applications here is likely not exhaustive.
  • The linearity requirement limits the approach to queries in which the referee can adjust fingerprints by known modifier strings; extending the framework to non-linear queries such as unbounded Hamming distance would need a different fingerprint structure, and the paper notes that exact Hamming distance requires linear communication even with entanglement.
  • A natural follow-up is to check the omitted proof of Lemma 14 computationally: small random graphs and representations over $\mathbb{F}_2$ can be tested to see whether the update rules ever produce linearly dependent vectors.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper studies quantum multiparty simultaneous message-passing (SMP) protocols without public coins or entanglement. It introduces modified equality queries (MEQ) and a compiler (Theorem 2) that converts any MEQ decision tree of depth D into a quantum SMP protocol with O(k(log D + log(1/δ)) log n) qubits and error probability at most δ. The compiler combines linear quantum fingerprints, gentle projective measurements, and Gao's quantum union bound. The authors then apply the compiler to obtain polylogarithmic-qubit protocols for grouping by equality, frequency moments, P3-induced-subgraph freeness, neighborhood diversity, reconstruction of distance-hereditary graphs, and enumeration of max-d-isolated cliques, matching the communication cost of classical public-coin protocols for these problems.

Significance. If correct, this is the first demonstration that quantum communication can replace public randomness in the multi-party SMP model for natural problems, going beyond the two-party results of Buhrman et al. and Yao. The main theorem is proven carefully: Lemma 1's error analysis is sound, and the use of Gao's union bound with ε = δ/(4D) gives the claimed error. The applications are grounded in prior classical algorithms, and the compiler is applied directly with no free parameters or data fitting. The main gap is the omitted proof of Lemma 14, which is load-bearing for the distance-hereditary reconstruction application; I verified the lemma by checking the three update cases and it is correct, but a proof should be included so that the advertised application is fully justified. The paper should be publishable after the proof is added and minor typos are corrected.

major comments (1)
  1. [Section 4.3, Lemma 14] Lemma 14 is load-bearing for Theorem 16 (distance-hereditary reconstruction), but its proof is omitted with the note that it is 'very similar to [29,36]'. Since the representation here is over binary vectors rather than the polynomials used in [29,36], the translation is not literally the same argument. I checked the three update rules directly: in each case the new family remains linearly independent (a non-empty zero subset sum would pull back to a non-empty zero subset sum of the original family), and the update of b'_u exactly compensates for the removal of a_w. The lemma is correct, but a full proof or a precise derivation from [29,36] should be included in the paper so that the advertised application is not contingent on an unstated argument.
minor comments (4)
  1. [Section 4.4, proof of Theorem 20] The displayed depth expression is incorrect: MHAM^{2d}_k and MHAM^{2d+2}_k each require O(n^{2d}) and O(n^{2d+2}) MEQ queries respectively, not O(n^d) and O(n^{d+2}). The final communication bound O(kd log^2 k) is unchanged because the logarithm of either expression is O(d log k), but the equation should be corrected.
  2. [Section 3, Theorem 2] The theorem states D ≥ 0, but the proof and the bound use log D. For D = 0 the decision tree is a leaf and the communication is O(1); the statement should either require D ≥ 1 or handle D = 0 separately.
  3. [Section 4.3, Algorithm 2] Line 7 of Algorithm 2 reads '∃w,v' but the query and comment refer to u; it should be '∃w,u'.
  4. [Section 4.4, Definition 17] The term 'max-d-isolated clique' is defined only by the clique and degree-bound conditions. If maximality under inclusion is intended (as the word 'max' suggests), the protocol as described would output non-maximal cliques as well; the authors should clarify the definition or add a filtering step.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the compiler and applications rest on external primitives (quantum fingerprints, SWAP test, Gao's quantum union bound) and do not fit or rename the target results.

full rationale

The paper's central derivation chain is self-contained rather than circular. Lemma 1 implements a single modified equality query using linear quantum fingerprints from [18] and the SWAP test from [7,9]; these are external, machine-independent primitives, and the query's answer is computed from the fingerprints rather than assumed. Theorem 2 compiles MEQ decision trees by applying the Lemma 1 procedure as a sequence of projective measurements and bounding the accumulated error with Gao's quantum union bound (Theorem 4); the error parameter is set as ε = δ/(4D), and the algebraic factor of 4 in Gao's bound exactly yields the claimed δ. This is a direct quantitative reduction, not a renaming or a fitted-input prediction. The applications (GroupByEQ, neighborhood diversity, distance-hereditary reconstruction, isolated cliques) are all expressed as MEQ decision trees and then fed through Theorem 2; no application parameter is fitted to the protocol's output. The only notable omission is the proof of Lemma 14, which the paper says is 'very similar to [29,36]', but [29] and [36] are independent prior works by different authors, and the lemma is an algebraic update rule that is directly verifiable; relying on it is not circular. The only self-citation in the paper, [13] (Fischer, Oshman, and Zwick), is used to state classical lower bounds for context and is not load-bearing for any claimed quantum protocol. Accordingly, no circular step meets the evidentiary bar of this review.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central compiler rests only on established quantum information theorems. The graph applications add one unproved, paper-specific algebraic lemma (Lemma 14) that should be supplied in a full version.

assumptions (5)
  • standard math Existence of linear quantum fingerprint families with O(log n) qubits and constant inner-product overlap, with the additional property that the fingerprint of x XOR y can be obtained from the fingerprint of x by a known unitary.
    Invoked in Lemma 1 (Section 3.1), where players send F(x)=|Ψ_x>^{⊗t} and the referee applies the linearity-based conversion. Construction is cited from Ref. [18].
  • standard math Gao's quantum union bound for sequential projective measurements (Theorem 4).
    Used in the proof of Theorem 2 (Section 3.2) to bound the total error of up to D sequential MEQ measurements.
  • standard math Any 2-outcome measurement can be converted into a 2-outcome projective measurement with the same outcome probabilities and with a gentle post-measurement state when the outcome is near-certain.
    Stated in Appendix B and used in Theorem 2 to enable sequential reuse of the players' quantum states.
  • ad hoc to paper Lemma 14: the update rules for the valid representation {(a_v,b_v)} preserve validity when removing a pendant or twin node.
    Stated without proof in Section 4.3 ('the proof is very similar to [29,36], and is omitted here'). It is load-bearing for Theorem 16 (distance-hereditary graph reconstruction).
  • standard math A graph is distance-hereditary iff it has a twin-pendant decomposition, and this decomposition can be computed by repeatedly removing any pendant or twin node.
    Cited from Refs. [6,29] and used as the basis of Algorithm 1 / Theorem 16.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries." pith.science (2026). https://pith.science/paper/TJB6A6O2

@misc{pith2026241208091,
  author       = {Pith},
  title        = {Pith review of: Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TJB6A6O2}},
  note         = {Machine review of arXiv:2412.08091}
}
read the original abstract

In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 26 canonical work pages

  1. [1]

    Lecture notes for the 28th McGill invitational workshop on computational complexity

    Scott Aaronson. Lecture notes for the 28th McGill invitational workshop on computational complexity. Arxiv:1607.05256, 2016

    arXiv 2016

  2. [2]

    Online locality meets distributed quantum computing

    Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, Fran c ois Le Gall , Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, V \' a clav Rozho n , and Jukka Suomela. Online locality meets distributed quantum computing. ArXiv:2403.01903, 2024

    work page arXiv 2024

  3. [4]

    What can be computed without communications? SIGACT News , 45(3):82--104, 2014

    Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News , 45(3):82--104, 2014. https://doi.org/10.1145/2670418.2670440 doi:10.1145/2670418.2670440

    work page arXiv 2014

  4. [5]

    L\'aszl\'o Babai and Peter G. Kimmel. Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC 1997) , pages 239--246, 1997. https://doi.org/10.1109/CCC.1997.612319 doi:10.1109/CCC.1997.612319

    work page arXiv 1997

  5. [6]

    Distance-hereditary graphs

    Hans - J \" u rgen Bandelt and Henry Martyn Mulder. Distance-hereditary graphs. Journal of Combinatorial Theory, Series B , 41(2):182--208, 1986. https://doi.org/10.1016/0095-8956(86)90043-2 doi:10.1016/0095-8956(86)90043-2

    work page doi:10.1016/0095-8956(86)90043-2 1986

  6. [7]

    Stabilization of quantum computations by symmetrization

    Adriano Barenco, Andr \' e Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello. Stabilization of quantum computations by symmetrization. SIAM Journal on Computing , 26(5):1541--1557, 1997. https://doi.org/10.1137/S0097539796302452 doi:10.1137/S0097539796302452

    doi:10.1137/s0097539796302452 1997

  7. [8]

    The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism

    Florent Becker, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. In Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2024) , volume 8576 of Lecture Notes in Computer Science , pag...

    work page doi:10.1007/978-3-319-09620-9 2024

  8. [9]

    Quantum fingerprinting

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf . Quantum fingerprinting. Physical Review Letters , 87:167902, 2001. https://doi.org/10.1103/PhysRevLett.87.167902 doi:10.1103/PhysRevLett.87.167902

    doi:10.1103/physrevlett.87.167902 2001

Show all 40 references
  1. [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 ACM...

    2024

  2. [11]

    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. https://doi.org/10.1145/1412700.1412718 doi:10.1145/1412700.1412718

    2008

  3. [12]

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

    Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014) , pages 166--175, 2014. https://doi.org/10.1145/2611...

    2014

  4. [13]

    Public vs

    Orr Fischer, Rotem Oshman, and Uri Zwick. Public vs. private randomness in simultaneous multi-party communication complexity. Theoretical Computer Science , 810:72--81, 2020. https://doi.org/10.1016/j.tcs.2018.04.032 doi:10.1016/j.tcs.2018.04.032

    2020 doi

  5. [14]

    Distributed quantum proofs for replicated data

    Pierre Fraigniaud, Fran c ois Le Gall, Harumichi Nishimura, and Ami Paz. Distributed quantum proofs for replicated data. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) , pages 28:1--28:20, 2021. https://doi.org/10.4230/LIPICS.ITCS...

    2021 doi

  6. [16]

    Quantum union bounds for sequential projective measurements

    Jingliang Gao. Quantum union bounds for sequential projective measurements. Physical Review A , 92:052331, 2015. https://doi.org/10.1103/PhysRevA.92.052331 doi:10.1103/PhysRevA.92.052331

    2015 doi

  7. [17]

    Shared randomness and quantum communication in the multi-party model

    Dmitry Gavinsky, Tsuyoshi Ito, and Guoming Wang. Shared randomness and quantum communication in the multi-party model. In Proceedings of the 28th Conference on Computational Complexity ( CCC 2013) , pages 34--43, 2013. https://doi.org/10.1109/CCC.2013.13 doi:10.1109/CCC.2013.13

    2013 doi

  8. [18]

    Quantum communication cannot simulate a public coin, 2004

    Dmitry Gavinsky, Julia Kempe, and Ronald de Wolf . Quantum communication cannot simulate a public coin, 2004. ArXiv:quant-ph/0411051

    2004 arXiv

  9. [19]

    Exponential separation of quantum and classical non-interactive multi-party communication complexity

    Dmitry Gavinsky and Pavel Pudl \' a k. Exponential separation of quantum and classical non-interactive multi-party communication complexity. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity ( CCC 2008) , pages 332--339, 2008. https://doi.org/10.110...

    2008 doi

  10. [20]

    What can be observed locally? In Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009) , volume 5805 of LNCS , pages 243--257

    Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009) , volume 5805 of LNCS , pages 243--257. Springer, 2009. https://doi.org/10.1007/978-3-642-04355-0\_26 d...

    2009 doi

  11. [21]

    Multi-party quantum fingerprinting with weak coherent pulses: circuit design and protocol analysis

    Hip\'olito G\'omez-Sousa. Multi-party quantum fingerprinting with weak coherent pulses: circuit design and protocol analysis. New Journal of Physics , 22:113004, 2020. https://doi.org/10.1088/1367-2630/abc2e5 doi:10.1088/1367-2630/abc2e5

    2020 doi

  12. [22]

    On the power of quantum distributed proofs

    Atsuya Hasegawa, Srijita Kundu, and Harumichi Nishimura. On the power of quantum distributed proofs. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC 2024) , page 220–230, 2024. https://doi.org/10.1145/3662158.3662788 doi:10.1145/3662158.3662788

    2024

  13. [23]

    The communication complexity of the Hamming distance problem

    Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the Hamming distance problem. Information Processing Letters , 99(4):149--153, 2006. https://doi.org/10.1016/j.ipl.2006.01.014 doi:10.1016/j.ipl.2006.01.014

    2006 doi

  14. [24]

    Enumeration of isolated cliques and pseudo-cliques

    Hiro Ito and Kazuo Iwama. Enumeration of isolated cliques and pseudo-cliques. ACM Transactions on Algorithms , 5(4):40:1--40:21, 2009. https://doi.org/10.1145/1597036.1597044 doi:10.1145/1597036.1597044

    2009

  15. [25]

    Linear-time enumeration of isolated cliques

    Hiro Ito, Kazuo Iwama, and Tsuyoshi Osumi. Linear-time enumeration of isolated cliques. In Proceedings of the 13th Annual European Symposium (ESA 2005) , volume 3669 of Lecture Notes in Computer Science , pages 119--130. Springer, 2005. https://doi.org/10.1007/11561071\_13 doi...

    2005 doi

  16. [26]

    Quantum distributed algorithm for the All-Pairs Shortest Path problem in the CONGEST-CLIQUE model

    Taisuke Izumi and Fran c ois Le Gall. Quantum distributed algorithm for the All-Pairs Shortest Path problem in the CONGEST-CLIQUE model. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC 2019) , pages 84--93, 2019. https://doi.org/10.1145/32...

    2019

  17. [27]

    Quantum distributed algorithm for triangle finding in the CONGEST model

    Taisuke Izumi, Fran c ois Le Gall , and Fr \' e d \' e ric Magniez. Quantum distributed algorithm for triangle finding in the CONGEST model. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) , pages 23:1--23:13, 2020. ht...

    2020 doi

  18. [28]

    The efficiency of quantum identity testing of multiple states

    Masaru Kada, Harumichi Nishimura, and Tomoyuki Yamakami. The efficiency of quantum identity testing of multiple states. Journal of Physics A: Mathematical and Theoretical , 41:395309, 2008. https://doi.org/10.1088/1751-8113/41/39/395309 doi:10.1088/1751-8113/41/39/395309

    2008 doi

  19. [29]

    Solving the induced subgraph problem in the randomized multiparty simultaneous messages model

    Jarkko Kari, Mart \' n Matamala, Ivan Rapaport, and Ville Salo. Solving the induced subgraph problem in the randomized multiparty simultaneous messages model. In Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 20...

    2015 doi

  20. [30]

    Isolation concepts for efficiently enumerating dense subgraphs

    Christian Komusiewicz, Falk H \" u ffner, Hannes Moser, and Rolf Niedermeier. Isolation concepts for efficiently enumerating dense subgraphs. Theoretical Computer Science , 410(38-40):3640--3654, 2009. https://doi.org/10.1016/j.tcs.2009.04.021 doi:10.1016/j.tcs.2009.04.021

    2009 doi

  21. [31]

    Algorithmic meta-theorems for restrictions of treewidth

    Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica , 64(1):19--37, 2012. https://doi.org/10.1007/s00453-011-9554-x doi:10.1007/s00453-011-9554-x

    2012 doi

  22. [32]

    Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

    Fran c ois Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications . In Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) , pages 63:1--63:15, 2023...

    2023 doi

  23. [33]

    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 In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018) , pages 337--346, 2018. https://doi.org/10.1145/3212734.32127...

    2018

  24. [34]

    Distributed quantum interactive proofs

    Fran c ois Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed quantum interactive proofs. In Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) , pages 63:1--63:15, 2023. https://doi.org/10.4230/LIPICS.STACS.20...

    2023 doi

  25. [35]

    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 Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS) , pages 49:1--49:14, 2019. https://doi.org/10.4230/LIP...

    2019 doi

  26. [36]

    Graph reconstruction in the congested clique

    Pedro Montealegre, Sebastian Perez - Salazar, Ivan Rapaport, and Ioan Todinca. Graph reconstruction in the congested clique. Journal of Computer and System Sciences , 113:1--17, 2020. https://doi.org/10.1016/j.jcss.2020.04.004 doi:10.1016/j.jcss.2020.04.004

    2020 doi

  27. [37]

    Private vs

    Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters , 39(2):67--71, 1991. https://doi.org/10.1016/0020-0190(91)90157-D doi:10.1016/0020-0190(91)90157-D

    1991 doi

  28. [38]

    Public vs

    Ilan Newman and Mario Szegedy. Public vs. private coin flips in one round communication games (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996) , pages 561--570, 1996. https://doi.org/10.1145/237814.238004 doi:...

    1996

  29. [39]

    General theory of quantum fingerprinting network

    Ji-Qian Qin, Jing-Tao Wang, Yun-Long Yu, and Xiang-Bin Wang. General theory of quantum fingerprinting network. Physical Review Research , 3:033039, 2021. https://doi.org/10.1103/PhysRevResearch.3.033039 doi:10.1103/PhysRevResearch.3.033039

    2021 doi

  30. [40]

    Exact quantum algorithms for the leader election problem

    Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto. Exact quantum algorithms for the leader election problem. ACM Transactions on Computation Theory , 4(1):1:1--1:24, 2012. https://doi.org/10.1145/2141938.2141939 doi:10.1145/2141938.2141939

    2012

  31. [41]

    Quantum complexity of weighted diameter and radius in CONGEST networks

    Xudong Wu and Penghui Yao. Quantum complexity of weighted diameter and radius in CONGEST networks. In Proceedings of the 42nd ACM Symposium on Principles of Distributed Computing (PODC 2022) , pages 120--130, 2022. https://doi.org/10.1145/3519270.3538441 doi:10.1145/3519270.3538441

    2022

  32. [42]

    On the power of quantum fingerprinting

    Andrew Chi - Chih Yao. On the power of quantum fingerprinting. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003) , pages 77--81, 2003. https://doi.org/10.1145/780542.780554 doi:10.1145/780542.780554

    2003

Pith tools

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