6.8.3.3. Grover Iteration
The iteration process in Grover’s algorithm increases the likelihood of finding the correct item while weakening the probabilities of incorrect items. This process occurs through the sequential application of the Oracle and Diffusion operators. The purpose of each iteration is to manipulate the quantum state in such a way that the correct item becomes more likely to be found.
Each Grover iteration consists of the sequential application of two main components:
- Oracle (O): This operator marks the correct item. If the item is correct (i.e., \(f(x) = 1\)), the oracle inverts its phase. Otherwise, it does not change the item.
- Diffusion (D): This operator adjusts the amplitude of each item with the aim of increasing the probability of the correct item. This is the amplitude amplification step. The Diffusion operator increases the probability of the correct item while decreasing the probabilities of the incorrect items.
6.8.3.3.1. Mathematical Expression
The mathematical expression for Grover’s iteration is:
\[ |\psi_k\rangle = D \ast O \ast |\psi_{k-1}\rangle \]
Where:
- \(|\psi_k\) is the quantum state after the \(k^{th}\) iteration,
- \(|\psi_{k-1}\) is the quantum state before the \(k-1^{th}\) iteration,
- \(O\) is the Oracle operator,
- \(D\) is the Diffusion operator.
Each iteration increases the amplitude of the correct item and decreases the amplitudes of the other items. This strengthens the probability of the correct item while weakening the probabilities of incorrect items.
6.8.3.3.2. Optimum Number of Iterations
In Grover’s algorithm, the probability of finding the correct item increases with each iteration, but too many iterations can lead to incorrect results. The optimum number of iterations, denoted as \(T\), is typically expressed as:
\[ T = \frac{\pi}{4} \sqrt{N} \]
Where:
- \(N\) is the total number of items in the database,
- \(\pi\) is the number approximately 3.14159.
The optimum number of iterations increases the amplitude of the correct item while decreasing the amplitudes of incorrect items with each iteration of Grover’s algorithm. However, exceeding this number can excessively amplify the correct item’s amplitude, causing the algorithm to produce an incorrect result. Therefore, accurately setting the number of iterations is crucial.
6.8.3.3.3. The Effect of Excessive Iterations
If the number of iterations, \(T\), exceeds the optimum value, the phase transformation can cause the amplitude of the correct item to increase while negatively affecting the amplitudes of incorrect items. Thus, too many iterations carry the risk of selecting an incorrect item with a higher probability.
This situation requires a balance in Grover’s algorithm: enough iterations must be performed so that the correct item is likely to be selected, but not so many that an incorrect item becomes more prominent.