Graph
embedding using quantum hitting time
(pp0231-0254)
David
Emms, Richard Wilson, and Edwin Hancock
doi:
https://doi.org/10.26421/QIC9.3-4-4
Abstracts: In this paper, we explore
analytically and experimentally a quasi-quantum analogue of the hitting
time of the continuous-time quantum walk on a graph. For the classical
random walk, the hitting time has been shown to be robust to errors in
edge weight structure and to lead to spectral clustering algorithms with
improved performance. Our analysis shows that the quasi-quantum analogue
of the hitting time of the continuoustime quantum walk can be determined
via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre
quadrature. We analyse the quantum hitting times with reference to their
classical counterpart. Specifically, we explore the graph embeddings
that preserve hitting time. Experimentally, we show that the quantum
hitting times can be used to emphasise cluster-structure.
Key words:
Continuous time quantum walk, commute time, graph
embedding |