1
$\begingroup$

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.

wrong result

$\endgroup$
1
  • $\begingroup$ You need to give us more details of what you were doing. $\endgroup$
    – DaftWullie
    Nov 5 at 9:36
2
$\begingroup$

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.enter image description here

In reality, we don't care about the case where 50% of states are solutions since we can solve this easily via random guessing.

$\endgroup$

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.