# Measuring Quantum State

1. Jun 18, 2008

### Dragonfall

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

2. Jun 18, 2008

### lbrits

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

3. Jun 19, 2008

### Dragonfall

Where does Bob violate the no-cloning theorem?

4. Jun 19, 2008

### lbrits

5. Jun 19, 2008

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 $a\oplus b[/tex] is a bitwise modulo 2 sum. 6. Jun 19, 2008 ### 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. 7. Jun 19, 2008 ### 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}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$? At least, with an arbitrarily small probability of getting the wrong result?

Last edited: Jun 19, 2008
8. Jun 19, 2008

### 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?

Last edited: Jun 19, 2008
9. Jun 19, 2008

### gel

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.

Last edited: Jun 19, 2008
10. Jun 19, 2008

### Hurkyl

Staff Emeritus
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!)

11. Jun 19, 2008

### Hurkyl

Staff Emeritus
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 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 $| 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.

12. Jun 19, 2008

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

13. Jun 19, 2008

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

14. Jun 20, 2008

### Hurkyl

Staff Emeritus
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.

15. Jun 20, 2008

### 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>$$?

16. Jun 20, 2008

### Dragonfall

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?

17. Jun 20, 2008

### Hurkyl

Staff Emeritus
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!

18. Jun 20, 2008

### Dragonfall

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

19. Jun 20, 2008

### Hurkyl

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