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:

(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

(2)
\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

(3)
\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}$
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.