5.3.1 Angle amplification

The final quantum algorithm that we will discuss is a very important subroutine that is used in many other quantum algorithms (for example, it is at the heart of Grover’s algorithm for functions with more than $n=2$ input bits).

The problem this subroutine solves might at first appear very strange. Indeed, it is a purely quantum problem that does not even have a meaningful classical formulation. Nevertheless, it appears naturally in various other algorithms, which makes the subroutine very useful. This highlights how different the ideas behind quantum algorithms are and that novel ways of thinking are required for inventing new quantum algorithms!

Moreover, this is an example of a problem where the oracle needs to be consulted more than once. This is different from all of the quantum algorithms we considered earlier in this quest, which used the oracle only once.

Homework 5.6 (What is the angle? (challenging)).

Alice and Bob hand are distraught. “We’re so sorry for the trouble,” they tell you. “We built this beautiful reflection $V(\theta)$ with angle

\theta=+\frac{\pi}{4k}\quad\text{or}\quad\theta=-\frac{\pi}{4k},

but we just cannot remember which one it was – we only remember the integer $k\geq 1$ !”¹⁵¹⁵ 15 If you like, you can think of this reflection as an oracle that hides one of the two angles in a funny way. What adds to their trouble is that the gate will self-destruct when used more than $k$ times.

Can you help them out? Your task, if you choose to accept it, is to determine which of the two angles is the correct one by using the gate $V(\theta)$ at most $k$ times.

Hint: Two consecutive reflections make a rotation. What do you get by combining $\mathrm{NOT}$ and $V(\theta)$ ? (You don’t need the general formula in 4.6 to answer this question.)

Hack.

Following the hint, we look at $R=\mathrm{NOT}\,V(\theta)$ . We find that

\displaystyle\mathrm{NOT}\,V(\theta)=\mathrm{NOT}\,\mathrm{NOT}\,U(\theta)=U(\theta)

is a rotation by angle $\theta$ . In the second step we used that $V(\theta)=\mathrm{NOT}\,U(\theta)$ , which is the way we defined $V(\theta)$ in Eq. 2.33.

In Section 4.1.4, we discussed that two consecutive rotations make a rotation whose angle is the sum of the two original angles. Since $R$ is a rotation by angle $\theta$ , this means that if we repeat it $k$ times then we get a rotation by angle $k\theta=\pm\frac{\pi}{4}$ . That is:

\displaystyle\underbrace{R\dotsb R}_{k\text{ times}}=U(\pm\pi/4)

If we take the initial state to be $\left|+\right\rangle=\left|\psi(\pi/4)\right\rangle$ then

\underbrace{R\dotsb R}_{k\text{ times}}\left|+\right\rangle=U(\pm\pi/4)\left|% \psi(\pi/4)\right\rangle=\left|\psi(\pi/4\pm\pi/4)\right\rangle.

Hence, the final state is either $\left|\psi(\pi/2)\right\rangle=\left|1\right\rangle$ (if the sign was ‘ $+$ ’) or it is $\left|\psi(0)\right\rangle=\left|0\right\rangle$ (if the sign was ‘ $-$ ’). We can distinguish these two cases by measuring the final state.