pith. sign in

arxiv: 1907.01313 · v2 · pith:6VPGSLUPnew · submitted 2019-07-02 · 🧮 math-ph · math.MP· quant-ph

Mean hitting times of quantum Markov chains in terms of generalized inverses

Carlos F. Lardizabal This is my paper

Pith reviewed 2026-05-25 10:58 UTC · model grok-4.3

classification 🧮 math-ph math.MPquant-ph
keywords quantum Markov chainsmean hitting timesgeneralized inversesfundamental matrixopen quantum random walkscompletely positive mapsfirst visit timesGudder model
0
0 comments X

The pith

The quantum mean hitting time equals a formula built from the fundamental matrix of the chain.

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

The paper establishes formulas for the mean time to first reach a chosen vertex in a quantum Markov chain on a graph. These formulas are derived using generalized inverses of the transition map, with special focus on the fundamental matrix, rather than summing the definition directly. This approach mirrors the classical Markov chain theory and applies to systems modeled by completely positive maps, such as open quantum random walks. It enables explicit calculations for specific cases, highlighting both the shared structure and the unique features of the quantum setting. A reader would care if they want algebraic tools to compute these times without enumerating paths in quantum networks.

Core claim

Expressions for the quantum mean time of first visit to a chosen vertex can be obtained in terms of generalized inverses associated with the walk and most particularly the fundamental matrix. Such objects are in close analogy with the theory of Markov chains and the methods described here allow us to calculate examples that illustrate similarities and differences between the quantum and classical settings.

What carries the argument

The fundamental matrix, a generalized inverse of the quantum walk operator that encodes the mean hitting times in analogy to its role in classical Markov chains.

Load-bearing premise

The quantum dynamics must admit a completely positive map description for which the relevant generalized inverse exists and can be applied in the same way as the classical fundamental matrix.

What would settle it

Direct computation of the mean first-visit time from its probabilistic definition on a small graph, compared against the value from the fundamental matrix expression, showing a mismatch.

Figures

Figures reproduced from arXiv: 1907.01313 by Carlos F. Lardizabal.

