I'm trying to implement Grover's algorithm in pyQuil, but I'm having trouble creating the oracle matrix given the function $f$, where $f(x)=1$ if $x=w$ and $f(x)=0$ otherwise. In most of the implementations I've seen, either a mysterious oracle function is called or the matrix representation is created using the knowledge of the index, which requires classical computation of all the $f(x)$ values, defeating the purpose of Grover search.

Can someone show me exactly how to create in the matrix (in say pyQuil) when writing the algorithm from scratch without classically computing all of the $f(x)$ values?


1 Answer 1


For most functions $f(x)$, there is nothing better than calculating all the values. After all, for most functions, there is no better way of defining the function than giving its truth table.

Probably, you want to talk about the relatively small fraction of cases in which the function $f(x)$ has some reasonably compact description. In that case, you should be able to design a classical circuit for its implementation. If you can do that, you can make the implementation reversible. And, once you've done that, it's no problem programming that reversible implementation into a quantum computer to act in the place of your oracle. And the whole point of Grover's search is to minimise the number of calls to the oracle, and hence minimise the number of times the function is evaluated.

At this point, some philosophical questions may arise, some of which were discussed here. Particularly regarding search, remember that the function would not typically be defined by having the marked item programmed into it directly, just that the function can run and recognise the marked item. You can think of this a bit like factoring. If I give you a large composite number of factor, you can run some code to determine if a particular integer is a factor or not. It doesn't mean that the code you've written already knows what the factors are.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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