Confusion about quantum walks and the quantum walk operator

Question

I am looking at the Quantum Signal Processing paper by GH Low and IL Chuang here. One step that they used was Child's quantum walks. They constructed a walk operator, $W \left | u_\lambda \right > = e^{i\theta_\lambda} \left | u_\lambda \right >$, from a Hamiltonian matrix $\hat{H}$, with two oracles $O_H$ and $O_F$. $O_H$ gives $\left < j \right | \hat{H} \left | k \right>$ where $j$ and $k$ are the row and column. $O_F$ gives the $l$th non-zero element of any row $j$.

My question is: What exactly do these oracles look like? For example, if I have a hamiltonian matrix

$ \begin{bmatrix} 2 & 3-2i & 2i \\ 3+2i & 3 & 6 \\ -2i & 6 & 5 \end{bmatrix} $

How would I calculate the oracles $O_H$ and $O_F$, and how would I use these to construct the quantum walk operator $W$?

Answer 1

For these problems we're not usually given a matrix that is small enough that we can write down explicitly, as is done in the question. Rather, these oracles $O_H$ and $O_F$ are most useful to consider when the Hermitian matrix is too large to write down, and instead we rely on these oracles to describe the sparse operator implicitly.

For example one operator that I like to think a lot about is the adjacency matrix $A$ of the Rubik's cube with quarter-turn or half-turn twists of each of the faces. This is a huge matrix! But, we can still have operators $O_H$ and $O_F$ defined in a straightforward and meaningful manner.

In more detail index the rows and columns of the adjacency matrix $A$ by one of the $43,252,003,274,489,856,000$ positions of the cube. Set entries $A_{jk}$ of the matrix to $1$ if there is a clockwise or counterclockwise rotation of one of the faces from position $j$ to position $k$, and set $A_{jk}$ to $0$ otherwise. This matrix has only $\{0,1\}$ entries and is symmetric about the diagonal; hence it is Hermitian and accordingly $\exp(-iAt)$ is unitary.

Such a matrix is very sparse - as most entries are $0$. Furthermore, given any two scrambles of the cube $j$ and $k$, we can quickly answer whether they are adjacent or not after a single twist of one of the faces; hence we have an oracle for $\langle k|A|j\rangle$. Additionally given any position of the cube $j$, we can just iterate through all of the twists to list all of the immediate neighbors to find the $l$th non-zero column in the matrix (in this case $l\le 18$, as there are $3\times 6=18$ twists that can conventionally be done).

It may also be helpful to think of these oracles $O_F$ and $O_H$ as procedures or subroutines that correspond to a sequence of instructions/sequence of gates which return the respective answer. For the Rubik's cube, the oracles themselves are not information-theoretically as large as a $43,252,003,274,489,856,000^2$ matrix; rather they encode the matrix itself in a much smaller form.

---

But, for the particular matrix in the question, we may have $O_H(2,2)=3$, because the entry of $\hat H_{2,2}=3$. Similarly, $O_F(3,2)=6$ because the second non-zero entry on the third row is $6$. But again the goal is not to explicitly describe the matrix and then construct the oracles; rather the goal is to implicitly describe a large matrix with the oracles, so as to avoid having to explicitly write down the matrix.