Chapter 7

Exercises are from QUANTUM COMPUTING: A GENTLE INTRODUCTION, by Eleanor Rieffel and Wolfgang Polak, published by The MIT Press.

$\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}\mathbf{Exercise\ 7.1}$

In the standard circuit model of section 5.6, the computation takes place by applying quantum gates. Only at the end are measurements performed. Imagine a computation that proceeds instead as follows. Gates $G_{0}, G_{1}, \dots, G_{n}$ are applied, then qubit $i$ is measured in the standard basis and never used again. If the result of the measurement is $0$, the gates $G_{01}, G_{02}, \dots, G_{0k}$ are applied. If the result is $1$, then gates $G_{11}, G_{12}, \dots, G_{1l}$ are applied. Find a single quantum circuit in the standard circuit model, with only measurement at the very end, that carries out this computation.


$\mathbf{Exercise\ 7.2}$

Prove Equation 7.1:

\begin{align} \sum_{x=0}^{2^n-1} (-1)^{x \cdot y} = \left\{\begin{array}{l}2^n \mbox{ if $y = 0$}\\ 0 \mbox{ otherwise.}\end{array}\right. \end{align}


$\mathbf{Exercise\ 7.3}$

Let $f$ and $g$ be functions from the space of $n$-bit strings to the space of $m$-bit strings. Design a quantum subroutine that changes the sign of exactly the basis states $\ket{x}$ such that $f(x) = g(x)$, where $x$ and $y$ are both $n$-bit binary strings, and which is efficient if $f$ and $g$ have efficient implementations.


$\mathbf{Exercise\ 7.4}$

a) Prove that any classical algorithm requires at least two calls to $C_f$ to solve Deutsch's problem.

b) Prove that any classical algorithm requires $2^{n-1} + 1$ calls to $C_f$ to solve the Deutsch-Jozsa problem with certainty.

c) Describe a classical approach to the Deutsch-Jozsa problem that solves it with high probability using fewer than $2^{n-1} + 1$ calls. Calculate the success probability of your approach as a function of the number of calls.


$\mathbf{Exercise\ 7.5}$

Show that a classical solution to Simon's problem requires $O(2^{n/2})$ calls to the black box, and describe such a classical algorithm.


$\mathbf{Exercise\ 7.6}$

Show directly that, in the distributed computation algorithm of section 7.5.4, when $u = v$, $\abs{\braket{x,y}{\psi}}^2 = 0$ for all $x \ne y$.


$\mathbf{Exercise\ 7.7}$ Fast Fourier Transform Decomposition

a) For $k < l$, write the entries $F_{ij}^{(k)}$ of the $2^k\times 2^k$ matrix for the Fourier transform ${U_F}^{(k)}$ in terms of $\omega_{(l)}$.

b) Find $m$ in terms of $k$ such that $-\omega_{(k)}^i = \omega_{(k)}^{m+i}$ for all $i\in {\bf Z}$.

c) Compute the product

\begin{align} \left(\begin{array}{cc}I^{(k-1)}& D^{(k-1)}\\ I^{(k-1)}& -D^{(k-1)}\\\end{array}\right) \left(\begin{array}{cc}{U_F}^{(k-1)}& 0\\ 0& {U_F}^{(k-1)}\\\end{array}\right) \end{align}

ultimately writing each entry as a power of $\omega_{(k)}$.

d) Let $A$ be any $2^k\times 2^k$ matrix with columns $A_j$. The product matrix $A R^{(k)}$ is just a permutation of the columns. Where does column $A_j$ end up in the product $A R^{(k)}$?

e) Verify that

\begin{align} {U_F}^{(k)} = \frac{1}{\sqrt{2}} \left(\begin{array}{cc}I^{(k-1)}& D^{(k-1)}\\ I^{(k-1)}& -D^{(k-1)}\\\end{array}\right) \left(\begin{array}{cc}{U_F}^{(k-1)}& 0\\ 0& {U_F}^{(k-1)}\\\end{array}\right) R^{(k)}. \end{align}


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