Quantum - Week 6 - Solved

QUANTUM ALGORITHMS


1.    Prove that the inner product and the tensor product commute:

hα ⊗ β | γ ⊗ δi = hα | γihβ | δi.

This is asserted on page 57 of the textbook.

2.    An n-ary function f : Bn → B is idempotent if

                                                   f(0,...,0) = 0             and             f(1,...,1) = 1.

Find a basis A so that every idempotent Boolean function is representable as a circuit over

A. Prove your answer is correct. [Hint 1: Post’s Lattice.] [Hint 2: ? :.]

1