{"id":"3354c7f5-1961-47c7-8176-712841dd46cf","arxiv_id":"2411.16676","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For discrete quantum walks with Grover coins on unmarked vertices and negative identity coins on marked vertices, the paper derives closed-form expressions and tight bounds for the average vertex mixing matrix.","lead":"This paper derives exact formulas for the long-run average probability that a discrete quantum walk with marked vertices moves between vertices of a regular graph. The formulas tie that probability to the graph's spectral structure and show exactly when a lower bound on marked-to-marked movement is achieved.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's printed formula is dimensionally inconsistent as written, so the central closed-form result cannot be verified or applied without a rewrite and a numerical check.","rationale":"I read the paper in good faith and find its overall architecture sound: the spectral correspondence in Theorem 3.2 is standard, the combinatorial bases in Section 2 are plausible, and the walk-equitable bound in Theorem 6.4 is a natural application of the Cauchy-Schwarz lemma. The reader's weakest assumption, that regularity and a nonempty proper S make L_S and Q_S invertible, is correct by interlacing and is not the place where the argument is most exposed. The most load-bearing issue is that the central formula in Theorem 4.1 is printed with incompatible block dimensions. The proof text suggests a specific W-matrix derivation, and the formula likely becomes coherent after transposing H or swapping the block indexing, but as typeset the theorem cannot be numerically checked or applied. Because all later bounds are stated in terms of this formula, any user of the paper must first resolve this ambiguity. The proposed numerical test on K_3 and K_2 will settle whether the discrepancy is purely typographical (in which case the reader's CONDITIONAL verdict stands with a more pointed correction) or reflects a substantive error (in which case the verdict should fall). Until that test is run, I do not see grounds to strengthen or weaken the verdict beyond the reader's conditional acceptance.","tokens_in":17741,"tokens_out":24676,"duration_ms":203570,"concrete_test":"Re-derive Theorem 4.1's expression by following the proof's W matrices (not the printed block layout) for the 3-cycle with one marked vertex. Form U = R((2/k)D_t^T O_S D_t - I), compute its eigenprojectors numerically, and evaluate \\hat M_{u,v} = (1/k)e_u^T D_t \\sum_\\theta ((F_\\theta D_t^T e_v) \\circ (F_\\theta D_t^T e_v)). Compare with the closed form, testing both H = A(S,\\bar S) and H = A(\\bar S,S), with L_S and Q_S relabeled accordingly. Repeat for X = K_2. If no orientation reproduces the direct computation, the theorem is false as stated; if a transposition fixes it, the correct verdict is CONDITIONAL on a corrected statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"With H = A(S,\\bar S) of size s x \\bar s and G_r an eigenprojection of A(X\\S) of size \\bar s x \\bar s, the formula for \\hat M_r in Theorem 4.1 is \\hat M_r = 1/(2(k^2-\\lambda_r^2)) [kH, (k^2-2\\lambda_r^2)I + k A_S] [(1/(k^2-\\lambda_r^2))(G_rH^T)^{\\circ2}; G_r^{\\circ2}]. The first block product kH (G_rH^T)^{\\circ2} is s x s; the second ((k^2-2\\lambda_r^2)I + k A_S) G_r^{\\circ2} is \\bar s x \\bar s; these cannot be added, and the two entries of the block column have s and \\bar s columns, so the vertical stack is not a matrix. Similarly, \\hat M_1 contains H(L_S^{-1}H^T)^{\\circ2}, which is undefined for s x \\bar s H and s x s L_S (inner dimension s vs \\bar s). Either H is transposed or the roles of S and \\bar S are swapped in the typesetting. Since Theorem 4.1 feeds every later bound (Theorems 6.4, 6.5, 7.1, 8.1, 8.4 and 9.1), this ambiguity is load-bearing: the central closed form cannot be checked, applied, or trusted as printed. The reader's named weakest assumption (regularity and nonempty proper S) is actually secure by interlacing; the real risk sits in the formula's block structure, not in the spectral-separation hypothesis.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the discrete quantum walk on a k-regular connected graph X in which marked vertices in S receive the negative identity coin and unmarked vertices receive the Grover coin. The transition matrix is U = R((2/k)D_t^T O_S D_t - I). The authors establish a spectral correspondence between U and the adjacency matrix of the vertex-deleted subgraph X\\S (Theorem 3.2), give explicit combinatorial bases for the +1 and -1 eigenspaces (Theorems 3.3 and 3.4), and derive a closed-form expression for the average vertex mixing matrix \\hat M in terms of the blocks of A and the spectral decomposition of A(X\\S) (Theorem 4.1). They then prove lower and upper bounds for the [S,S]-block of \\hat M (Theorems 6.4 and 6.5), characterize equality via walk-equitable collections, classify when \\hat M[S,S] is symmetric, positive semidefinite, or uniform (Theorems 8.1 and 8.4), and give a lower bound for the [\\bar S,\\bar S]-block (Theorem 9.1).","tokens_in":18066,"tokens_out":28796,"duration_ms":221265,"significance":"If the results are correct, the paper provides a fairly complete spectral theory for this family of marked-vertex discrete quantum walks, connecting the average mixing matrix to the partition structure of the graph. The introduction of walk-equitable collections as the tightness condition is a neat and useful contribution. The proofs are detailed and largely self-contained after standard background results, and the main structural result (Theorem 3.2) is a significant step. The paper also makes falsifiable predictions, for example the equality condition in Theorem 6.4 and the characterization in Theorem 9.1, which is a strength. However, the central formula in Theorem 4.1 suffers from serious notational ambiguities, and no numerical verification is included, so the closed form cannot currently be checked or applied without substantial interpretation.","major_comments":[{"comment":"The abstract claims that the paper finds combinatorial bases for the eigenspaces of the transition matrix, but explicit {0,\\pm1}- or {0,\\pm1,\\pm2}-bases are given only for the 1-eigenspace and the -1-eigenspace (Theorems 3.3 and 3.4). For the non-real eigenspaces, the paper only states an isomorphism from the eigenspaces of A(X\\S) and does not construct a combinatorial basis. The abstract should be tempered, or the missing bases for the non-real eigenspaces should be supplied.","section":"Abstract and Section 3"}],"minor_comments":[{"comment":"The displayed formula for F_{-1}D_t^T uses (D_t - D_h)^T, but Theorem 3.2(ii) and the surrounding derivation require (D_t + D_h)^T. This appears to be a sign typo that should be corrected.","section":"Section 6, Lemma 6.2"},{"comment":"The notation for the blocks of A and L is inconsistent throughout; for example, Section 4 writes A = (AS H; H^T AS) with identical symbols for the two diagonal blocks, and later the same symbol L_S is used for both L[S,S] and L[\\bar S,\\bar S]. A uniform notation with explicit bars or calligraphic letters is needed.","section":"Global"},{"comment":"In the upper bound H(G_rH^T)^{\\circ2} \\le HG_r^{\\circ2}H^T\\Delta(S,S), the rightmost factor should presumably be \\Delta(S,\\bar S), consistent with the proof and with Theorem 6.5. As printed, the statement is dimensionally suspect.","section":"Section 6, Lemma 6.2"},{"comment":"There are many typos and grammatical slips, including \"transtion\" in the abstract, \"sumed limit\", \"outgoign\", \"Consequencely\", \"simiar\", \"conncted\", \"oppostive\", and \"marices\". A careful proofreading pass is needed.","section":"Global"}],"recommendation":"major_revision","confidential_remarks":"The mathematical program appears sound in outline, but the notational collapse in Theorem 4.1 is a real obstacle to verification. I would encourage the authors to run a small explicit example (for instance, a cycle with one marked vertex) through the formula and report the resulting matrix, both to confirm the dimensions and to catch any residual sign errors. The paper is within scope for a combinatorics journal with an interest in quantum walks; the connection between average mixing and equitable partitions is a genuine contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on the Mohan-Zhan paper. The core contribution is real: they give a spectral decomposition for the Shenvi-Kempe-Whaley walk on regular graphs with marked vertices, derive a formula for the average vertex mixing matrix, and prove tight bounds characterized by walk-equitable neighborhoods. That's a useful advance for the discrete-walk literature, which has mostly focused on Szegedy walks or continuous time. The derivation is self-contained, uses standard facts, and has no fitted parameters. The interlacing argument that makes L_S and Q_S invertible is solid.\n\nBut the paper as printed has a load-bearing problem: Theorem 4.1's formula is dimensionally inconsistent. In \\hat M_1, the term H(L_S^{-1}H^T) is undefined because H is s x \\bar s, L_S^{-1} is s x s, and H^T is \\bar s x s; the inner dimensions don't match. Similarly, the block column in \\hat M_r stacks a matrix with s columns on top of one with \\bar s columns. The stress-test note is right that the central closed form cannot be checked or applied as written. From the proof sketch, the intended expressions appear to be H^T L_S^{-1} rather than L_S^{-1}H^T, and some L_S's should probably be L_{\\bar S}. If that's the case, the mathematical skeleton is probably still sound, but as it stands, every later theorem that quotes this formula inherits the ambiguity. This is more than a cosmetic typo; it's an unverifiable central result.\n\nThere are also smaller issues: the abstract's claim of 'combinatorial bases for the eigenspaces' is only demonstrated for the ±1 spaces, not for the non-real ones. Corollary 4.4 has swapped labels. The paper needs careful proofreading.\n\nMy bottom line: this deserves a serious referee, but the verdict should be 'major revision' rather than any kind of quick accept. The authors need to rewrite the formula with correct block structure, state the exact dimensions, and ideally add a small numerical example checking \\hat M on a concrete graph. Once that's done, I'd expect the main results to hold up. I would not cite the current version, but I'd be happy to cite a corrected one.\n\nBring it to reading group? Maybe, if people want to see how spectral decompositions get used in walk bounds, but wait for the revision.","headline":"Solid algebraic graph theory with a central formula that is dimensionally inconsistent as printed—fix the typesetting and this is a publishable paper.","tokens_in":18587,"tokens_out":9833,"would_cite":false,"duration_ms":74923,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C81","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves an exact, closed-form expression for the average vertex mixing matrix of a discrete quantum walk that uses negative identity coins on marked vertices and Grover coins elsewhere, and shows that the lower bound on average…","keywords":["discrete quantum walk","average vertex mixing matrix","marked vertices","Grover coin","regular graphs","walk-equitable partitions","spectral decomposition","quantum search"],"falsifier":"On a 6-cycle with vertices 0 and 2 marked, construct the transition matrix \\(U\\) from the reflection product, time-average the walk from each marked vertex to obtain a numerical \\(\\hat{M}[S,S]\\), and compare it with the right-hand side of Theorem 6.4; because these marked vertices' neighborhoods are not walk-equitable in the unmarked subgraph, the theorem predicts strict inequality, so equality would falsify the tightness claim.","tokens_in":125,"feed_emoji":"🎯","tokens_out":8643,"duration_ms":142238,"temperature":0.7,"pith_summary":"This paper studies a discrete quantum walk on a regular graph where marked vertices act with a negative identity coin and all other vertices use the Grover coin, a setup common in quantum search algorithms. It derives an exact, closed-form formula for the average vertex mixing matrix, the time-averaged matrix of transition probabilities between vertices, using only the graph's adjacency matrix, the spectral decomposition of the unmarked induced subgraph, and the edge structure between marked and unmarked vertices. This turns a limiting simulation problem into a spectral calculation. The paper then bounds the average probabilities between marked vertices from below and above; the lower bound is attained exactly when the marked vertices' neighborhoods form a walk-equitable collection in the unmarked subgraph, and in that tight case it characterizes when the marked block is symmetric, positive semidefinite, or uniform.","feed_headline":"Closed-form average found for marked-vertex quantum walks","feed_subtitle":"The long-run transition odds are pinned by the unmarked subgraph's spectrum, with tightness tied to walk-equitable neighborhoods.","key_machinery":"The central machinery is the reflection-product form \\(U = R(2P_2 - I)\\) with \\(P_2 = \\frac{1}{k}D_t^T O_S D_t\\), which lets the eigenspaces of \\(U\\) be read from intersections of column spaces and kernels of incidence matrices for the \\(\\pm 1\\)-eigenspaces, and from the spectrum of the vertex-deleted subgraph \\(A(X\\setminus S)\\) for the non-real eigenvalues. The formula for \\(\\hat{M}\\) is carried by the Schur-square inequality \\((BN)^{\\circ 2} \\le (I\\circ BB^T) B $N^{{\\circ 2}}$\\), a Cauchy-Schwarz bound whose equality case is exactly the walk-equitable condition, and by Schur complements such as \\(L'/L_S\\) and \\(Q'/Q_S\\), which rearrange the averaged transition probabilities into the stated bounds.","core_discovery":"The central claim is that the average vertex mixing matrix of this walk decouples into contributions from the two real eigenspaces and from each spectral projection of the vertex-deleted subgraph. Theorem 4.1 expresses \\(\\hat{M}\\) as \\(\\hat{M}_1 + \\hat{M}_{-1} + \\sum_r \\hat{M}_r\\), where each \\(\\hat{M}_r\\) is built from the \\(r\\)-th eigenprojection \\(G_r\\) of \\(A(X\\setminus S)\\), its eigenvalue \\(\\lambda_r\\), the adjacency block \\(H\\) between marked and unmarked vertices, and the Laplacian and signless Laplacian matrices of the marked block. Theorem 6.4 then bounds \\(\\hat{M}[S,S]\\) below by a matrix made from \\(Q(X[S])\\), Schur complements of Laplacian and signless Laplacian matrices of the edge-deleted graph \\(X-E(S)\\), and Schur squares of spectral projections, with equality if and only if the marked vertices have walk-equitable neighborhoods in \\(X\\setminus S\\). For walks attaining that bound, the paper further determines when \\(\\hat{M}[S,S]\\) is symmetric, positive semidefinite, or uniform.","pith_inferences":["Because Theorem 4.1 reduces the long-run behavior to the spectrum of \\(X\\setminus S\\), the formula should make numerical estimation of search-walk probabilities much cheaper on graphs whose vertex-deleted subgraph has a known closed-form spectrum, such as strongly regular or distance-regular graphs; this is an extension the paper does not explicitly test.","The tightness condition suggests a design rule for quantum search on regular graphs: mark a set whose neighborhoods in the unmarked subgraph form a walk-equitable collection, since then the lower bound on marked-to-marked average probability is attained and the walk's escape behavior is as simple as possible.","The walk-equitable notion is introduced for vertex subsets, but the same Schur-square machinery could plausibly be adapted to edge subsets or to weighted regular graphs, potentially linking these bounds to equitable partitions of directed or weighted graphs.","The paper's bounds identify when \\(\\hat{M}[S,S]\\) is symmetric or uniform, but leave open the analogous question for the full matrix or for the unmarked block; one could test numerically on small regular graphs whether similar degree-separating conditions appear there."],"forward_implications":["For any initial vertex in the unmarked set, the \\(\\pm 1\\)-eigenspaces contribute nothing to \\(\\hat{M}\\), so the walk's long-run vertex distribution is controlled entirely by the spectral projections of the unmarked subgraph.","If the marked set is a vertex cut, \\(\\hat{M}_{uv}=0\\) for vertices in different components of \\(X\\setminus S\\), meaning the walk never transfers probability between those components.","Two unmarked vertices that are strongly cospectral in \\(X\\setminus S\\) produce identical average probability distributions over the vertices.","When the lower bound is tight, \\(\\hat{M}[S,S]\\) is symmetric if and only if \\(S\\) is degree-separating in \\(X\\setminus S\\), and it is uniform only in the very special case of two marked vertices on an odd cycle or a bipartite graph with neighborhood-strongly-cospectral marked vertices.","For a single marked vertex, the average return probability has explicit lower and upper bounds in terms of the spectral decomposition of \\(X\\setminus a\\), with the lower bound tight exactly when all walks from neighbors of \\(a\\) to its neighborhood have equal counts."],"supporting_citations":[{"why":"Supplies the reflection-product spectral lemma that determines the eigenspaces of \\(U\\) and the Cesàro-average limit expressing \\(\\hat{M}\\) through eigenprojections.","marker":"[6]"},{"why":"Provides the incidence-matrix identities involving arc reversal, signed incidence, and the tail and head incidence matrices used to identify the \\(\\pm 1\\)-eigenspaces.","marker":"[12]"},{"why":"Gives the \\(\\{0,\\pm 1,\\pm 2\\}\\)-basis for \\(\\ker(B)\\) that is extended to a basis for \\(\\ker(B_S)\\) and hence to the \\((-1)\\)-eigenspace of \\(U\\).","marker":"[2]"},{"why":"Defines strong cospectrality, which Corollary 4.2 uses to show that strongly cospectral unmarked vertices produce identical average distributions.","marker":"[5]"},{"why":"Introduces walk matrices, which the paper uses to characterize walk-equitable collections in Lemma 5.2 and Corollary 5.4.","marker":"[3]"},{"why":"Introduces the discrete walk with negative identity coins on marked vertices and Grover coins on unmarked vertices, the model under study.","marker":"[9]"},{"why":"Introduces the average vertex mixing matrix that the paper computes and bounds.","marker":"[10]"}],"fun_headline_variants":["Marked-neighborhood symmetry dictates quantum walk averages","Quantum walk averages tied to walk-equitable neighborhoods","Tight bound on marked-vertex quantum walk mixing found","Closed-form average reveals quantum walk neighborhood condition","Uniformity and symmetry of quantum walk averages characterized"],"cache_read_input_tokens":20608,"weakest_assumption_plain":"The load-bearing premise is that the graph is connected and regular with a nonempty, proper marked set, because then the unmarked subgraph's eigenvalues lie strictly between \\(-k\\) and \\(k\\) and the matrices inverted in the formula exist.","fun_headline_variants_meta":{"raw":{"variants":["Marked-neighborhood symmetry dictates quantum walk averages","Quantum walk averages tied to walk-equitable neighborhoods","Tight bound on marked-vertex quantum walk mixing found","Closed-form average reveals quantum walk neighborhood condition","Uniformity and symmetry of quantum walk averages characterized"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00019,"raw_usage":{"total_tokens":1344,"prompt_tokens":954,"completion_tokens":390,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":318}},"tokens_in":570,"tokens_out":390,"duration_ms":4947,"temperature":1.0,"reasoning_tokens":318,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:51:19.328131+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a 6-cycle with vertices 0 and 2 marked, construct the transition matrix \\(U\\) from the reflection product, time-average the walk from each marked vertex to obtain a numerical \\(\\hat{M}[S,S]\\), and compare it with the right-hand side of Theorem 6.4; because these marked vertices' neighborhoods are not walk-equitable in the unmarked subgraph, the theorem predicts strict inequality, so equality would falsify the tightness claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the reflection-product spectral lemma that determines the eigenspaces of \\(U\\) and the Cesàro-average limit expressing \\(\\hat{M}\\) through eigenprojections."},{"cited_title":"$\\epsilon$-Uniform Mixing in Discrete Quantum Walks","cited_arxiv_id":"2311.18797","evidence_quote":"Provides the incidence-matrix identities involving arc reversal, signed incidence, and the tail and head incidence matrices used to identify the \\(\\pm 1\\)-eigenspaces."},{"cited_title":"Khosrovshah i, and Hamidreza Maimani, The kernels of the incidence matrices of graphs revisited, Linear Algebra and its Applications 414 (2006), no","cited_arxiv_id":null,"evidence_quote":"Gives the \\(\\{0,\\pm 1,\\pm 2\\}\\)-basis for \\(\\ker(B)\\) that is extended to a basis for \\(\\ker(B_S)\\) and hence to the \\((-1)\\)-eigenspace of \\(U\\)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines strong cospectrality, which Corollary 4.2 uses to show that strongly cospectral unmarked vertices produce identical average distributions."},{"cited_title":"4, 733–744 (en)","cited_arxiv_id":null,"evidence_quote":"Introduces walk matrices, which the paper uses to characterize walk-equitable collections in Lemma 5.2 and Corollary 5.4."},{"cited_title":"5, 52307","cited_arxiv_id":null,"evidence_quote":"Introduces the discrete walk with negative identity coins on marked vertices and Grover coins on unmarked vertices, the model under study."},{"cited_title":"1, 114196","cited_arxiv_id":null,"evidence_quote":"Introduces the average vertex mixing matrix that the paper computes and bounds."}],"review_version":1}