Discrete Quantum Walks with Marked Vertices and Their Average Vertex Mixing Matrices

Amulya Mohan; Hanmeng Zhan

REVIEW 1 major objections 4 minor 12 references

Discrete Quantum Walks with Marked Vertices and Their Average Vertex Mixing Matrices

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict Solid algebraic graph theory with a central formula that is dimensionally inconsistent as printed—fix the typesetting and this is a publishable paper. read the letter →

arxiv 2411.16676 v2 pith:DJKAROI7 submitted 2024-11-25 math.CO cs.DMquant-ph

Amulya Mohan , Hanmeng Zhan This is my paper · ORCID

classification math.COcs.DMquant-ph MSC 05C5005C8181P68

keywords discretequantumwalkaveragevertexmixingmatrixmarkedverticesGrovercoinregulargraphswalk-equitablepartitionsspectraldecompositionsearch

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

But 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.

There 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.

My 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.

Bring it to reading group? Maybe, if people want to see how spectral decompositions get used in walk bounds, but wait for the revision.

Referee Report

1 major / 4 minor

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).

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 (1)

[Abstract and Section 3] 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.

minor comments (4)

[Section 6, Lemma 6.2] 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.
[Global] 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 6, Lemma 6.2] 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.
[Global] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main formula and bounds are derived in-paper from standard linear-algebra lemmas; self-citations are background only.

full rationale

The paper's derivation chain is self-contained. Theorem 3.2 obtains the spectral decomposition of the transition matrix U by applying the standard two-projection lemma (Lemma 3.1, cited from the authors' textbook [6]) to P1=(I+R)/2 and P2=(1/k)D_t^T O_S D_t, together with incidence-matrix identities from [12]. These are background algebraic facts, not the paper's target result, and they do not presuppose the average vertex mixing matrix formula. Theorem 4.1 then derives the formula for the average vertex mixing matrix by expanding the contributions of each eigenprojection of U; the printed expression is obtained by explicit algebra from the identities (D_t + D_h)D_t^T = kI + A and the corresponding formulas for F_1 D_t^T, F_minus1 D_t^T, and F_plusminus_theta_r D_t^T. The later bounds in Theorems 6.4, 6.5, 7.1, 8.1, 8.4, and 9.1 are proven from Theorem 4.1 using Cauchy-Schwarz, Schur complements, and the spectral decomposition of the vertex-deleted subgraph; there are no fitted parameters or predictions that reduce to inputs by construction. The only self-citations are Lemma 2.1 from [12] and Lemma 3.1 from [6], both standard lemmas with stated assumptions that do not include the target formula; they are not load-bearing circularity under the rules. No step renames a known result or imports a uniqueness theorem as a forced choice. Any concern about the dimensional presentation of the block formula in Theorem 4.1 is a correctness or readability issue, not a circularity issue.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data. The only assumptions are standard graph-regularity and spectral facts. The paper introduces the combinatorial definition of walk-equitable collection, but that is a definition, not a postulated entity.

assumptions (5)

domain assumption The walk transition matrix U = R(2P_2 - I) is a product of two reflections, where P_1 = (I+R)/2 and P_2 = (1/k) D_t^T O_S D_t; this requires X to be k-regular.
Section 3 applies Theorem 3.1 from reference [6] to decompose eigenspaces; regularity is needed for the coin operator to be a projection P_2.
domain assumption X is connected and S is nonempty and proper, so L_S and Q_S are invertible and eigenvalues of A(X\S) lie strictly between -k and k by interlacing.
These invertibilities are used for the F_1 and F_-1 formulas in Theorem 3.2 and for the Schur complements in Theorem 6.4.
standard math Incidence matrix identities in Lemma 2.1 from reference [12] hold for the arc incidence matrices.
Used throughout Sections 2 and 3 to relate kernels of incidence matrices to eigenspaces of the walk.
standard math Spectral theorem and eigenprojection formalism for the symmetric transition matrix and for A(X\S).
Used to define the average vertex mixing matrix and to decompose M-hat into eigenspace contributions.
standard math Cauchy-Schwarz inequality and Schur complement rank, determinant, and positive semidefiniteness facts (Lemmas 6.1 and 6.3).
These yield the lower and upper bounds in Theorems 6.4 and 6.5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Discrete Quantum Walks with Marked Vertices and Their Average Vertex Mixing Matrices." pith.science (2026). https://pith.science/paper/DJKAROI7

@misc{pith2026241116676,
  author       = {Pith},
  title        = {Pith review of: Discrete Quantum Walks with Marked Vertices and Their Average Vertex Mixing Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DJKAROI7}},
  note         = {Machine review of arXiv:2411.16676}
}

abstract

We study the discrete quantum walk on a regular graph $X$ that assigns negative identity coins to marked vertices $S$ and Grover coins to the unmarked ones. We find combinatorial bases for the eigenspaces of the transtion matrix, and derive a formula for the average vertex mixing matrix $\AMM$. We then find bounds for entries in $\AMM$, and study when these bounds are tight. In particular, the average probabilities between marked vertices are lower bounded by a matrix determined by the induced subgraph $X[S]$, the vertex-deleted subgraph $X\backslash S$, and the edge deleted subgraph $X-E(S)$. We show this bound is achieved if and only if the marked vertices have walk-equitable neighborhoods in the vertex-deleted subgraph. Finally, for quantum walks attaining this bound, we determine when $\AMM[S,S]$ is symmetric, positive semidefinite or uniform.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[1]

