No, [itex]U_f[/itex] is defined only on the computational-basis states |0>,|1>, ...etc. And I forgot to mention it's actually [tex] U_f\mid x\rangle\mid y\rangle =\mid x\rangle\mid y\oplus f(x)\rangle[/tex] where [itex]a\oplus b[/tex] is a bitwise modulo 2 sum.

If [tex]U_f[/tex] keeps [tex]\left|x\right\rangle[/tex] untouched then the second argument had better not depend on what [tex]\left|x\right\rangle[/tex] was... otherwise the operator can't be unitary.

I'm not 100% sure what you're asking for, but I think the answer to your question is no. Let me rephrase it to see if I've got it right.
Bob has a 1-1 function f:A->A for a finite set A, and for every x in A, there is a state vector |x> describing a possible state of some system -- say, S. The |x> for x in A form an orthonormal basis for states of S. He then constructs the following state (on two copies of system S).

In your example, you have A={0,1}^{n}, but I don't know if there is any particular reason for this choice other than just wanting to think about a binary string of length n.

Then, supposing Alice has no knowledge of f other than it being a 1-1 function on A, you want to know if she can compute f(x) for her prefered value of x, simply by making measurements on the system with state [itex]\Psi_f[/itex]? At least, with an arbitrarily small probability of getting the wrong result?

Well, suppose that [itex]|\Phi_{x,y}>[/itex] is the state if Alice measures f(x) to be y. Then these states would have to be orthogonal for different y and, if the probability of getting the wrong result is less than [itex]\epsilon[/itex] you would need
[tex]
| <\Phi_{x,y}|\Psi_f>|^2>1-\epsilon
[/tex]
whenever y=f(x) and
[tex]
| <\Phi_{x,y}|\Psi_f>|^2<\epsilon
[/tex]
whenever y != f(x). I'm fairly certain that you can't make [itex]\epsilon[/itex] very small for all functions f.

Maybe you can do better than the classical situation though?

ok, the answer is no.
For a fixed x in A, you can easily find functions f and g with f(x) != g(x), but where [itex]<\Psi_f|\Psi_g>\not=0[/itex] and therefore can't be distinguished with zero probability.

If f(x) != g(x) for some f,g then f(y) and g(y) can agree for at most |A|-2 values of y, giving
[tex]
|<\Psi_f|\Psi_g>|^2 \le \left(1-2/|A|\right)^2.
[/tex]
This is a bit better than the classical case which does not have the square.

It seems to me that the answer yes. Alice plugs this qubit into her own computer, and enacts the transformation: (for n unequal to x)

[tex]| n \rangle | a \rangle |0 \rangle \mapsto | n \rangle | a \rangle |0 \rangle[/tex]
[tex]| x \rangle | a \rangle |0 \rangle \mapsto | x \rangle | a \rangle |1 \rangle[/tex]

Then, (and this is where things get iffy for me) can't you use something like Grover's algoritm to increase the amplitude on the state whose last bit is a '1'? If you can do that, then when you measure it, you are highly likely to get the state [itex]| x \rangle | a \rangle |1 \rangle[/itex], from which you can read the value of a/i] to get f(x).

This method, alas, hinges entirely on my limited recollection of what Grover's algorithm can do for you.

I will use [itex]| f_{\left|x\right\rangle} \rangle[/itex] to denote the vector onto which [tex]|x\rangle[/tex] is mapped. If I understand you correctly, then the following is assumed:

Now, since [itex]\left|u\right\rangle[/itex] and [itex]\left|v\right\rangle[/itex] may be chosen arbitrarily, for the two expressions to be equal, we must have

Well [tex]
f_{|u\rangle + |v\rangle}
[/tex] is not defined unless [tex]
|u\rangle + |v\rangle
[/tex] is a basis vector... I'm slightly confused by the contradicting answers. I'll check back a while to hopefully clear this up.

There is no such thing as [itex]f_{|u\rangle + |v\rangle}[/itex]. What Dragonfall was specifying was the action of U on the chosen basis. (and even then, only on the subset of the basis where the last qubit is zero) The action of U on linear combinations of basis vectors is defined by the linearity relation. It's not defined by assuming f is extended to the entire vector space.

If Alice measures the first n qubits of [tex]\frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\mid i\rangle\mid f(i)\rangle[/tex], and gets some random result, say |4>. Is the post-measurement state [tex]\left| 4\right>\left| f(4)\right>[/tex]?