{"id":"f0c9c2e7-2fb0-4d50-aa2c-419a374780c7","arxiv_id":"2506.12462","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces BeQuP-Link and BeQuP-Path, two algorithms that identify the highest-fidelity (or highest-SKF) path in a quantum network with high probability while using fewer quantum resources than baselines.","lead":"This paper studies how to find the best path between two nodes in a quantum network, where path quality is measured by fidelity or secret key fraction. It proposes two online learning algorithms, one for networks where individual links can be benchmarked and one for networks where only entire paths can be benchmarked, and analyzes their quantum resource costs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"BeQuP-Path calls LinkEst on candidate sets smaller than L, so its design matrix is necessarily singular; as written the algorithm is not executable for L>1.","rationale":"The reader's weakest assumption was the global full-rank WLOG for X. I agree that this is a gap, but the sharper and more load-bearing problem is that Algorithm 4 passes shrunken candidate sets to LinkEst. Even when the initial full path set spans R^L, any candidate set of size less than L produces an L x L design matrix A of rank at most |S|, so the inversion in Algorithm 3 is undefined. Since Algorithm 4 is explicitly designed to reduce |S| to one, it must eventually call LinkEst with |S| < L unless a single lucky prune eliminates all but one path and no further LinkEst call occurs; the algorithm does not guarantee or even state such a condition. There is also a termination issue for non-powers of two when the final threshold is zero. The link-level algorithm and the NetSquid simulations may still be useful, but the central path-level contribution, Theorem 4, is not supported by the stated procedure. A revised version could fix this by projecting each candidate set to its span, using a pseudo-inverse with appropriate confidence bounds, and adding an explicit stop when the candidate set is a singleton, but none of these are present in the current manuscript.","tokens_in":19004,"tokens_out":16983,"duration_ms":228689,"concrete_test":"On the L=3 network with paths {100, 010, 001, 110}, execute Algorithm 4 as written and instrument Algorithm 3 to print the rank of A before the inversion at Line 6. The loop structure forces a LinkEst call with |S| < 3 at some point (for example at h=1 or h=2 whenever pruning does not jump directly from 3 paths to 1). For that call, rank(A) <= |S| < 3, so A is singular and A^{-1} is undefined. This check is deterministic: it does not depend on random samples, only on the size and rank of the candidate set.","verdict_should_be":"REJECT","load_bearing_attack":"The path-level algorithm's correctness rests on LinkEst's matrix inversion. Algorithm 4 repeatedly invokes LinkEst(S_h^(1), N) on a shrinking candidate set. The reader flagged the global WLOG rank assumption in Section III.A; the actual problem is stronger. For any call with |S| < L, the matrix A = N * sum_{k in S} lambda(k) x(k) x(k)^T has rank at most |S| < L, hence is singular and A^{-1} in Algorithm 3, Line 6 is undefined. Algorithm 4 is designed to reduce |S| to 1, with h running to ceil(log2 L), so for every L>1 the algorithm must reach a state with |S| < L unless a single pruning step jumps from at least L paths to 1 path and avoids all future LinkEst calls; that is not guaranteed and not argued. Moreover, when L is not a power of two, the final h = ceil(log2 L) iteration has threshold floor(L/2^h) = 0, so a singleton candidate set causes the inner while loop to call LinkEst on one path forever. The WLOG projection statement in Section III.A applies only to the global matrix X, not to pruned subsets, and Lemma 3 provides no accuracy guarantee for rank-deficient S. Thus Theorem 4 cannot hold for Algorithm 4 as written; the failure is an internal inconsistency, not a disagreement with the literature.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of identifying the highest-fidelity path between two end nodes in a quantum network under an online learning formulation. Two feedback models are considered: link-level benchmarking, in which individual links can be probed, and path-level benchmarking, in which only end-to-end path measurements are available. The paper proposes BeQuP-Link, a link-level algorithm that adaptively benchmarks links in the symmetric difference between the empirical best path and an optimistic alternative, and BeQuP-Path, a path-level algorithm that first estimates link parameters from path-level samples via a linear-regression subroutine (LinkEst) and then prunes candidate paths. The authors claim resource complexity bounds in Theorems 2 and 4, extend the framework to the secret-key-fraction objective, and report NetSquid simulations for both objectives. The central difficulty of the paper is that the path-level algorithm, as written, is not executable and its main theorem is therefore not supported.","tokens_in":19289,"tokens_out":6249,"duration_ms":91078,"significance":"If the claimed results held, the paper would make a useful contribution: it formulates a clean online best-path identification problem for quantum networks, explicitly exploits path overlap to avoid complexity that is exponential in the path length, and provides simulation evidence for both fidelity and secret-key-fraction objectives. The link-level algorithm and its analysis are plausible and the problem setup is well motivated. However, the path-level algorithm contains a load-bearing correctness failure: LinkEst requires inverting a matrix that is singular whenever the candidate path set has fewer paths than links, and Algorithm 4 is designed to shrink the candidate set to a singleton. This is an internal inconsistency in the algorithm definition, not merely a gap in the proof. As a result, the main path-level claim (Theorem 4) cannot be accepted in the present form.","major_comments":[{"comment":"LinkEst is not defined on candidate sets of size less than L. In Algorithm 3, Line 6 computes A^{-1}, where A = N sum_{k in S} lambda(k) x(k) x(k)^T. Since A is a sum of |S| rank-one matrices, its rank is at most |S|, so for |S| < L the matrix A is singular and A^{-1} does not exist. Algorithm 4 is guaranteed to reach such a candidate set: for the final outer iteration h = ceil(log2 L), the inner while condition is |S_h^{(s)}| > floor(L/2^h) = 0, so any nonempty set triggers a LinkEst call; when the set is a singleton, pruning leaves that singleton unchanged and the inner loop does not terminate. Therefore Algorithm 4 is not executable as stated for L > 1, and Theorem 4 cannot hold for it. The rank-assumption discussion in Section III.A concerns the global matrix X only and does not apply to pruned subsets S_h^{(s)}.","section":"Section V, Algorithms 3 and 4"},{"comment":"The assertion \"without loss of generality, assume the matrix X has rank exactly L\" is not backed by an argument or construction. The proposed projection to a lower-dimensional space is not specified, and it is not shown that the projection preserves the identity of the best path or the link-level parameters used by LinkEst. This assumption is load-bearing: Lemma 3 and LinkEst require invertibility of the sampled design matrix. Moreover, even if the global matrix X has rank L, a pruned subset S_h^{(s)} can be rank-deficient, so the global rank assumption alone cannot repair Algorithm 4.","section":"Section III.A"},{"comment":"The accuracy guarantee for LinkEst is not self-contained. The proof in Appendix B assumes log p^{(path)}(k) is bounded (\"Assuming p^{(path)}(k) in (epsilon,1) for some parameter epsilon > 0\") and sub-Gaussian, but this condition is not stated in Lemma 3. The proof also delegates the key concentration argument to [18, Corollary 16] without verifying that the quantum benchmarking noise model satisfies the linear-bandit assumptions used there. In addition, the constant C_0 in the sample-complexity bound of Lemma 3 is left unspecified and is not related to the constant C in Lemma 1. These gaps make the claimed resource complexity in Theorem 4 impossible to verify from the manuscript.","section":"Lemma 3 and Appendix B"},{"comment":"Theorem 4, the central complexity result for BeQuP-Path, is stated without proof. The appendix says that detailed proofs will be provided in an extended version due to space limits; it contains only sketches for Lemmas 3 and 5. For a journal submission, the main theorem of the paper needs a proof in the manuscript. This is particularly important here because the algorithm itself appears to be undefined on the final iterations, so the proof cannot be a routine extension of known results.","section":"Section V.B and Appendix"}],"minor_comments":[{"comment":"The constant C in the concentration bound is said to depend on the bouncing number set M, the rounds T_0, and network parameters, but it is never quantified. Since C appears in the resource bounds of Theorems 2 and 4, the bounds remain asymptotic in an unspecified parameter; please state explicitly what C depends on or give a bound.","section":"Lemma 1"},{"comment":"The sentence \"which is avoidable according to the best arm identification literature [17]\" appears to say the opposite of what is intended. The text suggests that the sum over links is unavoidable, in which case \"unavoidable\" or \"cannot be removed\" would be the correct wording.","section":"Section IV.B"},{"comment":"LinkEst is called with S_h^{(1)} as the sampling set, while the empirical best path and pruning steps use S_h^{(s)}. Please clarify whether sampling from the initial outer-loop set is intentional and explain why that choice is sufficient for the pruning argument.","section":"Algorithm 4, Line 6"},{"comment":"The simulations report that all algorithms successfully identify the best path but do not report the empirical success probability, the confidence parameter delta used for the theoretical guarantees, or the number of trials over which success is measured. Without this information, the claim that the algorithms identify the best path is not fully quantified.","section":"Section VII"},{"comment":"Computing lambda^{(S)} requires solving a G-optimal design optimization problem over the path set S, but no algorithm or computational-cost bound is provided. This makes the simulation results harder to reproduce and the practical complexity of LinkEst incomplete.","section":"Algorithm 3, Line 1"}],"recommendation":"major_revision","confidential_remarks":"The paper has a useful problem formulation and a plausible link-level algorithm, but the path-level algorithm cannot be executed as written because LinkEst requires a full-rank design matrix while Algorithm 4 necessarily reaches candidate sets of size smaller than L. The authors should be asked to either redesign Algorithm 4 and LinkEst so that the matrix inversion is always well-defined, or clearly restrict the algorithm to phases where the candidate set is full-rank and justify the resulting complexity. If such a repair is possible, the paper could become acceptable after a careful revision; otherwise the contribution is limited to the link-level setting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, quick take: the paper's link-level algorithm is a solid, publishable result; the path-level algorithm is not executable as written. The stress-test note is correct, and it is worse than the reader's flagged full-rank assumption. Algorithm 4 calls LinkEst(S_h^(1), ...) on candidate sets that shrink below L paths during the halving process. Once |S| < L, the design matrix A = N * sum_{k in S} lambda(k) x(k) x(k)^T is necessarily singular (rank <= |S| < L), so A^{-1} in Algorithm 3 is undefined. The algorithm is designed to shrink the candidate set, so for L>1 you inevitably hit this state unless a single pruning step eliminates all but one path and skips further LinkEst calls; that is not guaranteed. Moreover, in the final h = ceil(log2 L) iteration the threshold floor(L/2^h) is 0, so the while loop never exits for a nonempty candidate set; for L=3 it calls LinkEst on a singleton forever. The WLOG rank-L assumption in Section III.A applies to the full X, not to subsets, and Lemma 3's proof is a verbatim delegation to Tao et al. [18, Corollary 16], whose full-rank design condition is precisely what fails.\n\nWhat is actually new and good: the problem formulation is sensible, and BeQuP-Link is a clean adaptation of elimination-based best-arm identification with a plausible proof and a resource bound O(L_max^2 sum 1/Delta^2 log(LH/delta)). The simulations, though limited to one topology and no code, do show the link-level algorithm outperforming baselines. If the paper is revised to fix the path-level part, the link-level contribution stands.\n\nMinor issues: Lemma 1's constant C is unspecified but inherited from prior work, fine; the appendix proof for Algorithm 2 is sketchy but recoverable. The path-level theorem, however, cannot hold for Algorithm 4 as written.\n\nWho should read: anyone working on online learning for quantum networks. The paper deserves a serious referee, but only with the expectation that the path-level algorithm either needs a substantial fix (e.g., only call LinkEst when |S| >= L and stop before the threshold reaches 0) or be removed. I would not cite it in its current form.","headline":"The link-level half is a real result; the path-level half is not executable as written because LinkEst is called on singular design matrices and the final loop can run forever.","tokens_in":19784,"tokens_out":7898,"would_cite":false,"duration_ms":89551,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Two algorithms learn the best quantum-network path with high probability, spending resources tied to link gaps rather than path count.","keywords":["quantum networks","best path identification","online learning","network benchmarking","fidelity estimation","secret key fraction","quantum resource complexity","multi-armed bandits"],"falsifier":"In a network where two links always appear together in every candidate path, the path-link matrix has dependent columns; running BeQuP-Path there should make the LinkEst inversion fail or produce estimates that cannot distinguish the two links, so the algorithm cannot certify a unique best path. This gives a direct experimental check of the full-rank premise.","tokens_in":18857,"feed_emoji":"⚛️","tokens_out":8459,"duration_ms":97478,"temperature":0.7,"pith_summary":"Quantum networks carry fragile quantum states, and applications like quantum key distribution need the route that preserves them best. This paper asks how to learn that best route online—benchmarking links or whole paths—while using as few quantum resources as possible. It proposes two algorithms: BeQuP-Link for networks that can inspect individual links, and BeQuP-Path for networks that can only inspect end-to-end paths. The central claim is that both find the best path with probability at least $1-\\delta$, with resource cost governed by the number of links and by how much the best path beats its rivals, rather than by the total number of candidate paths. If true, routing in large noisy quantum networks becomes learnable even when the path count is exponential in the network size.","feed_headline":"Two algorithms find best quantum path with high confidence","feed_subtitle":"Exploiting shared links keeps resource costs tied to link quality gaps, not the number of paths.","key_machinery":"The load-bearing identity is $F(k)=x(k)^\\top\\log p$, obtained by taking logarithms of the product rule $p^{(\\mathrm{path})}(k)=\\prod_{\\ell\\in L(k)}p_\\ell$; this turns the multiplicative path fidelity into a linear reward function over links, bringing the problem into the scope of linear best-arm identification. At link level, confidence radii on each link estimate define pessimistic and optimistic estimates that reveal whether the empirical best path could be beaten, and benchmarking the link with the largest radius in the symmetric difference terminates when no challenger remains. At path level, LinkEst builds the matrix $A=N\\sum_{k\\in S}\\lambda^{(S)}(k)x(k)x(k)^\\top$ and vector $b=\\sum_{n=1}^N\\log(Y_n)x(k_n)$ from path-level samples drawn by G-optimal design, then outputs $\\log\\hat{p}=A^{-1}b$; BeQuP-Path uses these link estimates in a halving candidate-set pruning loop. The quality of the estimates is controlled by the concentration of the network benchmarking subroutine, which gives a sub-Gaussian noise model for $\\log p$.","core_discovery":"On the paper's own terms, the central discovery is that best-path identification in a quantum network can be reduced to linear best-arm identification over links. The path depolarizing parameter satisfies $p^{(\\mathrm{path})}(k)=\\prod_{\\ell\\in L(k)} p_\\ell$, so taking logarithms gives a transformed fidelity $F(k)=x(k)^\\top\\log p$ that is linear in the link parameters and order-equivalent to the path fidelity. BeQuP-Link exploits this by maintaining confidence intervals on each link's $\\log p_\\ell$, benchmarking only links in the symmetric difference between the empirical best path and an optimistic challenger, and stopping when no challenger remains. BeQuP-Path handles the harder case where only end-to-end path benchmarks are available: a subroutine called LinkEst samples paths by a G-optimal design, solves a linear system to estimate $\\log p$ from path-level observations, and feeds these estimates into a candidate-set pruning loop that halves the path set in each outer round. The paper's theorems state that BeQuP-Link uses $O\\left(L_{\\max}^2 \\sum_{\\ell\\in L} \\Delta_\\ell^{-2}\\log\\left(\\frac{L}{\\delta}\\sum_{\\ell\\in L}\\Delta_\\ell^{-2}\\right)\\right)$ resources and BeQuP-Path uses $O\\left(L_{\\max}\\sum_{\\ell=2}^{L}(\\Delta^{\\mathrm{path}}_{[\\ell]})^{-2}\\log\\frac{K}{\\delta}\\right)$ resources, both identifying the best path with probability at least $1-\\delta$; the path-level bound depends on the top $L$ path gaps rather than on all $K$ paths.","pith_inferences":["A natural next step the paper leaves open is making the full-rank assumption constructive: for a rank-deficient incidence matrix, one would need to identify a subset of basis paths whose benchmarks determine all identifiable link combinations, and to prove the projection preserves the best path; the paper only asserts such a projection exists.","Since the link-level algorithm already avoids the $L_{\\max}^2$ factor by adaptive benchmarking, a path-level variant that replaces the fixed G-optimal batch with adaptive sampling could plausibly remove the linear $L_{\\max}$ factor from Theorem 4, improving the bound for long paths.","The log-linearization at the heart of the argument applies to any path metric that factors over links, such as entanglement generation rate or negativity, so the algorithmic template may transfer beyond fidelity and secret key fraction.","The dynamic counterpart, where network parameters drift over time, is not analyzed here, but the confidence-radius structure used by BeQuP-Link is the same structure used in non-stationary bandit algorithms, so a slowly-varying extension is a testable direction."],"forward_implications":["Under link-level benchmarking, the resource cost depends on $\\sum_{\\ell}1/\\Delta_\\ell^2$—a sum over links—rather than on the total number of paths $K$, so networks with exponentially many paths remain tractable.","Under path-level benchmarking, BeQuP-Path's cost is governed by the largest $L$ path gaps instead of all $K$ path gaps, improving on treating each path as an independent arm.","Both algorithms succeed with probability at least $1-\\delta$, so the confidence can be made arbitrarily high at a logarithmic price.","The same recipe works for quantum key distribution: maximizing secret key fraction $u(k)$ reduces to maximizing $\\sum_\\ell \\log((2p_\\ell+1)/3)$, and the same big-O resource bounds hold after adjusting the pruning threshold to $2\\epsilon$.","Simulations with several noise models show both algorithms output the correct best path and consume fewer quantum resources than uniform benchmarking or baselines that ignore path overlap."],"supporting_citations":[{"why":"Defines network benchmarking, the subroutine that estimates depolarizing parameters and supplies the fidelity–depolarizing model used throughout.","marker":"[8]"},{"why":"Gives the product rule for path depolarizing parameters and Werner parameters, the multiplicative structure that BeQuP linearizes by taking logs.","marker":"[14]"},{"why":"Provides the concentration bound in Lemma 1 and the LinkSelFiE algorithm whose resource complexity BeQuP-Path is compared against.","marker":"[15]"},{"why":"Supplies the linear-bandit best-arm identification technique that underlies Lemma 3's accuracy guarantee for LinkEst.","marker":"[18]"},{"why":"Contextualizes the resource complexity of link-level benchmarking via combinatorial pure exploration with additive rewards.","marker":"[17]"}],"fun_headline_variants":["Quantum pathfinding reduced to linear best-arm identification","BeQuP algorithms find optimal quantum route with minimal benchmarks","Efficient best-path learning in quantum networks from link and path feedback","Online learning pinpoints best quantum path with logarithmic overhead"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The path-level algorithm assumes that every link's contribution can be separated from the others using path-level measurements; if two links always appear together in every path, the estimate step cannot tell them apart, and the paper does not construct the projection it says would fix this.","fun_headline_variants_meta":{"raw":{"variants":["Quantum pathfinding reduced to linear best-arm identification","BeQuP algorithms find optimal quantum route with minimal benchmarks","Efficient best-path learning in quantum networks from link and path feedback","Online learning pinpoints best quantum path with logarithmic overhead"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"total_tokens":1550,"prompt_tokens":1110,"completion_tokens":440,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":726,"completion_tokens_details":{"reasoning_tokens":374}},"tokens_in":726,"tokens_out":440,"duration_ms":5591,"temperature":1.0,"reasoning_tokens":374,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:49:25.320614+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"In a network where two links always appear together in every candidate path, the path-link matrix has dependent columns; running BeQuP-Path there should make the LinkEst inversion fail or produce estimates that cannot distinguish the two links, so the algorithm cannot certify a unique best path. This gives a direct experimental check of the full-rank premise.","supporting_citations":[{"cited_title":"A benchmarking procedure for quantum networks,","cited_arxiv_id":null,"evidence_quote":"Defines network benchmarking, the subroutine that estimates depolarizing parameters and supplies the fidelity–depolarizing model used throughout."},{"cited_title":"LinkSelFiE: Link Selection and Fidelity Estimation in Quantum Networks,","cited_arxiv_id":null,"evidence_quote":"Provides the concentration bound in Lemma 1 and the LinkSelFiE algorithm whose resource complexity BeQuP-Path is compared against."},{"cited_title":"Best arm identification in linear bandits with linear dimension dependency,","cited_arxiv_id":null,"evidence_quote":"Supplies the linear-bandit best-arm identification technique that underlies Lemma 3's accuracy guarantee for LinkEst."},{"cited_title":"Combinatorial pure exploration of multi-armed ban- dits,","cited_arxiv_id":null,"evidence_quote":"Contextualizes the resource complexity of link-level benchmarking via combinatorial pure exploration with additive rewards."}],"review_version":1}