Phys. Rev. A 103, 042222 (2021) - Quantum-walk-based state- transfer algorithms on the complete $M$-partite graph

work page 2021
[2]

Khosrovshah i, and Hamidreza Maimani, The kernels of the incidence matrices of graphs revisited, Linear Algebra and its Applications 414 (2006), no

Saieed Akbari, Narges Ghareghani, Gholamreza B. Khosrovshah i, and Hamidreza Maimani, The kernels of the incidence matrices of graphs revisited, Linear Algebra and its Applications 414 (2006), no. 2, 617– 625

work page 2006
[3]

4, 733–744 (en)

Chris Godsil, Controllable Subsets in Graphs , Annals of Combinatorics 16 (2012), no. 4, 733–744 (en). [4] , Average mixing of continuous quantum walks , Journal of Com- binatorial Theory, Series A 120 (2013), 1649–1662. 33

work page 2012
[5]

Chris Godsil and Jamie Smith, Strongly cospectral vertices , AUS- TRALAS. J. COMBIN. (2024) (en)

work page 2024
[6]

Chris Godsil and Hanmeng Zhan, Discrete quantum walks on graphs and digraphs, Cambridge University Press, 2023

work page 2023
[7]

Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96 (New York, New York, USA), ACM Press, 1996, pp. 212–219

1996
[8]

13-14, 1137– 1152, Publisher: Rinton Press Inc

Peter Høyer and Zhan Yu, Analysis of lackadaisical quantum walks , Quantum Information and Computation 20 (2020), no. 13-14, 1137– 1152, Publisher: Rinton Press Inc

work page 2020
[9]

5, 52307

Neil Shenvi, Julia Kempe, and K Whaley, Quantum random-walk search algorithm, Physical Review A 67 (2003), no. 5, 52307

work page 2003

Show all 12 references

[10]

1, 114196

Julien Sorci, Average mixing in quantum walks of reversible Markov chains, Discrete Mathematics 348 (2025), no. 1, 114196

2025
[11]

Wong, Quantum walk search on Johnson graphs , Journal of Physics A: Mathematical and Theoretical 49 (2016), no

Thomas G. Wong, Quantum walk search on Johnson graphs , Journal of Physics A: Mathematical and Theoretical 49 (2016), no. 19, 195303, arXiv: 1601.04212 Publisher: Institute of Physics Publishing

2016 arXiv
[12]

Hanmeng Zhan, $\epsilon$-Uniform Mixing in Discrete Quantum Walks, July 2024, arXiv:2311.18797

2024 arXiv
[13]

ˇStefaˇ n´ ak and S

M. ˇStefaˇ n´ ak and S. Skoup´ y,Perfect state transfer by means of discrete- time quantum walk search algorithms on highly symmetric gra phs, Phys- ical Review A 94 (2016), no. 2, 022301, Publisher: American Physical Society. 34

2016

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Phys. Rev. A 103, 042222 (2021) - Quantum-walk-based state- transfer algorithms on the complete $M$-partite graph

work page 2021

[2] [2]

Khosrovshah i, and Hamidreza Maimani, The kernels of the incidence matrices of graphs revisited, Linear Algebra and its Applications 414 (2006), no

Saieed Akbari, Narges Ghareghani, Gholamreza B. Khosrovshah i, and Hamidreza Maimani, The kernels of the incidence matrices of graphs revisited, Linear Algebra and its Applications 414 (2006), no. 2, 617– 625

work page 2006

[3] [3]

4, 733–744 (en)

Chris Godsil, Controllable Subsets in Graphs , Annals of Combinatorics 16 (2012), no. 4, 733–744 (en). [4] , Average mixing of continuous quantum walks , Journal of Com- binatorial Theory, Series A 120 (2013), 1649–1662. 33

work page 2012

[4] [5]

Chris Godsil and Jamie Smith, Strongly cospectral vertices , AUS- TRALAS. J. COMBIN. (2024) (en)

work page 2024

[5] [6]

Chris Godsil and Hanmeng Zhan, Discrete quantum walks on graphs and digraphs, Cambridge University Press, 2023

work page 2023

[6] [7]

Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96 (New York, New York, USA), ACM Press, 1996, pp. 212–219

1996

[7] [8]

13-14, 1137– 1152, Publisher: Rinton Press Inc

Peter Høyer and Zhan Yu, Analysis of lackadaisical quantum walks , Quantum Information and Computation 20 (2020), no. 13-14, 1137– 1152, Publisher: Rinton Press Inc

work page 2020

[8] [9]

5, 52307

Neil Shenvi, Julia Kempe, and K Whaley, Quantum random-walk search algorithm, Physical Review A 67 (2003), no. 5, 52307

work page 2003