Details

Snapshot 1: The CTQW of the directed six-vertex cycle graph is shown. As the graph is directed, the Hamiltonian is non-Hermitian, and it can be seen that probability is not conserved.

Snapshot 2: This is the pseudo-Hermitian CTQW (-CTQW) of the same graph; by pseudo-Hermiticity, we can define a similarity transform to allow the walker probability to be conserved.

Snapshot 3: This shows the vertex centrality ranks of the graph using three different measures: (1) the classical PageRank; (2) the non-unitary CTQW; and (3) the unitary -CTQW.

Snapshot 4: This is similar to snapshot 3, however this time plotted on a line plot, with the axis sorted from vertices with highest PageRank (left) to vertices with lowest PageRank (right).

In a classical random walk, when a walker is on a vertex with possible edges to walk along, the walker flips an -sided coin to decide which of the edges to walk down. However, in a quantum walk, the walker utilizes quantum superposition to walk down all possible edges. This leads to markedly different properties to the classical walk, and the quantum walk is able to propagate through a graph quadratically faster than the classical walk [1]. In fact, the quantum walk has been shown to be a system of universal quantum computation—any quantum circuit can be reformulated as a quantum walk on a graph [2].

The continuous-time quantum walk on a graph is defined as follows. For a graph , composed of vertices and edges and with adjacency matrix , the Hamiltonian can be given by either or , depending on the convention preferred (this can be set in the Demonstration using the Hamiltonian radio buttons). Solving the Schrödinger equation, gives the formal solution , where is the initial state, and the state is given by the complex wavefunction . In this Demonstration, the initial state has been chosen to be an equal superposition of all vertices; .

If the graph is directed, then the adjacency matrix and the Hamiltonian become nonsymmetric and non-Hermitian. As a consequence, the time-evolution operator is no longer unitary (), causing the probability of the walker over time to blow up to infinity. As such, the standard CTQW is unsuited to walks on directed graphs. This can be seen from the Demonstration by viewing plots of the CTQW for a directed graph, for example, the graph .

One solution explored here comes in the form of PT-symmetry [3]. Graphs that exhibit PT-symmetry, while still non-Hermitian and non-unitary, will have real eigenvalues. This results in a total probability that oscillates with time—this can be seen by choosing an example of a PT-symmetric graph from the drop-down box in the Demonstration. In order to ensure the probability remains constant with time, we can utilize the "pseudo-Hermiticity" of these graphs by finding an operator such that , where is Hermitian yet retains information about the structure of the graph. This is known as a pseudo-Hermitian CTQW [4], or -CTQW for short, and can be viewed by clicking the "Pseudo-Hermitian -CTQW" tab.

Finally, we compare the vertex centrality ranking of the graph vertices using the CTQW, -CTQW, and the classical PageRank algorithm. For the CTQW and -CTQW, this is done simply by using the time-average probability for each vertex. The PageRank algorithm was created by Google for ranking their search results; it finds the fixed points of the so-called Google matrix, defined by , where is the column normalized adjacency matrix, and is generally chosen to be 0.85. In this Demonstration, you can view the vertex rankings in a line plot or a bar chart, and reorder the plots based on each ranking algorithm. In the toolbar, there is also a slider allowing you to change the value of used in the PageRank algorithm.

References

[1] J. Kempe, "Quantum Random Walks: An Introductory Overview", Contemporary Physics, 44(4), 2003 pp. 307–327. doi:10.1080/00107151031000110776.

[2] A. M. Childs, "Universal Computation by Quantum Walk," Physical Review Letters, 102(18), 2009. doi:10.1103/PhysRevLett.102.180501.

[3] C. M. Bender and S. Boettcher, “Real Spectra in Non-Hermitian Hamiltonians Having PT Symmetry,” Physical Review Letters, 80(24), 1998 pp. 5243–5246. doi:10.1103/PhysRevLett.80.5243.

[4] J. Izaac, J. B. Wang, P. C. Abbott, and X. S. Ma, "Quantum Centrality Testing on Directed Graphs via PT-Symmetric Quantum Walks", 2016. arxiv.org/abs/1607.02673.

[5] S. Brin and L. Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine," Computer Networks and ISDN Systems, 30(1–7), 1998 pp. 107–117. doi:10.1016/S0169-7552(98)00110-X.