{"id":"71e41592-a119-40b7-9be7-ef1ba72b4d40","arxiv_id":"2412.08091","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A compiler converts classical modified-equality-query decision trees into quantum simultaneous protocols with only O(k log D log n) qubits, proving that quantum messages can replace public coins for several multi-party problems.","lead":"This paper shows that quantum messages can replace shared randomness in certain multi-player simultaneous communication protocols. It gives the first such positive results for more than two players, with applications to graph problems like counting dense subgraphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: reader's flagged Lemma 14 is correct on direct verification, and the Theorem 20 depth expression is a typo that does not affect the asymptotic communication bound.","rationale":"The reader's conditional verdict is driven by two concerns: the omitted proof of Lemma 14 and an apparent depth-counting imprecision in Theorem 20. I checked Lemma 14 directly. For a pendant node w with neighbor u, removing w changes only b_u, which must lose the a_w term; the rule b'_u = b_u ⊕ a_w is exactly right, and all other neighborhoods are unchanged. For false twins w,u, w appears in exactly the neighborhoods where u appears, so replacing a_u by a_u⊕a_w and leaving all b_v unchanged compensates for deleting a_w; linear independence is preserved because any dependence among the new a-vectors would translate to a non-empty subset of the original independent family summing to zero. For true twins, the same compensation works for every common neighbor, and b_u is additionally flipped by a_w to account for the edge (w,u). Thus the update rules are correct, and the distance-hereditary application (Theorem 16) is not endangered. The Theorem 20 depth expression contains a typo: checking all vectors of weight at most d over {0,1}^k has depth Σ_{c=0}^d binom(k,c)=O(k^d), so MHAM^{2d} and MHAM^{2d+2} have depths O(k^{2d}) and O(k^{2d+2}) respectively, not O(k^{d+2}). But the logarithm of either depth is O(d log k), and Theorem 2's communication depends only on log D, so the claimed O(kd log^2 k) bound is unaffected. The central compiler theorem appears sound: the gentle-measurement conversion is standard, and Gao's bound applies to the sequence of projective measurements even though the measurements act on overlapping registers and the tree path is adaptive. I therefore find no load-bearing correctness concern, though adding the short proof of Lemma 14 and fixing the depth typo would improve the paper.","tokens_in":17806,"tokens_out":26300,"duration_ms":267468,"concrete_test":"Provide the missing proof of Lemma 14 as a three-case calculation: for cases I-III show (i) the new family {a'_v}_{v∈V\\{w}} has no non-empty subset summing to 0, and (ii) b'_v equals the sum of a'_x over the new neighborhood N'(v); the case analysis is short and entirely algebraic. Independently re-derive the depth of the MHAM decision trees in Theorem 20 using depth Σ_{c=0}^{d} binom(k,c) for MHAM^d; this will confirm the depth is O(k^{2d+2}) and the log-depth is O(d log k), leaving the communication bound unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined the compiler (Theorem 2) and the applications. The central claim rests on Lemma 1, the projective-measurement conversion, and Gao's quantum union bound; these steps are standard and the error accounting (ε=δ/(4D), then the factor 4 in Theorem 4) is sound. The only substantive worry raised by the reader is Lemma 14, whose proof is omitted. Direct verification shows the lemma is true: in each of the three cases the modified family {a'_v} remains linearly independent (a non-empty subset sum would pull back to a non-empty subset sum in the original independent family), and the update of the unique affected b'_v exactly compensates for removing a_w and replacing a_u by a_u⊕a_w. Thus the distance-hereditary reconstruction protocol is supported. The other flagged point, the depth expression in Theorem 20, is a typo: MHAM^{2d} and MHAM^{2d+2} decision trees have depths O(k^{2d}) and O(k^{2d+2}), not O(k^{d+2}); however both give log-depth O(d log k), so the stated O(kd log^2 k) communication is unchanged. No load-bearing correctness concern identified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18050,"tokens_out":20986,"duration_ms":200364,"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":[{"comment":"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.","section":"Section 4.3, Lemma 14"}],"minor_comments":[{"comment":"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.","section":"Section 4.4, proof of Theorem 20"},{"comment":"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.","section":"Section 3, Theorem 2"},{"comment":"Line 7 of Algorithm 2 reads '∃w,v' but the query and comment refer to u; it should be '∃w,u'.","section":"Section 4.3, Algorithm 2"},{"comment":"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.","section":"Section 4.4, Definition 17"}],"recommendation":"major_revision","confidential_remarks":"I verified Lemma 14 by hand and it is correct, so the paper does not contain a load-bearing error. The main revision needed is to add the proof of Lemma 14; the remaining issues are typographical. The contribution is significant for the quantum distributed computing community, and I recommend major revision mainly to ensure the completeness of the proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the first paper to show that quantum communication can replace public randomness in multi-player simultaneous message passing beyond two players, and the proof of the main compiler is in good shape. It deserves a serious referee.\n\nThe new thing is a compiler (Theorem 2) that turns any MEQ decision tree of depth D into a k-player quantum SMP protocol with O(k(log D + log(1/δ)) log n) qubits and error δ. The key move is to run each query as a projective measurement with very high success probability, so the players' fingerprints survive reuse; Gao's quantum union bound then controls the accumulated error. That is a clean and genuinely useful idea. The applications to grouping by equality, frequency moments, neighborhood diversity, isolated cliques, and distance-hereditary reconstruction are concrete and give exponential improvements over classical private-coin protocols. The classical decision trees come from prior work and are cited properly.\n\nI checked the two spots the referee report flags. Lemma 14's proof is indeed omitted; the paper says it is \"very similar\" to [29,36]. I verified the three update rules directly. In each case the new {a_v} stays linearly independent, and the changed b_u compensates exactly for removing a_w. So the distance-hereditary reconstruction protocol looks supported, but the authors should still write out the proof rather than leave it to the reader. The depth expression in Theorem 20 also has an exponent slip: MHAM^{2d} and MHAM^{2d+2} trees have depths O(n^{2d}) and O(n^{2d+2}), not O(n^d) and O(n^{d+2}). Both give log-depth O(d log n), so the stated O(k d log^2 k) communication bound is unaffected.\n\nOverall the central argument holds up. The paper is for people working on quantum communication complexity and distributed computing; it gives them a new tool and a batch of first positive results in a previously negative-looking area. The right move is to send it to peer review and ask for a revision that supplies the missing proof of Lemma 14 and fixes the typo in Theorem 20. I would be happy to be that referee.","headline":"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.","tokens_in":18531,"tokens_out":2498,"would_cite":true,"duration_ms":22426,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["SMP model","quantum communication complexity","public randomness","modified equality queries","quantum fingerprinting","neighborhood diversity","distance-hereditary graphs","isolated cliques"],"falsifier":"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.","tokens_in":17630,"feed_emoji":"⚛️","tokens_out":9092,"duration_ms":79528,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quantum fingerprints remove the need for public randomness","feed_subtitle":"A compiler converts public-coin protocols into private-coin quantum ones at nearly the same cost.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the SWAP-test quantum fingerprinting protocol whose single-query behavior Lemma 1 adapts to modified equality queries.","marker":"[9]"},{"why":"constructs the linear quantum fingerprint family whose fingerprints can be unitarily shifted by known modifier strings.","marker":"[18]"},{"why":"provides the quantum union bound used to keep the total error small when many gentle measurements are applied sequentially.","marker":"[16]"},{"why":"gives the pendant-twin decomposition and public-coin reconstruction protocol that the distance-hereditary protocol simulates with modified equality queries.","marker":"[29]"},{"why":"extends graph reconstruction to distance-hereditary graphs and supplies the update-rule approach that Lemma 14 adapts.","marker":"[36]"},{"why":"defines neighborhood diversity, the graph parameter computed by Theorem 10.","marker":"[31]"},{"why":"introduces max-d-isolated cliques, the objects enumerated by Theorem 20.","marker":"[30]"},{"why":"defines the number-in-hand network model used by the graph applications.","marker":"[8]"},{"why":"shows a three-player problem where quantum-without-coin protocols are exponentially weaker than classical public-coin protocols, the negative result this paper's compiler circumvents.","marker":"[17]"},{"why":"shows quantum fingerprinting in the two-party simultaneous model, the seed of the multi-party approach.","marker":"[42]"}],"fun_headline_variants":["Quantum fingerprints erase public randomness","Multiparty quantum protocols skip public coins","Compiler converts public-coin to private-coin quantum","Modified equality queries go quantum without public coins"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum fingerprints erase public randomness","Multiparty quantum protocols skip public coins","Compiler converts public-coin to private-coin quantum","Modified equality queries go quantum without public coins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000281,"raw_usage":{"total_tokens":1632,"prompt_tokens":884,"completion_tokens":748,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":500,"completion_tokens_details":{"reasoning_tokens":694}},"tokens_in":500,"tokens_out":748,"duration_ms":7901,"temperature":1.0,"reasoning_tokens":694,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:14:28.672490+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Quantum Communication Cannot Simulate a Public Coin","cited_arxiv_id":"quant-ph/0411051","evidence_quote":"constructs the linear quantum fingerprint family whose fingerprints can be unitarily shifted by known modifier strings."},{"cited_title":"Graph reconstruction in the congested clique","cited_arxiv_id":null,"evidence_quote":"extends graph reconstruction to distance-hereditary graphs and supplies the update-rule approach that Lemma 14 adapts."},{"cited_title":"Isolation concepts for efficiently enumerating dense subgraphs","cited_arxiv_id":null,"evidence_quote":"introduces max-d-isolated cliques, the objects enumerated by Theorem 20."},{"cited_title":"The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism","cited_arxiv_id":null,"evidence_quote":"defines the number-in-hand network model used by the graph applications."},{"cited_title":"Shared randomness and quantum communication in the multi-party model","cited_arxiv_id":null,"evidence_quote":"shows a three-player problem where quantum-without-coin protocols are exponentially weaker than classical public-coin protocols, the negative result this paper's compiler circumvents."},{"cited_title":"On the power of quantum fingerprinting","cited_arxiv_id":null,"evidence_quote":"shows quantum fingerprinting in the two-party simultaneous model, the seed of the multi-party approach."}],"review_version":1}