Figure 1
Figure 1. Figure 1: Schematic illustration of quantum Markov chains. The walk is realized on a graph with a set of vertices denoted by i, j, k, l, . . . and each operator Φij is a completely positive map describing a transformation in the internal degree of freedom of the particle during the transition from vertex j to vertex i. For simplicity of illustration some edges are not labeled. In the particular case that all maps ar… view at source ↗
Figure 2
Figure 2. Figure 2: Graph with 2 vertices. In the block matrix Tb we have that the (i, j)-th order 4 block matrix equals the matrix representation [Bij ] = Bij ⊗ Bij for the conjugation Bij · B † ij = C · C † or B · B† which describes the possible transitions on such graph (Bij corresponds to the transition effect from vertex j to vertex i). The choice of matrices given for such example leads to an ergodic, unital OQW. The ei… view at source ↗
Figure 3
Figure 3. Figure 3: Graph with 2 vertices, with its associated transition maps Φij leading to an ergodic, nonunital QMC, for every 0 < p < 1. In general the mean hitting times for reaching a vertex depend on p and the initial density ρ. The exact values can be obtained by any of the methods discussed in the previous sections. Let Pi denote the projection on (the space generated by) vertex i, (8.3) P1 =  I4 04 04 04  , P2 = … view at source ↗
Figure 4
Figure 4. Figure 4: Complete graph with 3 vertices and associated transitions Bij from vertex j to vertex i, where i, j = 1, 2, 3. Examples 8.3a,b,c are all ergodic but only a and b are unital. a) Let B11 = B22 = B33 = 1 2  1 1 0 0 , B13 = B32 = B21 = 1 2  0 0 1 −1  B12 = B23 = B31 = 1 √ 2 I 18 [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
read the original abstract

We study quantum Markov chains on graphs, described by completely positive maps, following the model due to S. Gudder (J. Math. Phys. 49, 072105, 2008) and which includes the dynamics given by open quantum random walks as defined by S. Attal et al. (J. Stat. Phys. 147:832-852, 2012). After reviewing such structures we examine a quantum notion of mean time of first visit to a chosen vertex. However, instead of making direct use of the definition as it is usually done, we focus on expressions for such quantity in terms of generalized inverses associated with the walk and most particularly the so-called fundamental matrix. Such objects are in close analogy with the theory of Markov chains and the methods described here allow us to calculate examples that illustrate similarities and differences between the quantum and classical settings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript develops expressions for the mean time of first visit (hitting time) to a chosen vertex in quantum Markov chains on graphs, where the dynamics are given by completely positive maps in the sense of Gudder's model (including open quantum random walks of Attal et al.). Rather than using the direct definition, the authors derive closed-form expressions in terms of generalized inverses of the associated superoperator, with emphasis on the fundamental matrix, in direct analogy to classical Markov chain theory. The work reviews the model, defines the quantum hitting time, performs the algebraic derivation, and illustrates the results with examples that highlight similarities and differences with the classical setting.

Significance. If the derivations hold, the paper supplies a practical, matrix-based computational tool for quantum hitting times that mirrors the classical fundamental-matrix method, potentially simplifying calculations for open quantum walks and related CP-map dynamics. The explicit analogy and concrete examples are useful for clarifying quantum-specific features. The approach strengthens connections between classical stochastic processes and quantum information theory when the relevant generalized inverses exist.

major comments (2)
  1. [derivation of the hitting-time expression (following the model review)] The central derivation (abstract and the algebraic steps following the definition of the quantum hitting time) assumes that the classical-style manipulations with the fundamental matrix carry over without extra terms arising from non-commutativity of the CP map or the trace. The manuscript should explicitly verify the absence of commutator contributions in the final expression for the mean first-visit time.
  2. [model review and statement of the main results] Existence of the fundamental matrix (and other generalized inverses) for the superoperator is assumed throughout but not accompanied by sufficient conditions in the quantum CP-map setting (e.g., irreducibility or spectral properties of the map). This assumption is load-bearing for the claimed expressions and examples.
minor comments (2)
  1. Notation for the superoperator, the generalized inverse, and the fundamental matrix should be introduced with explicit comparison to the classical case to prevent reader confusion.
  2. The bibliography entries for Gudder (J. Math. Phys. 49, 072105, 2008) and Attal et al. (J. Stat. Phys. 147:832-852, 2012) should be checked for completeness and consistency with in-text citations.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: The central derivation (abstract and the algebraic steps following the definition of the quantum hitting time) assumes that the classical-style manipulations with the fundamental matrix carry over without extra terms arising from non-commutativity of the CP map or the trace. The manuscript should explicitly verify the absence of commutator contributions in the final expression for the mean first-visit time.

    Authors: We thank the referee for this observation. The derivation is performed entirely at the level of the superoperator acting on the space of operators, with all steps consisting of linear operations and the final application of the trace (which is linear). Consequently, no commutator terms arise. To make this explicit as requested, we will add a short verification remark immediately after the main theorem, confirming the absence of such contributions by direct expansion. This will be included in the revised manuscript. revision: yes

  2. Referee: Existence of the fundamental matrix (and other generalized inverses) for the superoperator is assumed throughout but not accompanied by sufficient conditions in the quantum CP-map setting (e.g., irreducibility or spectral properties of the map). This assumption is load-bearing for the claimed expressions and examples.

    Authors: We agree that the manuscript would benefit from an explicit discussion of conditions guaranteeing the existence of the fundamental matrix for CP-maps. While the examples satisfy the required spectral gap properties by construction, we will add a paragraph in the model review section outlining sufficient conditions drawn from the theory of quantum channels (such as uniqueness of the invariant state together with appropriate peripheral spectrum). This will clarify the applicability of the results. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algebraic derivation from external model

full rationale

The paper reviews the Gudder CP-map model (external citation) and Attal et al. open quantum walks, then derives closed-form expressions for quantum mean first-visit times via the fundamental matrix of the superoperator using standard generalized-inverse techniques. No step reduces the target quantity to a fitted parameter, self-definition, or load-bearing self-citation; the algebraic manipulations are presented as carrying over from the classical case without additional commutator terms being smuggled in. The derivation is self-contained against the stated assumptions and does not rename known results or import uniqueness theorems from the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the prior definition of quantum Markov chains via completely positive maps (Gudder model) and the existence of the generalized inverse; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Quantum Markov chains on graphs are described by completely positive maps following the Gudder model, which includes open quantum random walks.
    Stated in the abstract as the foundational structure under study.

pith-pipeline@v0.9.0 · 5679 in / 1153 out tokens · 19760 ms · 2026-05-25T10:58:14.138711+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages · 1 internal anchor

  1. [1]

    Accardi, D

    L. Accardi, D. Koroliuk. Quantum Markov chains: The recurrence problem. Quant. Prob. Rel. Top. VII, 63-73 (1991)

    work page 1991

  2. [2]

    Accardi, D

    L. Accardi, D. Koroliuk. Stopping times for quantum Markov chains. Journ. Th. Prob., Vol. 5, no. 3, pp 521-535, 1992

    work page 1992

  3. [3]

    Aldous, J

    D. Aldous, J. Fill. Reversible Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/∼aldous/RWG/book.html

    work page

  4. [4]

    Ambainis, E

    A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous. One-dimensional quantum walks, in: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 6069

    work page 2001

  5. [5]

    Ambainis

    A. Ambainis. Quantum walks and their algorithm applications. Int. Journ. Quant. Inf., Vol. 01, No. 4, p. 507-518 (2003)

    work page 2003

  6. [6]

    Attal, F

    S. Attal, F. Petruccione, C. Sabot, I. Sinayskiy. Open Quantum Random Walks. J. Stat. Phys. 147:832-852 (2012)

    work page 2012

  7. [7]

    Attal, N

    S. Attal, N. Guillotin-Plantard, C. Sabot. Central Limit Theorems for Open Quantum Random Walks and Quantum Measurement Records. Ann. Henri Poincar´ e 16 (2015), 15-43. 27

    work page 2015

  8. [8]

    Bardet, D

    I. Bardet, D. Bernard, Y. Pautrat. Passage times, exit times and Dirichlet problems for open quantum walks. J. Stat. Phys. 167, 173 (2017)

    work page 2017

  9. [9]

    Bourgain, F

    J. Bourgain, F. A. Gr¨ unbaum, L. Vel´ azquez, J. Wilkening. Quantum recurrence of a subspace and operator-valued Schur functions, Comm. Math. Phys., 329 (2014) 1031-1067

    work page 2014

  10. [10]

    Br´ emaud

    P. Br´ emaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues. Texts in Applied Mathematics 31. Springer, 1999

    work page 1999

  11. [11]

    H. P. Breuer and F. Petruccione. The Theory of Open Quantum Systems. Oxford University Press, Oxford, 2002

    work page 2002

  12. [12]

    S. L. Campbell, C. D. Meyer, Jr. Generalized inverses of linear transformations. Pitman, London, 1979

    work page 1979

  13. [13]

    Carbone, Y

    R. Carbone, Y. Pautrat. Open Quantum Random Walks: Reducibility, Period, Ergodic Properties. Ann. Henri Poincar´ e 17 (2016) 99-135

    work page 2016

  14. [14]

    Carbone, Y

    R. Carbone, Y. Pautrat. Homogeneous open quantum random walks on a lattice. J. Stat. Phys. (2015) 160:1125-1153

    work page 2015

  15. [15]

    S. L. Carvalho, L. F. Guidi, and C. F. Lardizabal. Site recurrence of open and unitary quantum walks on the line. Quantum Inf. Process. 16:17 (2017)

    work page 2017

  16. [16]

    Dhahri, F

    A. Dhahri, F. Mukhamedov, Open quantum random walks, quantum Markov chains and recurrence. Rev. Math. Phys. DOI: 10.1142/S0129055X1950020X

    work page doi:10.1142/s0129055x1950020x

  17. [17]

    Ellinas, C

    D. Ellinas, C. Konstandakis. Parametric quantum search algorithm by CP maps: algebraic, geometric and complexity aspects. J. Phys. A: Math. Theor. 46 (2013) 415303

    work page 2013

  18. [18]

    C. M. Grinstead, J. L. Snell. Introduction to probability. American Mathematical Society, 1997

    work page 1997

  19. [19]

    F. A. Gr¨ unbaum, L. Vel´ azquez. A generalization of Schur functions: applications to Nevanlinna functions, orthogonal polynomials, random walks and unitary and open quantum walks. Adv. Math. 326 (2018) 352-464

    work page 2018

  20. [20]

    F. A. Gr¨ unbaum, L. Vel´ azquez, A. H. Werner, R. F. Werner. Recurrence for Discrete Time Unitary Evolutions. Comm. Math. Phys. 320, 543-569 (2013)

    work page 2013

  21. [21]

    S. Gudder. Quantum Markov chains. J. Math. Phys. 49, 072105 (2008)

    work page 2008

  22. [22]

    S. Gudder. Analysis of a quantum Markov chain. Ann. Inst. Henri Poincar. Vol. 52, no. 1, 1990, p. 31-50

    work page 1990

  23. [23]

    R. A. Horn, C. R. Johnson. Topics in matrix analysis. Cambridge University Press, 1991

    work page 1991

  24. [24]

    J. J. Hunter. Generalized inverses and their application to applied probability problems. Lin. Alg. Appl. 45:157-198 (1982)

    work page 1982

  25. [25]

    Kassal, S

    I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, A. Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proc. Natl. Acad. Sci. 105 (48) 18681-18686 (2008)

    work page 2008

  26. [26]

    J. Kempe. Quantum random walks: An introductory overview. Cont. Phys., 44:4, 307-327 (2003)

    work page 2003

  27. [27]

    J. Kempe. Discrete Quantum Walks Hit Exponentially Faster. Prob. Th. Rel. Fields 133, 215-235 (2005)

    work page 2005

  28. [28]

    Kendon, B

    V. Kendon, B. Tregenna. Decoherence can be useful in quantum walks. Phys.Rev. A67, 042315 (2003)

    work page 2003

  29. [29]

    Kitagawa, M

    T. Kitagawa, M. S. Rudner, E. Berg, and E. Demler: Exploring topological phases with quantum walks, Phys. Rev. A, 82, 033429 (2010)

    work page 2010

  30. [30]

    N. Konno. A new type of limit theorems for the one-dimensional quantum random walk. J. Math. Soc. Japan Vol. 57, No. 4 (2005), 1179-1195

    work page 2005

  31. [31]

    Krovi, T

    H. Krovi, T. A. Brun. Quantum walks with infinite hitting times. Phys. Rev. A 74, 042334 (2006)

    work page 2006

  32. [32]

    K¨ ummerer, H

    B. K¨ ummerer, H. Maassen. A pathwise ergodic theorem for quantum trajectories. J. Phys. A Math. Gen. 37, 11889-11896 (2004)

    work page 2004

  33. [33]

    C. F. Lardizabal, R. R. Souza. On a class of quantum channels, open random walks and recurrence. J. Stat. Phys. (2015) 159:772-796

    work page 2015

  34. [34]

    C. F. Lardizabal, R. R. Souza. Open quantum random walks: ergodicity, hitting times, gambler’s ruin and potential theory. J. Stat. Phys. (2016) 164:1122-1156

    work page 2016

  35. [35]

    C. F. Lardizabal. Open quantum random walks and the mean hitting time formula. Quant. Inf. Comp. Vol. 17, No. 1&2 (2017) 79-105. ArXiv e-prints:1603.06255

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  36. [36]

    D. A. Levin, Y. Peres, E. L. Wilmer. Markov chains and mixing times. AMS, Providence, RI, 2009

    work page 2009

  37. [37]

    D Meyer, Jr

    C. D Meyer, Jr. The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains. SIAM Rev., Vol. 17, No. 3 (Jul., 1975), pp. 443-464

    work page 1975

  38. [38]

    M. A. Nielsen, I. L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000

    work page 2000

  39. [39]

    Pawela, P

    L. Pawela, P. Gawron, J. A. Miszczak, P. Sadowski. Generalized Open Quantum Walks on Apollonian Networks. PLoS ONE 10(7):e0130967 (2015)

    work page 2015

  40. [40]

    Portugal

    R. Portugal. Quantum walks and search algorithms. Springer, 2013

    work page 2013

  41. [41]

    Sadowski, L

    P. Sadowski, L. Pawela. Central limit theorem for reducible and irreducible open quantum walks. Quantum Inf. Process. (2016) 15:2725-2743

    work page 2016

  42. [42]

    S. E. Venegas-Andraca. Quantum walks: a comprehensive review. Quantum Inf. Process. (2012) 11:1015-1106

    work page 2012

  43. [43]

    Sinayskiy, F

    I. Sinayskiy, F. Petruccione. Efficiency of open quantum walk implementation of dissipative quantum computing algo- rithms. Quantum Inf. Process. (2012) 11:1301-1309

    work page 2012

  44. [44]

    Sinayskiy, F

    I. Sinayskiy, F. Petruccione. Microscopic derivation of open quantum Brownian motion: a particular example. Phys. Scr. T165 (2015) 014017

    work page 2015

  45. [45]

    Sinayskiy, F

    I. Sinayskiy, F. Petruccione. Open quantum walks. Eur. Phys. J. Spec. Top. DOI: 10.1140/epjst/e2018-800119-5

    work page doi:10.1140/epjst/e2018-800119-5

  46. [46]

    D. Sutter. Approximate Quantum Markov Chains. Springer (2018). 28

    work page 2018

  47. [47]

    Verstraete, M.M

    F. Verstraete, M.M. Wolf, J.I. Cirac. Quantum computation and quantum-state engineering driven by dissipation. Nat. Phys. 5, 633 (2009)

    work page 2009

  48. [48]

    G. Wang, Y. Wei, S. Qiao. Generalized inverses: theory and computations. Springer 2018. Instituto de Matem´atica e Estat´ıstica, Universidade Federal do Rio Grande do Sul - UFRGS. Av. Bento Gonc ¸alves 9500 - CEP 91509-900, Porto Alegre, RS, Brazil E-mail address : cfelipe@mat.ufrgs.br 29

    work page 2018