2
$\begingroup$

Chapter 6.3 of "Quantum Computation and Quantum Information 10th Anniversary Edition" textbook by Nielsen and Chuang talks about using the Quantum Counting Algorithm to find the number of solutions to the Quantum Search Algorithm before actually implementing it.

For a search space of size $2N$ with $M$ number of solutions, the number of Grover iterations $R$ required to obtain the state of solutions is upper bounded by (Eqn 6.17):

$$R \leq \lceil\frac{\pi}{4}\sqrt{2N/M}\space\rceil $$

At the last paragraph of this chapter, they stated that the angular error after the $R$ number of Grover iterations is at most $\pi/4(1+|\Delta\theta|/\theta)$. I think that this means:

$$|\Delta\theta| R \leq |\Delta\theta|\lceil\frac{\pi}{4}\sqrt{2N/M}\space\rceil = \pi/4(1+|\Delta\theta|/\theta) $$

We know that $\sin^2(\theta/2)=\frac{M}{2N}$, so I tried to use substitution in the attempt to get the stated angular error. This is what I got:

$$|\Delta\theta| R \leq |\Delta\theta| \space \lceil \frac{\pi}{4}\frac{1}{\sin(\theta/2)} \rceil $$

Can someone explain to me how to get the stated angular error?

$\endgroup$
  • $\begingroup$ where exactly is the $\pi/4(1+|\Delta \theta|/\theta)$ equation in the text? I can't find it in that chapter of N&C (I'm looking at the 2010 edition) $\endgroup$ – glS Jun 30 at 8:00
  • $\begingroup$ @gIS Yes the one released on year 2010. Last paragraph of chapter 6.3, "Another application of quantum counting is to find...." $\endgroup$ – C.C. Jul 1 at 8:09
2
$\begingroup$

The angle of each rotation $\theta$ obeys $0\leq \theta \leq \frac{\pi}{2}$ so that $0\leq \frac{\theta}{2} \leq \frac{\pi}{4}$. The Grover Iterations as we know, rotates our initial state vector $|\psi\big>=cos(\theta/2) |\alpha\big> + sin(\theta/2)|\beta\big>$ by the angle $\theta$ a few times, such that eventually $|\psi \big>$ will be rotated to within an angle $\frac{\theta}{2}\leq \frac{\pi}{4}$ of $|\beta\big>$ which is our desired state.

By using the Quantum Counting Algorithm to get an estimate of $\theta\approx\theta+\Delta\theta$ and thus $\approx M$ which is the number of solutions, we introduced the error of $\Delta (\theta/2)$ to our initial state $|\psi \big>$. Since we know $\frac{\theta}{2}\leq \frac{\pi}{4}$, the maximum error tied to our initial state $|\psi\big>$ will be given as:

$$\text{Maximum Initial Error} = \frac{\pi}{4} \times \frac{|\Delta(\theta/2)|}{\theta/2} = \frac{\pi}{4} \frac{|\Delta(\theta)|}{\theta}$$

Grover Iterations will then rotate $|\psi\big>$ close to $|\beta\big>$, with the maximum angular separation being $\frac{\pi}{4}$ no matter what is the initial angle of $\frac{\theta+\Delta\theta}{2}$. So the total angular deviation (accounting for the offset of $\Delta(\theta/2)$ in the initial state $|\psi\big>$) from $|\beta\big>$ in this case is:

$$\text{Total Angular Deviation} =\frac{\pi}{4}+\text{Maximum Initial Error}$$

This is why we'll get $\frac{\pi}{4}\big(1+\frac{|\Delta\theta|}{\theta}\big)$ as compared to just $\frac{\pi}{4}$. Please do input additional comments if any.

$\endgroup$
1
$\begingroup$

In the last equation in the question above the left hand, and right hand - the $\Delta \theta$ terms cancel, and the denominator $\sin^{2}(\theta)$ term whose root is as you mentioned inverted (as it's in the denominator) to give the bound as the first equation in the question. See related question for the floor operation,

$\endgroup$
  • $\begingroup$ My question is how to get $\frac{\pi}{4} (1+\frac{|\Delta \theta|}{\theta})$? $\endgroup$ – C.C. Jul 10 at 16:01
  • 1
    $\begingroup$ @C.C: the $|\Delta \theta|$ term is used in the case of Grover search when its used for $k$ items. The phase estimation algorithm introduces this error $|\Delta \theta|$, in estimating $\theta$, which then is passed to a Grover Search(I dont have the N&C up front), but the $k$ item Grover Search application uses, the Phase Estimation algorithm before the Grover Search to get the good states. $\endgroup$ – user3483902 Jul 11 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.