How to implement an Oracle

Question

Often when reading about QC algorithms the Authors assume the existence of an Oracle. I understand this is so that they can focus on the overall structure of the algorithm, and an Oracle can be seen as a subroutine that depends on the application. (One famous example is Grover's algorithm)

However, I imagine that if you were to try to implement one algorithm yourself for some applications, it would be necessary to assemble the oracle yourself for the algorithm to work. Thus, how do you do it? To make the question more specific I will refer to a particular one I am trying to implement: it's equation 41, 42 of Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing.

The idea is the following, Imagine you have an s-sparse matrix of which you know the entries, then they assume there exist an oracle that given the row $|j\rangle$, and column indices $|i\rangle$ returns the matrix entry:

\begin{equation} |j\rangle|i\rangle |z\rangle \rightarrow |j\rangle|i\rangle |z \oplus A_{ji}\rangle \end{equation}

where (I guess) the column and row indices are in binary notation. Moreover, imagine that I would like to implement a sparse matrix with the following shape (1 on two diagonals)

\begin{equation} A=\left[ \begin{array}{cccccc} 0 & 1 & 0 & 0 & \ldots & 0 \\ 1 & 0 & 1 & 0 & \ldots & 0 \\ . & & & & & . \\ . & & & & & 1 \\ 0 & 0 & 0 & \ldots & 1 & 0 \end{array} \right] \end{equation}

Thus, how do I build this oracle? I thought I could try to manually compute cases until I get a matrix, that is to say: I would take a few vectors that encode $|j\rangle$, $|i\rangle$ and try to manually assign values to a matrix that multiplied to those vectors would return either 1 or 0 depending on the indices I have chosen. For instance you if you pick $i,j=3,4$ then $A_{j,i}=1$, whereas it's 0 for $i,j=3,3$ and so on.

After trying different indices and matrix multiplication by hand I might be able to identify the shape of this matrix and successively try to guess the gates that would implement that operation. However, this seems time-consuming and I am not sure I can easily generalize it to an arbitrary sized matrix, and probably guessing the necessary gates from the matrix wouldn't be easy either.

Is there a smart way to proceed in this case, and is there a general strategy one uses to implement Oracles?

Answer 1

In general, you want to understand the process by which you compute the matrix elements if you were doing it by hand. In the example you give, for instance, you're effectively computing $|i-j|==1$. This has a classical algorithm which you can figure out, and there's your oracle.

In this specific instance there are probably some smarter things you can do. For instance, introduce the shift operator $T$ which does $T|i\rangle=|i+1\text{ mod N}\rangle$ on an $N$-dimensional system. By applying this to one system, you can then compare if the two systems are equal (basically, a Toffoli, but generalised to the $N$ dimensions). This gives one of the two off-diagonals. Then applying ${T^\dagger}^2$ to the same system undoes the effect and goes in the opposite direction so that comparing the systems again gives you the other off-diagonal. Then you probably just need to implement some special logic to take care of the periodic boundaries.

Answer 2

5.1 Implementation of oracles P_A and P_b (p. 13)

https://arxiv.org/pdf/1910.10649.pdf