{"id":"c6d3fdf1-6e65-4023-9883-647ce2d4cdc8","arxiv_id":"2412.14757","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A peer-to-peer protocol, P2PGSD, distributes arbitrary graph states over quantum networks, with hardness proofs and simulations showing up to 50% resource savings for sparse graphs.","lead":"This paper introduces a peer-to-peer protocol for distributing multiparty entangled graph states across quantum networks, treating each entanglement connection like a file that nodes can pass along. It reports large resource savings for sparse graph states and proves that optimizing the distribution is NP-hard in several senses.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported resource savings may be inflated by discarding >200-shot samples; the headline 50% improvement needs a no-truncation rerun.","rationale":"The reader's weakest_assumption was the unproven correctness of the modified Dijkstra step in Section 3.3. That is a real gap, but the P2PGSD family is explicitly heuristic, and local suboptimality would at most mean the algorithm leaves some resources on the table; it does not directly threaten the claimed advantage over MGST. By contrast, the numerical headline is the paper's main evidence, and it is computed from truncated samples. The paper itself flags the cutoff, so this is not an artifact of my reading. If the tail censoring is biased across algorithms, the reported 'up to 50%' can be wrong in direction. That makes the central quantitative claim conditional on a methodological fix. I do not think this warrants changing the reader's CONDITIONAL verdict; it reinforces it. The Dijkstra proof gap and the unresolved code repository remain secondary concerns. Therefore the verdict is unchanged, with partial agreement: the reader identified a different weakest assumption but did also note the truncated-sample issue in the rationale.","tokens_in":32099,"tokens_out":12377,"duration_ms":106001,"concrete_test":"Rerun the experiments in Fig. 8(a,b) with the same seeds and configuration but without the >200-shot cutoff, and report the mean, median, and 95th percentile of #S and #M for each algorithm, together with the fraction of samples exceeding 200 shots at each success probability. If the P2PGSD-vs-MGST ordering or the ≥50% improvement changes at any tested probability, the claimed advantage must be qualified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's headline ('improvement of up to 50% for general sparse graph states') and Section 4.3's 'huge advantage' are quantitative claims supported only by simulation. The Fig. 8 caption states: 'The samples (less than 5% for each data point) that consume more than 200 shots are discarded to avoid extremeness.' This censors the upper tail of the resource-usage distribution. In a probabilistic network with success probabilities down to 0.4, shot and memory usage are heavy-tailed: a small fraction of very long runs can dominate the mean. Truncating the top 5% can lower a reported mean substantially, and the effect is algorithm-dependent because MGST (with its center-node choice) and the P2PGSD variants have different tail behavior. Thus the reported relative advantage, and the 'up to 50%' number, may be an artifact of the censoring rule rather than a robust property of the protocols. The paper does not report untruncated means or the per-algorithm tail fraction, so the central empirical claim is not yet established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes the distribution of an arbitrary graph state over a stochastic quantum network as a triple (network, graph state, assignment), introduces the metrics #S (shots), #B (Bell-pair usage), and #M (cumulative memory usage), and proves NP-hardness of optimizing each of these metrics. It also claims a tight worst-case upper bound on #S under unlimited memory. The main algorithmic contribution is a pair of decentralized heuristics, P2PGSD and ST-P2PGSD, inspired by classical peer-to-peer file distribution, together with an adaptation of the earlier GST algorithm, called MGST. The protocols are evaluated in a custom simulator against MGST for tree, star, grid, Bell-pair, and sparse Erdős-Rényi graph states on random Waxman topologies, with the abstract claiming resource improvements of up to 50% for general sparse graph states. A scheme for distributing quantum computations by teleporting a layer of CZ gates is also proposed.","tokens_in":32323,"tokens_out":5408,"duration_ms":50712,"significance":"If the results hold, the paper would make a useful contribution: it gives a general mathematical model for multiparty graph-state distribution in stochastic networks, introduces a spacetime-network accounting method that treats memory symmetrically with Bell-pair usage, and provides decentralized algorithms with a plausible scaling advantage over centralized schemes for sparse target graphs. The comparison against a modified version of Fischer and Towsley's GST is an appropriate baseline, and the paper's explicitly formulated resource metrics are sensible. The main weaknesses are that several load-bearing proofs are presented as sketches or with omitted details, the correctness of the modified Dijkstra step is explicitly unproven, and the headline empirical improvement is based on simulation data from which the upper tail of the resource distribution has been discarded. These issues need to be addressed before the paper's central claims can be regarded as established.","major_comments":[{"comment":"The proof of the claimed tight upper bound on #S is not rigorous. The key step asserts without proof that 'removing or reversing a subset of paths passing a specific node will not increase the absolute flow values in the channels connecting to it', then moves the root to the downstream endpoint and reverses paths. This argument does not show that the modified flow still satisfies the reachability condition of Definition 2.6 at every intermediate step, nor that the capacity constraints are respected after the root is moved. A formal exchange or uncrossing argument is needed; as written, the claimed tightness and the subsequent optimality discussion are not established.","section":"Appendix A, Theorem A.2"},{"comment":"The correctness of the modified Dijkstra pathfinding is explicitly omitted, and the stated condition ('no path from other n_{v_{s1,i}}/n_{v_{s2,j}} to other n_{v_{s1,i'}}/n_{v_{s2,j'}} with smaller cost exists') is effectively the property the algorithm is supposed to verify. Since P2PGSD is greedy and its resource-minimization claim depends on these paths being near-optimal, the paper needs either a proof of correctness under precise assumptions or a characterization of when the greedy choice is optimal. In the absence of such a proof, the simulation results cannot be attributed to the algorithm's intended optimality properties.","section":"Section 3.3, modified Dijkstra"},{"comment":"The empirical claim of 'an improvement of up to 50%' is supported by simulation data in which samples consuming more than 200 shots are discarded, as stated in the Fig. 8 caption. Resource usage in a probabilistic network with success probabilities down to 0.4 is heavy-tailed, so truncating the upper tail can substantially lower the reported means, and the bias may differ across algorithms because MGST and the P2PGSD variants have different tail behavior. The paper should report untruncated means and medians, the number of discarded samples per algorithm and data point, and ideally a rerun without the 200-shot cutoff, before the 'up to 50%' claim can be accepted.","section":"Section 4.3 and Fig. 8"},{"comment":"The NP-hardness reductions are presented at the level of sketches rather than complete proofs. The restriction to unit-width channels and unlimited memory is justified by 'one can easily persuade oneself', and the modification that makes G_S connected in the edge-disjoint-paths reduction is asserted with 'we omit the details of the proof here'. Since intractability of all three resource metrics is a principal theoretical contribution, the reductions need to be spelled out completely, including the connected-G_S construction and the verification that the Steiner-tree reduction for #B and the memory-cost reduction for #M preserve optimality exactly.","section":"Appendix A, Theorem A.1"},{"comment":"The proof that any GST flow solution can be converted into a simply executable path set in N shots divides the flow by N and invokes the integral flow theorem, but it does not demonstrate that the resulting paths are executable within the original channel width constraints at each shot, nor that the implied memory strategy respects the W_m capacities. Because Theorem A.4 underlies the validity of the MGST baseline used throughout the evaluation, a complete proof is necessary rather than optional.","section":"Appendix A, Theorem A.4"}],"minor_comments":[{"comment":"The cost C_B is written as -b_i sum_i log(P_i); the placement of b_i inside the prefactor and the missing index range on the sum make the formula ambiguous.","section":"Equation (6)"},{"comment":"The text refers to a 'cell topology network shown in Fig. 7 (g)', but the figure contains panels (a)-(f); the caption and the in-text reference need to be aligned.","section":"Fig. 7"},{"comment":"The repository link appears as '[?]' rather than as a citation to reference [75]; this should be fixed.","section":"Section 4.1"},{"comment":"The base case of the recursive reachability definition uses n_i in both V_N and V_N x [N+1]; the notation should distinguish spacetime nodes from physical nodes, otherwise the definition is confusing.","section":"Definition 2.6"},{"comment":"The hyperparameters m_f and the memory-cost prefactor are introduced but their values in the simulations are not reported; a sensitivity analysis or at least a statement of the chosen values is needed for reproducibility.","section":"Section 3.4"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the paper is within the journal's scope and has a plausible central idea, but the formal developments are currently too sketchy and the headline empirical claim is weakened by the censored simulation data. I do not recommend rejection, but the authors should be asked to supply complete proofs for the hardness reductions and the upper-bound theorem, prove or properly qualify the modified Dijkstra step, and rerun the simulations without truncation while reporting tail statistics. The relationship between the simulation setup and the claimed 'up to 50%' figure also needs to be made explicit in the main text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is a genuinely new angle on multiparty entanglement distribution: treat each graph-state edge as a file in a classical P2P network, and use fusion operations to 'copy' and merge ancillary qubits. The space-time network construction for tracking memory alongside Bell-pair usage is also a nice conceptual tool, and it pays for itself by turning the memory-allocation problem into a flow problem. The paper deserves a serious referee.\n\nWhat's good: the formal problem model is the first I've seen that unifies Bell-pair routing and graph-state distribution under one metric set (shots, Bell-pair count, cumulative memory). The NP-hardness reductions, while sketched, are plausible and point in the right direction. The simulation study is broad: multiple graph families, network sizes up to 200, channel success rates down to 0.4, and a modified GST baseline. For tree and grid graphs, the P2P series consistently beats MGST in shots and memory. The authors also honestly include regimes where MGST wins (dense graphs), which is a good sign.\n\nSoft spots, in order of severity. (1) The headline 'up to 50%' is supported by Fig 8, and Fig 8 discards samples consuming more than 200 shots ('less than 5% for each data point'). In a probabilistic network with success probabilities down to 0.4, resource usage is heavy-tailed; dropping the top 5% can move the mean a lot, and the algorithms have different tail behavior. The paper does not report untruncated means or per-algorithm truncation fractions, so the relative advantage may be inflated. This is the one claim I'd want re-run before accepting. (2) The modified Dijkstra correctness is explicitly omitted and rests on a greedy local-optimality assumption that may fail; this undermines the optimality language, though the algorithm is a heuristic anyway. (3) The proofs in Appendix A are often sketches ('one can easily persuade oneself', flow-reversal arguments). Theorems 2.1–2.3 are believable, but a referee should ask for formal statements. (4) The code repository citation is an unresolved '[?]' in the text; the GitHub link [75] exists but the paper doesn't point to it cleanly. That's a reproducibility issue.\n\nWho is this for: quantum network protocol researchers, especially people working on multiparty entanglement, quantum repeaters, and distributed quantum computing. It's a protocols/systems paper with clear practical relevance.\n\nMy recommendation: send to peer review. The core idea is strong and the simulations, modulo the truncation issue, support the qualitative claims. Ask for the no-truncation rerun, a tighter correctness statement for the Dijkstra variant, and a clean code/data link. If those come back, this will be a useful paper.","headline":"Fresh P2P-style graph-state distribution with real algorithmic ideas; the 50% resource advantage needs a no-truncation rerun before I'd trust the headline.","tokens_in":32847,"tokens_out":2767,"would_cite":true,"duration_ms":23054,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Hk","03.67.Mn"],"model":"deepseek-v4-flash","headline":"This paper shows that graph-state entanglement can be distributed peer-to-peer, treating each vertex's entangling connections as files that any holding node can re-share, and that this approach cuts shot and memory usage by up to 50%…","keywords":["quantum networks","graph states","peer-to-peer entanglement distribution","space-time network","quantum memory management","entanglement routing","NP-hardness","distributed quantum computation"],"falsifier":"Run the paper's reference simulation settings from Section 4.2 on a 50-node random network with distance-decaying channel success near 0.87, distributing a sparse tree and a grid graph with 9 to 200 vertices, and record the median shot usage and cumulative memory for P2PGSD, ST-P2PGSD, and MGST; if the peer-to-peer family does not beat MGST by roughly the claimed margin on these instances, the central advantage claim is refuted.","tokens_in":31898,"feed_emoji":"🔗","tokens_out":14602,"duration_ms":112976,"temperature":0.7,"pith_summary":"Distributing a multiparty entangled state across a quantum network is normally done by creating the whole state at one center and teleporting qubits outward. This paper argues that graph states—entangled states whose vertices are qubits and edges are entanglements—can instead be distributed peer-to-peer: a node holding a vertex's connections can use one Bell pair to create an ancilla at another node, so those connections behave like a file that any holder can re-share. The authors build two algorithms on this idea, P2PGSD (peer-to-peer graph state distribution) and the space-time version ST-P2PGSD, prove that optimizing shots, Bell-pair use, or memory for the general problem is NP-hard, and simulate that the peer-to-peer family beats the center-based MGST algorithm by up to 50% in shot usage and cumulative memory on sparse graph states such as trees, grids, and star graphs. If the result holds, resource-efficient multiparty entanglement distribution across arbitrary network topologies becomes a plausible network-layer primitive rather than an expensive central service, with direct consequences for distributed quantum computation and quantum secret sharing.","feed_headline":"Treating entanglement as files nearly halves quantum-network costs","feed_subtitle":"For sparse graph states, sharing entanglement like files instead of shipping qubits from a center saves shots and memory.","key_machinery":"The load-bearing mechanism is the reversed fusion operation: a node holding a vertex's connections can create an ancilla at another node through one Bell pair, so the vertex's entanglements behave like a redistributable file and the graph-state topology is exploited rather than ignored. The paper tracks this through a Vertex Reaching Map (VRM), a dictionary from each graph-state vertex to the set of network nodes that can currently host its ancilla; routing an edge becomes a shortest-path search between the two endpoint sets. For memory, the space-time network makes one copy of the network for each time shot and adds memory links from $(n_i,k)$ to $(n_i,k+1)$, so cumulative memory usage is a cost exactly symmetric to cumulative Bell-pair usage; ST-P2PGSD plans paths on this augmented graph, jointly optimizing shots and memory. The recovery layer (Expected Union Method) chooses which qubits to switch at each node to maximize the probability of completing a path.","core_discovery":"The central discovery is that the multiparty generalization of entanglement routing has a peer-to-peer structure: a vertex's entanglement with the rest of the graph state can be separated from the qubit itself, distributed as an ancilla over a Bell pair, and later fused back, so the same 'file' can be re-shared without cloning any quantum information. The paper formalizes this as the General Graph State Distribution Problem with three resources—number of shots, Bell-pair consumption, and cumulative memory usage—and proves all three minimization problems are NP-hard, with a tight $\\lfloor |V_S|/2 \\rfloor$ shot upper bound under unlimited memory. It then proposes P2PGSD, a greedy protocol that routes graph edges using a Vertex Reaching Map and a modified shortest-path search, and ST-P2PGSD, which runs the same search on a space-time network in which memory links and Bell-pair links are symmetric. Simulations on random networks show the peer-to-peer family using fewer shots and less cumulative memory than the modified center-based MGST algorithm for star, tree, grid, and sparse random graph states, with the advantage growing with state size and reaching up to 50%.","pith_inferences":["Going beyond the paper, the space-time construction should apply to any distributed quantum protocol whose resource cost is a weighted sum of Bell-pair and memory terms: one can tune the memory weight and get the same trade-off curve the paper observes between its standard, maximum-memory, and space-time variants.","A natural test is to compose P2PGSD with a preprocessing step that finds a local-complementation-equivalent graph state with fewer edges, since the paper's own outlook notes the peer-to-peer advantage is strongest when the target graph is sparse; this could extend the advantage to denser states.","The unproved local-optimality assumption in the modified shortest-path search can be probed directly: on small random instances, compare P2PGSD's cost against an exact optimizer or the linear-programming approach cited in the paper and measure how often the greedy step is suboptimal and how large the penalty is."],"forward_implications":["For sparse target states—trees, grids, star (GHZ) states, and low-degree random graphs—the peer-to-peer distribution algorithms use fewer shots and less cumulative memory than center-based transfer, and the advantage grows with the number of vertices, reaching up to 50% in the reported simulations.","The optimization problems for shots, Bell-pair consumption, and cumulative memory are NP-hard even for injective assignments and connected target graphs, so no exact efficient algorithm exists for the general problem and heuristics are justified.","With unlimited memory, any distribution takes at most $\\lfloor |V_S|/2 \\rfloor$ shots, and this bound is tight, so the shot complexity of graph-state distribution is linear in the state size in the worst case.","The space-time network turns memory management into a routing problem: choosing which qubits to keep for the next shot becomes a choice of memory links, which lets one algorithm optimize both time and memory together.","A distributed graph state can teleport an entire layer of CZ gates at once using only local operations, so efficient graph-state distribution directly lowers the resource cost of distributed quantum computation and quantum secret sharing."],"supporting_citations":[{"why":"Classical peer-to-peer download concept that inspires treating graph-state vertex connections as files distributed among holders.","marker":"[5]"},{"why":"Source of the center-based Graph State Transfer algorithm that the paper modifies into MGST and uses as the baseline.","marker":"[30]"},{"why":"Supplies the concurrent Bell-pair routing model, the four-phase network cycle, and the recovery-path idea that the paper adapts.","marker":"[67]"},{"why":"Space-time and time-varying network routing constructions used to build the spacetime network for memory-aware pathfinding.","marker":"[76, 77]"},{"why":"Defines graph states as multiparty entanglement resources and establishes the CZ and fusion operations used throughout.","marker":"[38]"},{"why":"Provides the stochastic channel model and cumulative cost and attenuation reasoning used in the cost metrics and threshold analysis.","marker":"[4]"},{"why":"Sources the NP-hard tree-cover problem used to prove intractability of minimizing Bell-pair consumption.","marker":"[45]"},{"why":"Sources the edge-disjoint paths problem used to prove intractability of minimizing shot usage.","marker":"[28, 46]"}],"fun_headline_variants":["Peer-to-peer entanglement distribution cuts resource use up to 50%","Spacetime P2P protocol shares graph states with half the cost","Quantum entanglement as files: P2P distribution cuts network costs","P2P graph-state distribution beats center routing by 50%","Space-time symmetric entanglement routing halves resource costs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the unproved local-optimality assumption in the modified shortest-path search: whenever P2PGSD routes an edge, it assumes no cheaper path exists between the other currently reachable nodes of the two endpoints, so if that assumption fails, the algorithm can route edges wastefully and the claimed resource savings shrink.","fun_headline_variants_meta":{"raw":{"variants":["Peer-to-peer entanglement distribution cuts resource use up to 50%","Spacetime P2P protocol shares graph states with half the cost","Quantum entanglement as files: P2P distribution cuts network costs","P2P graph-state distribution beats center routing by 50%","Space-time symmetric entanglement routing halves resource costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000606,"raw_usage":{"total_tokens":2839,"prompt_tokens":974,"completion_tokens":1865,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":590,"completion_tokens_details":{"reasoning_tokens":1779}},"tokens_in":590,"tokens_out":1865,"duration_ms":13084,"temperature":1.0,"reasoning_tokens":1779,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:55:56.349809+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's reference simulation settings from Section 4.2 on a 50-node random network with distance-decaying channel success near 0.87, distributing a sparse tree and a grid graph with 9 to 200 vertices, and record the median shot usage and cumulative memory for P2PGSD, ST-P2PGSD, and MGST; if the peer-to-peer family does not beat MGST by roughly the claimed margin on these instances, the central advantage claim is refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Classical peer-to-peer download concept that inspires treating graph-state vertex connections as files distributed among holders."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the center-based Graph State Transfer algorithm that the paper modifies into MGST and uses as the baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the concurrent Bell-pair routing model, the four-phase network cycle, and the recovery-path idea that the paper adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines graph states as multiparty entanglement resources and establishes the CZ and fusion operations used throughout."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Sources the NP-hard tree-cover problem used to prove intractability of minimizing Bell-pair consumption."}],"review_version":1}