Measuring Quantum State: Solving for a Specific Value of a Unitary Function

[Dragonfall]

The other thread was going too off-topic, so I'll repost here. Why is this not possible, without considering FTL signals?

I'm just going over what I'm asking again since I wasn't clear before:

Bob takes n+1 qubits, all initiated at |0> (the first n being input registers and the last is an output register), and sends the first n through an n-fold Hadamard gate. This results in the superposition

$$\mid\Psi\rangle =\frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\mid i\rangle\mid 0\rangle$$

Bob then chooses some function f bounded above by 2^n-1, then finds a unitary operator which implements the function:

$$U_f\mid x\rangle\mid 0\rangle =\mid x\rangle\mid f(x)\rangle$$

Bob then sends $U_f\mid\Psi\rangle$ to Alice. Alice now has n+1 qubits with loads of information about the function f. Alice would like to learn a PARTICULAR VALUE of f (not a random one). Can she do it?

 

[lbrits]

Bob violates the no-clone theorem? Said operator isn't unitary.

 

[Dragonfall]

Where does Bob violate the no-cloning theorem?

 

[lbrits]

I believe this does:
$$U_f\mid x\rangle\mid 0\rangle =\mid x\rangle\mid f(x)\rangle$$
I could be mistaken. Specifically, $$f(x)$$ cannot depend on $$x$$. See http://www.physics.thetangentbundle.net/wiki/Quantum_mechanics/no_cloning_theorem

 

[Dragonfall]

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

 

[lbrits]

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

 

[gel]

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).

$$\Psi_f=\frac{1}{\sqrt{|A|}}\sum_{x\in A}|x>|f(x)>$$

In your example, you have A={0,1}ⁿ, 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 preferred value of x, simply by making measurements on the system with state $\Psi_f$? At least, with an arbitrarily small probability of getting the wrong result?

 

[gel]

Well, suppose that $|\Phi_{x,y}>$ 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 $\epsilon$ you would need
$$| <\Phi_{x,y}|\Psi_f>|^2>1-\epsilon$$
whenever y=f(x) and
$$| <\Phi_{x,y}|\Psi_f>|^2<\epsilon$$
whenever y != f(x). I'm fairly certain that you can't make $\epsilon$ very small for all functions f.

Maybe you can do better than the classical situation though?

 

[gel]

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 $<\Psi_f|\Psi_g>\not=0$ 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
$$|<\Psi_f|\Psi_g>|^2 \le \left(1-2/|A|\right)^2.$$
This is a bit better than the classical case which does not have the square.

 

[Hurkyl]

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

Sure it can. For example, the operator (given by its action on the chosen basis)

$$| x \rangle | y \rangle \mapsto | x \rangle | y \oplus f(x) \rangle$$

is linear and has an obvious inverse. (Itself!)

 

[Hurkyl]

Alice would like to learn a PARTICULAR VALUE of f (not a random one). Can she do it?

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)

$$| n \rangle | a \rangle |0 \rangle \mapsto | n \rangle | a \rangle |0 \rangle$$
$$| x \rangle | a \rangle |0 \rangle \mapsto | x \rangle | a \rangle |1 \rangle$$

Then, (and this is where things get iffy for me) can't you use something like Grover's algorithm 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 $| x \rangle | a \rangle |1 \rangle$, 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.

 

[lbrits]

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

$$U |x\rangle \otimes |0\rangle = |x\rangle \otimes | f_{|x\rangle}\rangle$$.

Then

$$U \left\{ |u\rangle + |v\rangle \right \} \otimes |0\rangle = \left\{ |u\rangle + |v\rangle \right\} \otimes | f_{|u\rangle + |v\rangle} \rangle = |u\rangle \otimes | f_{|u\rangle + |v\rangle} \rangle + |v\rangle \otimes | f_{|u\rangle + |v\rangle} \rangle$$

and also

$$U \left\{ |u\rangle + |v\rangle \right \} \otimes |0\rangle = |u\rangle \otimes | f_{ |u\rangle} \rangle + |v\rangle \otimes | f_{ |v\rangle} \rangle$$

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

$$| f_{|u\rangle + |v\rangle} \rangle = | f_{ |u\rangle} \rangle = | f_{ |v\rangle} \rangle$$.

Either I misunderstand your notation or $$U$$ is not linear.

 

[Dragonfall]

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

 

[Hurkyl]

| f_{|u\rangle + |v\rangle} \rangle

There is no such thing as $f_{|u\rangle + |v\rangle}$. 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.

 

[Dragonfall]

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

 

[Dragonfall]

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)

$$| n \rangle | a \rangle |0 \rangle \mapsto | n \rangle | a \rangle |0 \rangle$$
$$| x \rangle | a \rangle |0 \rangle \mapsto | x \rangle | a \rangle |1 \rangle$$

Then, (and this is where things get iffy for me) can't you use something like Grover's algorithm 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 $| x \rangle | a \rangle |1 \rangle$, 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.

But you wouldn't even need to do that. Can't you just use Grover's algorithm to search for the exact term you want?

 

[Hurkyl]

Can't you just use Grover's algorithm to search for the exact term you want?

Yah, I realized after I left for work that if my understanding of Grover's algorithm is right, then I didn't need to bother with the indicator qubit!

 

[Dragonfall]

But what's the catch? This seems too easy...

 

[Hurkyl]

But what's the catch? This seems too easy...

Either it really is that easy, or I'm misremembering Grover's algorithm. It's up to you to figure out which.