The working of a quantum oracle is still not completely clear to me and I have a few questions: As I understand it, an oracle is a unitary quantum gate and must somehow differentiate between the eigenstates of the quantum register (the current state of which is a superposition of its eigenstates which are composites of the eigenstates of the cubits that make up the register) so that the amplitudes of some eigenstates can be increased or decreased. The differentiating criterion is given by some function $f(x)$ and $f(x)$ is mostly given to be two-valued.
My first question is: what is the domain of $x$? Is this just the set of eigenstates of the quantum register? If so, then for the quantum algorithm to work, all data must somehow be in the register state. This encoding of external data (the haystack) into the states of the quantum register would seem to be a major challenge. How can this be done?
Or is it possible that $f(x)$ somehow calls a classical function... but how, when?
It is said that in e.g. Grover's algorithm the function $f(x)$ is called just once. But what does this mean if it somehow has to filter all the $2^N$ eigenstates.