The accuracy of Grover's algorithm decreases for 3 qubit then increases for 4 qubit and then again increases for 5-qubit on simulator (qasm simulator) with pi/4(sqrt N) iterations. What is the reason behind that? Why there is no specific patten.
1 Answer
The accuracy of measuring the correct result is given by a sine $\sin^2((r + \frac{1}{2})\theta)$ where $r$ is the number of Grover iterations and $\theta$ is the angle between starting state (before Grover iteration) $|s\rangle$ and $|s'\rangle$. $|s'\rangle$ is a state perpendicular to our winner, desired output state $|\omega\rangle$. $\theta$ is given by $\sin\frac{\theta}{2} = \frac{1}{\sqrt{N}}$ where $N$ is the number of all possible outputs (for $n$ qubits $N = 2^n$.) Therefore the precise accuracy may float a bit up and down depending on number of all elements and, related, number of Grover iterations.
Qiskit textbook's chapter on Grover Algorithm has a nice graphical interpretation of these rotations that could help understand it.