{"id":"b219cb56-2bb4-40d0-b808-f980a16f991b","arxiv_id":"2608.03777","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"For bridge weight w=M, a continuous-time quantum walk on the simplex of complete graphs finds a marked vertex with 80% probability in O(sqrt(N)) time, the first analytical proof of optimal search on this graph, while numerics extend optimality to w>=sqrt(M).","lead":"This paper studies a quantum walk searching a special network of linked cliques, the simplex of complete graphs, where the bridges between cliques have adjustable strength. It proves optimal search time for one bridge strength and, mostly by numerical simulation, charts which strengths make search fast, deterministic, or both.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3's analytic proof omits second-order H'(1) corrections that enter at the same O(1/M) order as the splitting it computes, so the w=M claim is not rigorously established.","rationale":"The paper's headline contribution is an analytical proof of optimal search at w=M; the numerical sections are explicitly numerical and are not the central proof. I therefore treated Section 3 as the load-bearing part. The derivation obtains two eigenvectors and an energy splitting from a 2x2 matrix in a specially chosen basis, after discarding H'(1) from the effective Hamiltonian. The discarded terms are not obviously negligible: H'(1)'s matrix elements in the degenerate subspace vanish, but its couplings to |b'>, |d'>, and |e'> are gamma sqrt(M), and the H'(0) energy denominators for those intermediate states are O(1) because the relevant H'(0) eigenvalues are of order unity near gamma M = 2/3. Hence second-order H'(1) corrections are O(1/M), the same order as the H'(2) off-diagonal term that produces the O(1/M) splitting and the O(sqrt(N)) runtime. Without a bound showing these corrections are smaller, the derivation of |psi_0>, |psi_1>, Delta E, and the 0.8 success probability is incomplete. This matches the reader's weakest assumption. The paper has strong numerical convergence in Tables 3 and related checks, and the conclusion may well be correct, so this does not warrant rejection. But the analytic claim is not yet fully established. I keep the reader's CONDITIONAL verdict; the proposed Schur-complement check would either supply the missing asymptotic estimate or reveal a real flaw in the proof.","tokens_in":27828,"tokens_out":13480,"duration_ms":146578,"concrete_test":"At w=M and gamma = gamma_{w=M} from Eq. (7), compute the exact 7D Schur complement of H' restricted to P = span{|g'>, |ac>} for M = 10^6, 10^8, 10^10: H_eff = P H' P - P H' Q (Q H' Q - E0)^-1 Q H' P. Compare the diagonal and off-diagonal entries with the 2x2 matrix used in Section 3. If H_eff differs by a relative amount that does not tend to 0 as M grows, or if the resulting success probability at t = pi sqrt(5)/4 sqrt(N) deviates from 0.8 by a nonvanishing amount, the perturbation truncation is invalid and the analytic proof fails. If H_eff matches the paper's matrix to O(1/M^2), the concern is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3's proof of the w=M result rests on a truncated degenerate perturbation calculation. After the change of basis, H' is split into H'(0), H'(1), H'(2) with matrix entries scaling as M, sqrt(M), and constants before the overall -gamma factor. The paper then solves a 2x2 problem in the degenerate subspace span{|g'>,|ac>} using only H'(0)+H'(2) in the matrix above Eq. (9). This truncation is not justified. The relevant eigenvalues of H'(0) at the critical gamma are O(1), not O(M): for gamma M ~ 2/3, the a-c block has eigenvalues near -4/3 and +1/3, and the b-e and d-f blocks have eigenvalues near 0.41 and -1.08. Thus the energy denominators in a Schur-complement treatment are O(1). H'(1) has matrix elements of size gamma sqrt(M) = O(1/sqrt(M)) connecting the degenerate subspace to |b'>, |d'>, and |e'>. Their first effect appears at second order, of size (gamma sqrt(M))^2 / O(1) = O(1/M). This is the same order as the off-diagonal matrix element from H'(2), which is -3 gamma / sqrt(5) = O(1/M), and the same order as the resulting splitting Delta E ~ 4/(sqrt(5) M). Omitting these second-order H'(1) terms can change the effective 2x2 Hamiltonian by O(1) relative corrections. The statement that 'H'(2) behaves as the first-order correction' is therefore an assertion, not a consequence of the scaling decomposition. The numerical agreement in Table 3 supports the conclusion, but it does not supply the missing analytical bound needed for the claimed 'first analytical proof'.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies continuous-time quantum walk search on the weighted simplex of complete graphs, a graph with M+1 cliques of M vertices and bridge weight w. The authors' central analytical result is the case w=M: by changing to a seven-dimensional basis and applying degenerate perturbation theory, they derive the critical jumping rate gamma=(2M-3)/(3(M-1)(M-3)), Eq. (7), and show that the system evolves from the uniform state to |ac>=(2|a>+|c>)/sqrt(5) in time t=pi sqrt(5) sqrt(N)/4, giving an 80% success probability and O(sqrt(N)) runtime. The remaining sections numerically map the behavior for other bridge weights: w=sqrt(M) gives 50% |a> and 50% |b>; sqrt(M) << w << M gives asymptotically deterministic search at pi sqrt(N)/2 time; w >> M gives 50% |a> and 50% |c> at pi sqrt(N/2) time; and w>=sqrt(M) is claimed to be optimal, though not always deterministic. The paper also proposes a neighbor-inspection procedure for nondeterministic regimes and argues that algebraic connectivity is not a reliable predictor of search speed within this graph family.","tokens_in":28426,"tokens_out":8672,"duration_ms":102784,"significance":"If the w=M derivation is made rigorous, the paper would deliver the first analytical proof of optimal continuous-time quantum search on the simplex of complete graphs, improving on earlier numerical results (36% and 75% success probabilities) and providing an explicit 80% success probability with a closed-form runtime. The paper also provides a useful numerical map of the search behavior across bridge weights, an extension of known two-stage results, and a practical neighbor-inspection strategy. The explicit formulas for gamma and the runtime, together with numerical tables up to M=10^10, are valuable and appear to strongly support the qualitative claims. The main weakness is that the analytic proof in Section 3 rests on an unproved perturbation truncation, and the broader 'optimal whenever w>=sqrt(M)' and 'deterministic when sqrt(M)<<w<<M' conclusions are extrapolated from finite numerical fits without error estimates.","major_comments":[{"comment":"The w=M proof is not yet rigorous. The authors split H' = H'(0)+H'(1)+H'(2) and then solve a 2x2 problem in span{|ac>,|g'>} using only H'(0)+H'(2), stating that H'(2) 'behaves as the first-order correction' because H'(1) does not perturb the two degenerate eigenvectors directly. However, H'(1) has off-diagonal elements of size gamma sqrt(M) = O(1/sqrt(M)) coupling the degenerate subspace to |b'>, |d'>, and |e'>. At the critical gamma, the relevant H'(0) gaps in those channels are O(1), so second-order virtual processes through H'(1) contribute at order (gamma sqrt(M))^2 / O(1) = O(1/M). This is the same order as the H'(2) matrix element -3 gamma / sqrt(5) = O(1/M) and the same order as the computed splitting Delta E = 4/(sqrt(5) M). Omitting these terms can change the effective 2x2 Hamiltonian by O(1) relative corrections. The sentence 'H'(2) behaves as the first-order correction' is the","section":"Section 3, display before Eq. (9)"},{"comment":"The numerical determination of the critical jumping rate in the non-w=M regimes is not accompanied by uncertainty estimates or convergence tests. For each example, gamma is obtained by locating the crossing |<s|psi_0>|^2 = |<s|psi_1>|^2 and then fitting an ad-hoc inverse-power series. For w=M^{3/4}, Table 9 supplies only 13 support points to fix 9 coefficients; for w=M^{7/8}, Table 11 uses 99 points but the fit has 17 terms and no reported residuals. The coefficients are rounded to integers without justification. Since the abstract and Fig. 2b claim behavior over entire regimes (e.g., 'optimal whenever w>=sqrt(M)' and 'deterministic when sqrt(M)<<w<<M'), these are extrapolations beyond the sampled exponents. I recommend that the authors report fit residuals, confidence intervals, and an explicit statement distinguishing numerically established facts from conjectures. This does not invali","section":"Sections 4-7, Tables 5,7,9,11"},{"comment":"The claim that the algorithm is deterministic for all weights between sqrt(M) and M is supported only by three example exponents, w=M^{5/8}, M^{3/4}, and M^{7/8}. While these are representative, the paper provides no proof, or even a numerical scan, that the behavior is uniform over the continuous interval. The same issue applies to the claim in the introduction that optimality holds for every w>=sqrt(M); Fig. 3 uses only a discrete set of alpha values. The authors should temper these statements to 'numerically supported at the sampled values' or provide an argument (even heuristic) that the properties are monotone or continuous in w. This is proportionate because the abstract presents these as general results.","section":"Abstract and Section 6"}],"minor_comments":[{"comment":"The header says 'at time t_{w=\\sqrt{M}}' but the section is about w=M^{3/4}; should be 'at time t_{w=M^{3/4}}'.","section":"Table 10"},{"comment":"The text refers to 'Fig. 18' when discussing w=M^2, but the relevant figure is Fig. 20.","section":"Section 7.3"},{"comment":"The linear combination is written with |g>, but the degenerate subspace is span{|ac>,|g'>}. Clarify the notation to avoid confusion between the unprimed and primed basis states.","section":"Eq. (8) and surrounding text"},{"comment":"The paper states that the primed basis was found 'by trial and error.' This is not an error, but the presentation would be improved by explaining the construction or at least providing the intuition in a more structured way, since the basis choice is central to the calculation.","section":"Section 3"},{"comment":"The term 'deterministic' is used for a success probability that tends to 1 asymptotically. Please define this terminology explicitly in Section 1 to avoid confusion with exact probability 1 for finite N.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The w=M result is the key contribution, and the paper's title and abstract lean heavily on the word 'analytical.' The perturbation truncation in Section 3 is the load-bearing step, and without a rigorous error bound the claim of a first analytical proof is premature. The numerical work is extensive and plausible, but it should be framed as numerical evidence rather than as proof of the full w-regime claims. If the authors can supply the missing perturbation bound, I would view the paper as suitable for publication in QIP."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the analytical treatment at w=M: an exact critical jumping rate, an 80% success probability, and an O(sqrt(N)) runtime derived from an eigenvector computation. The basis change is clever (even if found by trial and error), and the numerical verification up to M=10^10 is convincing evidence that 80% really is the asymptotic value. The broad numerical phase diagram from w=1 to w=M^2, with the deterministic window sqrt(M)<<w<<M, is useful, and the neighbor-inspection trick works for the nondeterministic regimes. Credit where due: this advances the state of the art for spatial search on this graph family.\n\nThe soft spot is exactly where the stress-test note lands. The paper splits H' into parts scaling as M, sqrt(M), and constants, then solves a 2x2 problem using only the M and constant parts. But at the critical gamma, the unperturbed eigenvalues are O(1), not O(M), so the energy denominators are order one. Second-order effects from the sqrt(M) part therefore enter at O(1/M) — the same order as the off-diagonal matrix element from the constant part that produces the splitting. The statement that H'(2) behaves as the first-order correction is an assertion, not a consequence of the scaling hierarchy. The numerics support the conclusion, but the paper is not a rigorous proof of the w=M result as written. A referee should ask for a genuine bound on the neglected second-order terms, or a softened claim that the result is a high-confidence asymptotic prediction with strong numerical support.\n\nThe other regimes are openly numerical: critical gamma values are fitted, coefficients are rounded to integers, and there is no error analysis or code. That is acceptable for a map of behavior, but it should not be oversold. To the paper's credit, it is honest about its own limitations — it admits the basis was found by trial and error and that the remaining sections are numerical.\n\nWho is this for? Researchers in quantum walk spatial search. It deserves a serious referee. The flagship proof needs work, but the paper is a substantive contribution with a plausible central claim and a lot of useful numerical structure.\n\nRecommendation: send to peer review, with a request for either a rigorous perturbation estimate at w=M or a revised claim that matches what is actually established.","headline":"The w=M result is a real step forward, but the 'proof' has a perturbation-theory gap at the same order as the effect it computes; still worth refereeing.","tokens_in":28806,"tokens_out":2319,"would_cite":true,"duration_ms":28752,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.-a","03.67.Ac"],"model":"deepseek-v4-flash","headline":"The paper proves that when the bridge weight equals M, a continuous-time quantum walk on the simplex of complete graphs reaches the marked vertex with probability 0.8 in O(sqrt(N)) time, giving the first analytical proof of optimal search o","keywords":["continuous-time quantum walk","spatial search","weighted graph","simplex of complete graphs","truncated simplex lattice","degenerate perturbation theory","optimal quantum search","graph connectivity"],"falsifier":"Numerically diagonalize the exact seven-dimensional Hamiltonian at w=M and compute the second-order corrections to the 2x2 energy gap through all sqrt(M)-order off-diagonal couplings; if any neglected correction is O(1/M) rather than o(1/M), the 80% peak will drift as M grows. The direct check is whether the gap converges to 4/(sqrt(5)M) fast enough that the time pi*sqrt(5)M/4 remains the peak.","tokens_in":1914,"feed_emoji":"🔎","tokens_out":2232,"duration_ms":155835,"temperature":0.7,"pith_summary":"This paper asks how fast a continuous-time quantum walk can find a marked vertex on the simplex of complete graphs, a network of M+1 cliques of M vertices with N=M(M+1) vertices total. The central result is a proof: at bridge weight M and hopping rate gamma=(2M-3)/(3(M-1)(M-3)), the walker provably evolves from the uniform state to a state that is 80% marked vertex and 20% its neighbor in time pi*sqrt(5)*sqrt(N)/4, which is O(sqrt(N)). Previous work on this graph could show optimal runtime numerically or deterministic success analytically, but not both in the same algorithm. The paper also maps the full range of bridge weights numerically: weights at least sqrt(M) give optimal runtime, weights strictly between sqrt(M) and M give both optimal runtime and deterministic success, and in nondeterministic regimes, measuring and checking neighbors within O(sqrt(N)) extra queries locates the marked vertex. Along the way it shows that spectral connectivity measures are not a reliable predictor of search speed even within this single graph family.","feed_headline":"Proof: weighted simplex search hits 80% in optimal time","feed_subtitle":"Bridge weight M gives O(sqrt(N)) quantum search with measured 80% success on the marked vertex.","key_machinery":"The load-bearing object is the 2x2 degenerate subspace spanned by |g'> and |ac> inside a seven-dimensional symmetry-adapted basis, with the Hamiltonian split by scaling order. At w=M the leading-order Hamiltonian makes these two states degenerate at the critical hopping rate; the sqrt(M)-order terms leave them degenerate, and the constant-order term produces the energy splitting Delta E approximately 4/(sqrt(5)M). That gap sets the oscillation time pi/Delta E, giving the O(sqrt(N)) runtime, and the eigenvector |ac> sets the 80/20 measurement split. The primed change of basis is the enabling device: it creates the direct |g'>-|a> and |g'>-|c> couplings that the degenerate perturbation theory","core_discovery":"At w=M, the search Hamiltonian H=-gamma*A-|a><a| is reduced by symmetry to seven basis states, then transformed to a primed basis. Splitting the transformed Hamiltonian into terms scaling as M, sqrt(M), and constants, the two leading eigenvectors |g'> (approximately the starting state) and |ac>=(2|a>+|c>)/sqrt(5) become degenerate at gamma=(2M-3)/(3(M-1)(M-3)). The sqrt(M)-order terms leave the degeneracy, while the constant-order term splits it by an energy gap Delta E approximately 4/(sqrt(5)M). As a result, |s> rotates to |ac> in time pi*sqrt(5)*M/4, approximately 1.756*sqrt(N), and measurement gives the marked vertex with probability 0.8 and its clique neighbor c with probability 0.2. Th","pith_inferences":["The primed-basis construction, found by trial and error, is likely reusable: applying the same M/sqrt(M)/constant decomposition at w=M^(3/4) could upgrade the deterministic optimal regime from numerical to analytic, which the paper leaves open.","The threshold at w=sqrt(M), separating suboptimal O(N^(3/4)) from optimal O(sqrt(N)) search, looks like a phase transition in the effective two-level dynamics; proving it analytically would explain why the final state switches among |b>, |a>, and mixed |a>/|c> branches.","If the weight-window design rule is general, the same optimal-and-deterministic window should appear on higher-order truncated simplex lattices and for Laplacian-based quantum walk search; that is a direct testable extension of the paper's numerics."],"forward_implications":["At w=M, with gamma=(2M-3)/(3(M-1)(M-3)), the algorithm is analytically proven to return the marked vertex with probability 0.8 in time pi*sqrt(5)*sqrt(N)/4.","Any bridge weight w at least sqrt(M) gives optimal O(sqrt(N)) runtime with success probability at least 50%, so repeating the walk or measuring and checking neighbors keeps the overall search optimal.","For weights strictly between sqrt(M) and M, such as w=M^(3/4), the walk is asymptotically both optimal and deterministic, reaching the marked vertex with probability approaching 1 in time pi*sqrt(N)/2.","In nondeterministic regimes, measuring the walker and then checking the found vertex and its clique, or following the bridge from the c vertex, locates the marked vertex within O(sqrt(N)) extra queries.","Neither algebraic connectivity nor normalized algebraic connectivity reliably predicts search speed within the weighted simplex of complete graphs; around w=M connectivity rises while the algorithm slows down."],"supporting_citations":[{"why":"Quantum search algorithm whose O(sqrt(N)) query bound is the baseline used throughout.","marker":"[1]"},{"why":"Establishes the O(sqrt(N)) lower bound that makes the achieved runtime optimal.","marker":"[2]"},{"why":"Introduces the continuous-time quantum walk search Hamiltonian H=-gamma*A-|a><a| used here.","marker":"[5]"},{"why":"Introduces the simplex of complete graphs, its seven-dimensional symmetry subspace, and the unweighted two-stage search.","marker":"[17]"},{"why":"Defines the weighted graph, derives the w << sqrt(M) two-stage results and connectivity formulas that this paper extends and refines.","marker":"[19]"},{"why":"Previous numerical study of w=M search whose approximate jumping rate and 36%/75% probabilities are improved by the analytic proof.","marker":"[20]"},{"why":"Supplies the degenerate perturbation theory used to compute the splitting at w=M.","marker":"[29]"},{"why":"Source of the change-of-basis technique used to set up the degenerate perturbation calculation.","marker":"[10]"}],"fun_headline_variants":["First analytic proof of optimal quantum search on complete-graph simplex","Optimal quantum search on simplex lattices: now analytically proven","On simplex of complete graphs, optimal search now has analytic proof","Simplex search optimal and deterministic for bridge weights between sqrt(M) and M","Quantum search on complete-graph simplex optimal and deterministic for some weights"],"cache_read_input_tokens":30336,"weakest_assumption_plain":"The load-bearing premise is that the truncated perturbation calculation, keeping only the leading, next-to-leading, and constant terms and only the two important states, becomes exact as the number of vertices grows, so neglected couplings cannot shift the 80% success probability.","fun_headline_variants_meta":{"raw":{"variants":["First analytic proof of optimal quantum search on complete-graph simplex","Optimal quantum search on simplex lattices: now analytically proven","On simplex of complete graphs, optimal search now has analytic proof","Simplex search optimal and deterministic for bridge weights between sqrt(M) and M","Quantum search on complete-graph simplex optimal and deterministic for some weights"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002562,"raw_usage":{"total_tokens":9692,"prompt_tokens":836,"completion_tokens":8856,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":8766}},"tokens_in":580,"tokens_out":8856,"duration_ms":77809,"temperature":1.0,"reasoning_tokens":8766,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:44:27.455687+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically diagonalize the exact seven-dimensional Hamiltonian at w=M and compute the second-order corrections to the 2x2 energy gap through all sqrt(M)-order off-diagonal couplings; if any neglected correction is O(1/M) rather than o(1/M), the 80% peak will drift as M grows. The direct check is whether the gap converges to 4/(sqrt(5)M) fast enough that the time pi*sqrt(5)M/4 remains the peak.","supporting_citations":[{"cited_title":"In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC ’96, pp","cited_arxiv_id":null,"evidence_quote":"Quantum search algorithm whose O(sqrt(N)) query bound is the baseline used throughout."},{"cited_title":"Fortschr","cited_arxiv_id":null,"evidence_quote":"Establishes the O(sqrt(N)) lower bound that makes the achieved runtime optimal."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the continuous-time quantum walk search Hamiltonian H=-gamma*A-|a><a| used here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the simplex of complete graphs, its seven-dimensional symmetry subspace, and the unweighted two-stage search."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the weighted graph, derives the w << sqrt(M) two-stage results and connectivity formulas that this paper extends and refines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Previous numerical study of w=M search whose approximate jumping rate and 36%/75% probabilities are improved by the analytic proof."},{"cited_title":"Prentice Hall (2005)","cited_arxiv_id":null,"evidence_quote":"Supplies the degenerate perturbation theory used to compute the splitting at w=M."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the change-of-basis technique used to set up the degenerate perturbation calculation."}],"review_version":1}