$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.8}$

Even though we know little about quantum hardware, it makes sense that we may not want to require multiple qubit transformations that involve physically distant qubits since these may be difficult to implement. To avoid such transformations we can modify the implementation we gave very slightly.

a) Give a quantum circuit like that of figure 7.8 for the Fourier transform that does not swap qubits but changes the order of the output qubits instead.

b) Give a complete quantum circuit for the Fourier transform ${U_F}^{(3)}$ that contains only single-qubit transformations and two-qubit transformations on adjacent qubits. You may want to use the two-qubit swap operator defined in section 5.2.4.