# How do we compute quantum walks for a graph?

I am reading Childs' paper on discrete and continuous quantum walks. I do not really understand why quantum walks are useful--- as implementing the quantum walk operator requires knowing the principal eigenvector of a Hamiltonian (The eigenvector with eigenvalue equal to the norm of the Hamiltonian).

The paper does mention this:

However, it is straightforward to implement the walk for many cases of interest, such as for an unweighted regular graph.

But it is confusing to me. What is the graph meant to represent in this case? The Hamiltonian? If not the Hamiltonian, how could we simulate Hamiltonian evolution using this unweighted regular graph method. And how would we construct the walk operator from this?

The graph is the Hamiltonian I think.

I'll start off by saying I only understand portions of Childs' paper and I am far from familiar with graph theory, much less spectral graph theory - much of what's below may be wrong or misplaced. But, just some thoughts:

• Adjacency matrices $$A$$ of an unweighted, undirected, $$d$$-regular graph $$G$$ are Hermitian: entries are all either $$\{0,1\}$$ because they are unweighted, and further they are symmetric about the diagonal because they are undirected.
• These matrices may be normalized to correspond to a stochastic transition matrix.
• The spectral properties of this transition matrix control the dynamics of a (classical) random walk - in particular, the adjacency matrix controls the discrete-time walk, while similar spectral properties of the Laplacian matrix $$\mathcal L=dI-A$$ controls the continuous-time walk.
• It's noteworthy also that a continuous-time classical walk is given by the diffusion equation, while the continuous-time quantum walk is given by the Schrödinger equation.
• Recall also the Perron-Frobenius theorem which puts a lot of constraints on the largest eigenvalue. Indeed up to some degeneracy I think it may be the case that the dominant eigenvector - the one corresponding to the eigenvalue given by the Perron-Frobenius theorem - of an undirected, unweighted, $$d$$-regular graph is the principal eigenvector. But, for such graphs the eigenvector is uniformly distributed over all vertices I think, because the stationary distribution of such graphs is uniform.
• Reading Childs' paper further it's also suggestive that the walk is provided when the graph is implicitly defined - meaning that one has oracular access to entries in the matrix. Here, Childs refers to row-computable and index-computable graphs, which I take to mean oracles/subroutines for accessing various entries in $$A$$.

If the graph isn't connected then there might be some degeneracies, and I don't know what to say about those. But then again a classical discrete-time random walk on an unconnected graph also wouldn't converge to uniform because there's no way to walk form one connected component to another.

• Thank you so much, this answer lead me to some pretty good sources. If I understand correctly, the case of unweighted regular graphs allows us to implicitly define a Hamiltonian (using the $O_H$ and $O_F$ oracles). Using these oracles, we can construct the T isometry without actually needing the principal eigenvector? If so, how would we implicitly define this type of graph? And are there any other cases like it? (Childs hints to more in the quote I put in my question, but didn't provide any examples to my knowledge) Commented Oct 2, 2022 at 0:35
• I don't know what's meant by T isometry - sorry! Also I think that Childs' reference to the P-F theorem in the paper seems to imply that he's equating the principal eigenvector to the Perron-Frobenius eigenvector... sorry, can't help much more! Commented Oct 2, 2022 at 0:43