Grover's Algorithm uses a black box gate that can recognize an x such that $f(x) = 1$ for a certain function f. It inverts this x and leaves all other inputs unchanged. My question is about the construction of such a gate. For example, for a database search application, the function is often represented as a diagonal matrix with a $-1$ at a certain position, which represents the position that needs to be found by the algorithm. But when constructing such a matrix we already need to know the position that we want to find, defeating the purpose of the algorithm. Is there a smart way to construct these gates without already knowing the solution?
A trivial implementation of a Grover's-algorithm oracle is a controlled Z gate involving every wire:
The highlighted gate flips the amplitude of the $|010001111\rangle$ state, and nothing else. (The Hadamards are just surrounding context. Part of Grover's algorithm, but not part of the oracle.)
Of course no one would use Grover's algorithm to figure out the "grand mystery" of which state the highlighted gate above flips. But we can always make more complicated circuits!
Which state does this circuit flip?:
That oracle is permuting, phase-flipping exactly one state, then unpermuting. What single input state did it end up flipping? It's a bit harder to figure out by hand this time, but Grover's algorithm doesn't care how complicated the circuit is.
The above circuit is easily solved by starting from the 111111 state and applying the uncomputation. An oracle circuit that's actually difficult to solve would use ancilla bits that aren't part of the big-controlled-Z in the middle. Once you have ancilla bits, any classical circuit can be turned into a Grover oracle circuit. Including classical circuits that compute things like "Is the input a solution to the 3-SAT instance?" and "Is the input a valid proof of the Riemann hypothesis?".
(If you want to apply the simplest form of Grover's algorithm, then you need to know that the circuit only has one satisfying solution. But there are ways to avoid that problem.)
What you are worried about is known as the problem of constructing the oracle function. It has been proven that a usable oracle can be constructed in polynomial time. The simplest way of doing this is just to use a classical algorithm to check whether a given entry matches what you are searching for; this is the same check that would need to be made in a completely classical search. What is slightly tricky is setting up the check stage so that it works using reversible quantum gates, so that it can work within the larger quantum algorithm devised by Grover. This too can be done, although doing it practically is a somewhat nasty problem.
This excellent blog post discussed the practicalities of constructing a working oracle for Grover's algorithm.
A different approach that does not apply a factor of -1 to any except a match follows:
libquantum 1.0.0 has an implementation of the oracle in grover which uses toffoli gates, a controlled x gate, and a cnot gate. If you print out the bit string of the states for each block of gate operations, you see that at some point, the true match has all bits sets before the pseudo reversal of operations returns the state to the original value which is a nice look at the operations.
I made a few changes to my version of their code and added a method that accepts a list of numbers.
I reserve an extra bit as the high bit and use that to indicate when all bits are set, that is, the query matches a state. I assume a CCAND will be available on the computer too. Then I use a phase kick to apply the rotation if the high bit is set. Then the result is that only a match has its amplitude multiplied by -1.
Note that their code requires a couple of small changes for the oracle. One is that the register should be initialized to 2*N + 2 where N is the requested number of qubits. Also note that one of the blocks in the oracle needs the for loop arguments adjusted to not overrun the register word size (== the number of qubits).