Chapter 9

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\ 9.1}$

Verify that

(1)
\begin{align} g_i = \sin ((2i+1)\theta)\\ b_i = \cos ((2i+1)\theta), \end{align}

with $\sin\theta = \sqrt{t} = \sqrt{{\abs{G}}/{N}}$, is a solution to the recurrence relations of section 9.1.4.

$\mathbf{Exercise\ 9.2}$

Show that applying Grover's algorithm in the case $t = |G|/N = 1/2$ results in no improvement.

$\mathbf{Exercise\ 9.3}$

What happens if we try to apply Grover's algorithm to the case $t = |G|/N = 3/4$?

$\mathbf{Exercise\ 9.4}$

a) How many iterations should Grover's algorithm use in order to find one item among sixteen?

b) If we apply one fewer than the optimal number of iterations and then measure, how does the success probability compare to the optimal case?

c) If we apply one more than the optimal number of iterations and then measure, how does the success probability compare to the optimal case?

$\mathbf{Exercise\ 9.5}$

Suppose $P: \{0,\dots, N-1\} \to \{0,1\}$ is zero except at $x = t$, and suppose we are given not only a quantum oracle $U_P$, but also the information that the solution $t$ differs from a known string $s$ in exactly $k$ bits. Exhibit an algorithm that finds the solution with $O(\sqrt{2^k})$ calls to $U_P$.

$\mathbf{Exercise\ 9.6}$

Suppose $P: \{0,\dots, N-1\} \to \{0,1\}$ is zero except at $x = t$, and suppose we are given not only a quantum oracle $U_P$, but also the information that all suffixes except $010$ and $100$ have been ruled out. In other words, the solution $t$ must end with either $010$ and $100$. Exhibit an algorithm that finds the solution with fewer calls to $U_P$ than Grover's algorithm.

$\mathbf{Exercise\ 9.7}$

Suppose $P: \{0,\dots, N-1\} \to \{0,1\}$ is zero except at $x = t$, and suppose we are given not only a quantum oracle $U_P$, but also the information that the solution $t$ differs from a known string $s$ in at most $k$ bits. Exhibit an algorithm that finds the solution with $O\left(\left(\begin{array}{c} n \\ k \end{array} \right) \right)$ calls to $U_P$.

$\mathbf{Exercise\ 9.8}$

Suppose $P: \{0,\dots, N-1\} \to \{0,1\}$ is zero except at $x = t$, and suppose we are given a quantum oracle $U_P$ and told that with probability $0.9$ the first $n/2$ bits of the solution $t$ are zero. How can we take advantage of this information to obtain an algorithm that is more efficient, in terms of the number of calls needed, than $O(\sqrt{2^n})$?

$\mathbf{Exercise\ 9.9}$

Given a quantum black box for a function $f: \{0,\dots, N-1\} \to \{0,\dots, N-1\}$, design a quantum algorithm that finds the minimum with $O(\sqrt{N}\log{N})$ queries, where $N = 2^n$.

$\mathbf{Exercise\ 9.10}$

Suppose there is an error in the initial state, so that instead of starting with $\ket{00\dots 0}$, we run Grover's algorithm starting with the state

(2)
\begin{align} \frac{1}{\sqrt{1 + \epsilon^2}} (\ket{00\dots 0} + \epsilon\ket{11\dots 1}). \end{align}

How does this error affect the results of Grover's algorithm?

$\mathbf{Exercise\ 9.11}$

Why does applying amplitude amplification to the output of a first application of amplitude amplification not result in an additional square root reduction in the query complexity?

$\mathbf{Exercise\ 9.12}$

Prove the optimality of Grover's algorithm in the multiple solution case.

$\mathbf{Exercise\ 9.13}$
For the quantum counting procedure of section 9.5.2, show how the estimate of $t$ is obtained in the case that a bad state is measured.