Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The black box in Deutsch's algorithm

  1. Mar 7, 2015 #1
    I am not sure whether this question should go in Quantum Physics, Computers, or Linear Algebra. I am willing to see it moved if appropriate.
    In Nielsen and Chuang's "Quantum Computation and Quantum Information", in explaining quantum parallelism in section 1.4.2 (as a preparation for Deutsch's algorithm), he introduces the "black box" (later in the book he is more explicit about its construction) Uf such that: if f is a function from {0,1} to {0,1}, and x, y are qubits, then Uf (x,y) = (x,y⊕f(x)) where ⊕ is addition mod 2. This definition confuses me, for two reasons:
    (a) If the domain of f is bits, then how can we talk of applying it to a qubit x?
    (b) If the range of f is bits, then what is the manner in which we add it to a qubit mod 2? For example, how does one calculate (1/√2)(|0> +|1>) ⊕ 1?
    Thanks for any indications. This is stopping me from clearly understanding the algorithm.
     
  2. jcsd
  3. Mar 8, 2015 #2

    atyy

    User Avatar
    Science Advisor

    x and y are either 0 or 1. The function f is implemented by a unitary transformation, so it is linear. You can see what they mean by looking at Eq 1.37.
     
  4. Mar 8, 2015 #3
    Thanks, atyy. I am however puzzled by your reply (since you obviously have access to the text, I will refer to it), in that precisely the equation 1.37 refers to the situation in Figure 1.17, in which the inputs are x = (1/√2)(|0> + |1>) and y = |0>, neither one of which is 0 or 1.

    Also I am a little unsure of the notation in 1.37: does |0, f(0)> mean the ket (written horizontally for typographical reasons) (0, f(0)) or does it mean the tensor product |0>⊗|f(0)>?

    As far your remark of linearity, I presume that one part of that is that
    f((1/√2)(|0> + |1>) = (1/√2)(f(|0>) + f(|1>)) ) ,
    but then I am not sure whether f(|0>) means |f(0)>, or , using the convention |0> = (1,0), does it mean (f(1),f(0))?

    Thanks for your help.
     
  5. Mar 8, 2015 #4

    martinbn

    User Avatar
    Science Advisor

    In equation 1.37 they apply the transformation [itex]U_f[\itex], not the function. The transformation is defined on a basis and it is extended to the whole space by linearity. You are right that they are not very careful and use [itex]x[\itex] and [itex]y[\itex] for qubits and for 0 or 1 if the qubit is in the corresponding state. For your last question, it means the tensor product.
     
  6. Mar 8, 2015 #5

    atyy

    User Avatar
    Science Advisor

    martinbn gave all the answers, I'll just write the same in a different way. They do not implement f directly, the implement Uf, and Uf is defined by its action on |x,y> where x and y are 1 and 0. They define Uf to be a linear operator, and they define its action on the whole space by defining its action in a certain basis.

    It means the tensor product.

    No, they don't implement f directly. So it is

    Uf(|0>⊗(|0> + |1>)) = Uf(|0>⊗|0> + |0>⊗ |1>) = |0>⊗|f(0)> + |0>⊗ |f(1)>)
     
    Last edited: Mar 8, 2015
  7. Mar 8, 2015 #6
    Thanks for your help, martinbin and atyy. I am starting to see through the notation. But (A) to make sure I understand, and (B) to be able to ask a further question, I am going to be really dense and write out everything very explicitly.

    First, the definition of Uf would be written explicitly like this:

    Uf(|x>⊗|y>) = |x>⊗(|x>⊕f(|y>)

    So, taking the first two steps of atyy’s last calculation, and putting in my explicit continuation, I get

    Uf(|0>⊗(|0> + |1>)) = Uf(|0>⊗|0> + |0>⊗ |1>) = Uf(|0>⊗|0>) + Uf (|0>⊗ |1>)
    = (|0>⊗(|0>⊕f(|0>)) +(|0>⊗(|1>⊕f(|0>)) (*)

    instead of atyy’s |0>⊗|f(0)> + |0>⊗ |f(1)>) (**).

    It is not evident that (*) and (**) are the same, but perhaps I am just not used to modulo addition with vectors. Getting even more explicit: Does it work with vectors as follows?
    (a,b) ⊕(c,d) = (a⊕c, b⊕d)?
    E.g., (1,0) ⊕(1,0)= (0,0), (1,0)⊕(0,1)=(1,1), etc.? (So, for example, |0>⊕|0> is not equal to |0>.)

    If it does, then for example, then I definitely do not see how (*) could be equivalent to (**). If it doesn’t, then how does it go?

    Thanks again for your patience.
     
  8. Mar 8, 2015 #7

    martinbn

    User Avatar
    Science Advisor

    It should be

    Uf(|x>⊗|y>) = |x>⊗(|x⊕f(y)>
     
  9. Mar 8, 2015 #8
    Ah, thanks again, martinbn. That might clear the whole thing up. But first, in the book, it has the x and y in the last two terms switched:
    |x,y> into |x,y⊕f(y)>. (lines 2 and 3 of page 31, my edition).
    So, to check: in my version of saying |x> instead of x, and assuming that x and y are digits, and not vectors, if I were to write the kets out in vector notation, I would get the definition Uf|x,y> into |x,y⊕f(x)> to be
    Uf((a,b)⊗(c,d)) = (a,b)⊗(c⊕f(a), 1-(c⊕f(a))) ?
     
  10. Mar 8, 2015 #9

    martinbn

    User Avatar
    Science Advisor

    Yes, you are right it should be [itex]U_f|x,y\rangle =|x,y\oplus\rangle f(x)[/itex].

    What does [itex](a,b)[/itex] stand for? Is it [itex]a|0\rangle+b|1\rangle[/itex]? That would be my guess, but then [itex]a, b[/itex] e complex numbers not bits and the transformation will be different.
     
  11. Mar 9, 2015 #10
    Thanks, martinbn. When typing that last response rather hastily, I had in mind that a, b in {0,1}. However, taking another look at it, I see that this still resolve my difficulty. Therefore let me back up a little and try again.

    To be very clear, I am converting the notation |x,y> into |x>⊗|y>.
    Following the convention in Nielsen&Chuang, |0> = (1,0), and |1> = (0,1) (except here written horizontally.)

    The book allows |x> and |y> to be qubits.

    The definition of Uf is that it takes |x>⊗|y> to |x>⊗ |y⊕ f(x)>

    For s, t ∈ℂ, if |x> = s|0> + t|1>, f(x) = s⋅f(0)+ t⋅f(1).

    If y = s⋅p, for p∈ {0,1}, and s=t, then we can say that |x>⊗ |y⊕f(x)>= |sx>⊗|p⊕(f(0)+f(1))>

    This is the example in 3.17, with s = √½ and y = s⋅0

    Also if s,t,y ∈ {0,1}, then f(x) is an integer, and the expression y⊕f(x) makes sense.

    However, if s≠ t and s,t ∉ {0,1}, or if s=t and y∉ {0,s}, or s,t∈ {0,1} and y∉{0,1} , I am not quite sure how to make sense out of y⊕f(x). I do not see how linearity will help outside of the special cases.
     
  12. Mar 9, 2015 #11

    martinbn

    User Avatar
    Science Advisor

    In the definition of Uf, x and y are assumed to be just 0 or 1, so it makes sense to compute f(x) and f(y). Once it is defined for these states [itex]|x\rangle\otimes|y\rangle[/itex] with x and y only 0 or 1, you can extend it by linearity.
     
  13. Mar 9, 2015 #12
    Thanks again, martinbn, but I think you are missing my point. Yes, I got the fact that you can extend f by linearity: I did precisely that in my last post in order to accommodate the assumption that x could be a qubit, as stipulated by the text. The problem is that once you extend it, you end up with the addition modulo 2 no longer making sense. Once you extend f(x), you end up with non-integer values that are not always possible to factor out.
     
  14. Mar 9, 2015 #13

    martinbn

    User Avatar
    Science Advisor

    You don't extend the function f, you extend the transformation Uf by linearity so that you can apply it to states like |0,0>-|0,1>+3|1,1>. The fomula defines it only for the basis |00>, |01>, |10> and |11>.
     
  15. Mar 9, 2015 #14

    atyy

    User Avatar
    Science Advisor

    Again, I'm just saying the same as martinbn. It's fine up to here. At this stage x and y can only be 0 or 1. Since Uf is linear, the action of Uf on any vector is defined if we define its action in a particular basis. By defining it for all combinations of x and y being 0 or 1, Uf is defined for any vector.

    This step is not correct. Uf is the operator which acts on |x>⊗|y> , where it is defined on a basis, and because it is linear, that defines its action on any vector. To get the action explicitly, you can expand each vector using the basis |00>, |01>, |10>, |11>.
     
  16. Mar 10, 2015 #15
    Thanks a lot for your continued help, martinbn and atyy. Am I to understand that the definition |x,y>→|x, y⊕f(x)> is only applicable for x, y ∈{0,1}, and that the extension to the rest of the vectors, say
    |x>=√½ (|0>+|1>) & |y>= |1>,
    is not explicitly given?
     
  17. Mar 10, 2015 #16

    martinbn

    User Avatar
    Science Advisor

    That is correct. To see what the transformation is for |x>|y> with |x>=√½ (|0>+|1>) & |y>= |1>, write it as |x>|y>=√½ (|0>+|1>)|1>=√½ |0>|1>+√½|1>|1> and apply it for each of the two terms.
     
  18. Mar 10, 2015 #17
    ... ending up with √½ [(|0>|1⊕f(0)>)+(|1>|1⊕f(1)>)]? This finally makes sense! :smile: I can imagine that it would be a lot trickier for most other qubits, but I believe that I get the idea. Thanks a million, martinbn! (and to atyy)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: The black box in Deutsch's algorithm
  1. MWI, EPR and Deutsch (Replies: 10)

Loading...