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

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 [Broken]

Last edited by a moderator: May 3, 2017
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: