The black box in Deutsch's algorithm

[nomadreid]

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) U_f such that: if f is a function from {0,1} to {0,1}, and x, y are qubits, then U_f (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.

 

[atyy]

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.

 

[nomadreid]

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.

 

[martinbn]

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.

 

[atyy]

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

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

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

It means the tensor product.

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

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

U_f(|0>⊗(|0> + |1>)) = U_f(|0>⊗|0> + |0>⊗ |1>) = |0>⊗|f(0)> + |0>⊗ |f(1)>)

 

[nomadreid]

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.

 

[martinbn]

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

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

It should be

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

 

[nomadreid]

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

 

[martinbn]

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.

 

[nomadreid]

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.

 

[martinbn]

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.

 

[nomadreid]

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.

 

[martinbn]

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

 

[atyy]

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

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.

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

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

 

[nomadreid]

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?

 

[martinbn]

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.

 

[nomadreid]

... ending up with √½ [(|0>|1⊕f(0)>)+(|1>|1⊕f(1)>)]? This finally makes sense! 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)