The quantum Fourier transform as a quantum circuit. Let d be a positive integer and let 2d=e2d2i, where iC is the imaginary unit. Let H=21[1111] and R(d,)= [1002d2d] for [d] (a) Show that Bj=I2jHI2dj1 factors as Bj=H[ddj1] for j[d]. (b) Show that Tj=I2jdiag(2d2j22dj1) factors as Tj=k=0dj2(CR(d,j+k))[ddj1,k] for j[d1]. (c) Conclude that the d-qubit quantum Fourier transform Fd=PdBd1Td1Bd1T1B1T0B0C2d2d factors into a product of O(d2) extensions of at-most-two qubit gates. Hints: Recall (the unnormalized form of) the factorization (1) and our conventions with matrices from Week 2. You may want to work with the d-bit binary representation of the row and column indices x,y[2d]. For part (a), using the definitions of Kronecker product and extension, conclude that (Bj)x,y=(H[ddj1])x,y. For part (b), first derive an expression for the diagonal entry (Tj)x,x using the binary representation of x, then assemble this expression using a sequence of controlled R(d,) gates. Part (c) is an immediate consequence of (a), (b), and Problem 1(b)