Quantum - Week 5 - Solved

QUANTUM ALGORITHMS


1. Let V and S be vector spaces over C with bases BV and BS, respectively. Define

 and 

and recognize it as a vector space by coordinate-wise interpretation of the vector space axioms. That is,

(v1,s1) + (v2,s2) = (v1 + v2,s1 + s2)
for v1,v2 ∈ V and s1,s2 ∈ S,
λ · (v1,s1) = (λ · v1,λ · s1)
for v1 ∈ V,s1 ∈ S, and λ ∈ C a scalar.
If R : A → V and T : A → S are linear functions, then we can define a linear function (R × T) : A → V × S by

                                                                  for a ∈ A.

(i)                        Let

  and  .

Show that C-span(C) = V × S but that C is not always a basis for V × S.

(ii)                      Prove that

  and 

is a basis for V × S. What is the dimension of V × S?

(iii)                    Let R : A → V and T : A → S be linear functions. Suppose that A, V, and S have ordered bases

                                   ,           ,              BS = {s1,s2},

and that the matrix representations of R and T relative to these bases are

                                             and         (  .

Using the lexicographic order for the basis BV×S (i.e. ordering by BV first, and then BS), find the matrix representation for (R × T) (that is, find (R × T)BA→BV×S).

Problems continue on the next page.

1

                                                  QUANTUM ALGORITHMS, HW 5 ADDITIONAL PROBLEMS                                                                         2
2.    Let T : A → B be a linear transformation between vector spaces with ordered bases

                                                                .

Suppose that T has matrix with respect to these bases

  .

(i)         Show that the matrix for T can be written T = X aij |iihj|

|ji∈BA

|ii∈BB

(note that |1i ∈ BA is a 3-dimensional vector, while |1i ∈ BB is a 2-dimensional vector).

(ii)       Show that for fixed |ii ∈ BA and |ji ∈ BB

 

for all hv| ∈ A. From this, prove that |jihi| defines a linear transformation from A → B.

(iii)    Suppose that

R = X bij |iihj|

|ji∈BA |ii∈BB

for bij ∈ C. Use the previous part to prove that R is a linear transformation from A → B.

3.    Let V and S be vector spaces over C with bases BV and BS, respectively.

(i)         Prove that

  and  

is a basis of V ⊗ S. What is the dimension of V ⊗ S?

(ii)       Let R : V → A and T : S → B be linear functions. Suppose that A, V, and S have ordered bases the same as in the previous question and that B has ordered basis  and that the matrix representations of R and T relative to these bases are

                                    and         (  .

Using the lexicographic order for the basis BV⊗S, find the matrix representation for (R ⊗ T)

(that is, find (R × T)BV⊗S→BA⊗B). [Hint: Kronecker product.]