|\psi\rangle = |0\rangle. •
Haddamard gate operations is applied on both lower and upper registers. -->
Setup The input consists of two
registers (namely, two parts): the upper p qubits comprise the
first register, and the lower n qubits are the
second register.
Create superposition The initial state of the system is |0\rangle^{\otimes p}|0\rangle^{\otimes n}. After applying multiple bit
Hadamard gate operation on each of the registers separately, the state of the
first register is :\frac{1}{2^{p/2}}(|0\rangle + |1\rangle)^{\otimes p} and the state of the
second register is :\frac{1}{2^{n/2}}(|0\rangle + |1\rangle)^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle an equal
superposition state in the computational basis.
Grover operator Because the size of the space is \left\vert \{0,1\}^n \right\vert = 2^n = N and the number of solutions is \left\vert B \right\vert = M , we can define the normalized states: From the
properties of rotation matrices we know that G is a
unitary matrix with the two
eigenvalues e^{\pm i \theta}. Note that the second register is actually in a
superposition of the
eigenvectors of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate \theta, and with some probability, we approximate 2\pi - \theta; those two approximations are equivalent.
Analysis Assuming that the size N of the space is at least twice the number of solutions (namely, assuming that M \leq \tfrac{N}{2} ), a result of the analysis of Grover's algorithm is: : \sin {\frac{\theta}{2}} = \sqrt{\frac{M}{N}}. Thus, if we find \theta, we can also find the value of M (because N is known). The error : \frac{\vert \Delta M \vert}{N} = \left \vert \sin^2 \left( \frac{\theta + \Delta \theta}{2} \right) - \sin^2 \left( \frac{\theta}{2} \right) \right \vert is determined by the error within estimation of the value of \theta. The quantum phase estimation algorithm finds, with high probability, the best p-bit approximation of \theta; this means that if p is large enough, we will have \Delta \theta \approx 0, hence \vert \Delta M \vert \approx 0 . \Bigg\vert \sin {\frac{\theta + \Delta \theta}{2}} - \sin {\frac{\theta}{2}}\Bigg\vert \leq \frac{\Delta \theta}{2} and \Bigg\vert \sin {\frac{\theta + \Delta \theta}{2}}\Bigg\vert we see that \vert \Delta M \vert . --> == Uses ==