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$?


1 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.

  • $\begingroup$ Hi, thank you for such a good answer. I am just confused on two things. 1. Do we assume the Hamiltonian is described using these oracles? For example, in QSP, why can we assume that the person using the algorithm has access to these oracles if they are hard to compute. 2. Will the oracles not be $n \times n$ where n is the dimension of the matrix? Because it still needs to encode all the data points. In your rubik's cube example, each state can compute the next state (adjacent states), but how would that be done for indices in a Hamiltonian matrix? $\endgroup$
    – Loic Stoic
    Sep 22 at 23:23
  • $\begingroup$ Updated answer but briefly, yes the Hamiltonian could be described with the oracles, and the oracles are assumed to be easy to compute. You can think of the oracles as just snippets of code that succinctly encode or describe the entire matrix. $\endgroup$
    – Mark S
    Sep 23 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.