Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
The image below is the result of finding 4 correct answers from 8 candidates using qiskit. The 4 correct answers I set were 000, 001, 010, 011, but the graph shows the probability is incorrect (the result gives even distribution). Then, I tried on cases with more qubits, and they are all confused on half solution condition. I have no idea about why it occurs.
Check out this explanation of Grover's algorithm.
If half the possible strings are solutions, then we start with $|s\rangle$ exactly halfway between the $|\text{solution}\rangle$ vector and the $|\text{not-solution}\rangle$ vector. When we then do the two reflections, we end up with a vector that is $$U_s U_w |s\rangle = \tfrac{1}{\sqrt{2}}(|\text{solution}\rangle - |\text{not-solution}\rangle)$$
i.e. equal chance of measuring a solution or not a solution.
In reality, we don't care about the case where 50% of states are solutions since we can solve this easily via random guessing.
