3
$\begingroup$

Suppose I have a list of numbers from 0 to 32, that is $ [0,1,2....31, 32].$ I want to find a number $n$ in this list such that it satisfies a property, say $n$ is prime. How would I translate this to an Oracle that can be used with Grovers's Algorithm in Qiskit?

I am following this guide but, it seems like the general pattern to the solution is already known in this Sudoku example, that is the pattern of the bits of a potential solution is known and it can be checked.

What if there isn't a general pattern? How would you implement an oracle to look through the list, check each item and return the one that matches some criteria?

I'm following the same code in the link referenced above but, changing the sudoku_oracle to my own custom function.

Any help is appreciated, thanks.

Improve this question
$\endgroup$
2
$\begingroup$

Per your link, the trick is to create a unitary matrix that satisfies $$U|x\rangle=(-1)^{f(x)}|x\rangle.$$ This can work for any arbitrary function, but you'll have to do the work for all possible inputs $x$ and actually figure out what each value of $f(x)$ will be if you want to physically implement $U$. The function $f(x)$ is restricted to return $0$ if $x$ is not a solution (in your case, if $x$ is not a prime number) and $1$ if $x$ is a solution (in your case, if $x$ is a prime number).

In your example, we could write $U$ in the computational basis as a diagonal matrix of the form \begin{equation}\begin{aligned}U&=\text{Diag}((-1)^0,(-1)^0,(-1)^1,(-1)^1,(-1)^0,(-1)^1,(-1)^0,(-1)^1,(-1)^0,(-1)^0,\cdots)\\ &=\text{Diag}(1,1,-1,-1,1,-1,1,-1,1,1,\cdots).. \end{aligned}\end{equation} The whole point is that you first have to know which of the integers is prime before you can construct the oracle $U$ that helps you search for it. You can't use the algorithm to simplify the compution of $f(x)$, so it will never help you determine the value of an unknown function.

This is true regardless of whether $f(x)$ follows a pattern. You simply must know all the values of the function for all possible inputs if you wish to construct the oracle for Grover's algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the insight, I've received this suggestion of using a unitary matrix from someone else as well. My follow up question is, how would one ensure the matrix is indeed unitary and reversible? Otherwise Qiskit will fail to use it. I suppose we can follow the $U_f(x, h) = (x , h \oplus f(x))$ principle to make any $f(x)$ reversible, but, I'm not sure what this would look like in Qiskit. $\endgroup$
    – Shazil Arif
    Nov 29 '21 at 3:30
  • 1
    $\begingroup$ @ShazilArif good catch, I forgot to make the elements of $U$ be $(-1)^{f(x)}$ - these ensure that $U$ is always unitary because it has elements with magnitude $1$ on the diagonal and nothing else. $\endgroup$
    – Quantum Mechanic
    Nov 29 '21 at 14:25

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.