# Why can't Grover's algorithm apparently solve this simple situation?

I'm utilizing Grover's algorithm to solve a straightforward problem. It presents eight options, but only four are correct (the 1's in the S column)

$$\begin{array}{c|c|c|c} q_0& q_1\ & q_2\ &S \\ \hline 0 & 0 & 0 &1 \\ \hline 0 & 0 & 1 &1 \\ \hline 0 & 1 & 0 &1 \\ \hline 0 & 1 & 1 &0 \\ \hline 1 & 0 & 0 &0 \\ \hline 1 & 0 & 1 &0 \\ \hline 1 & 1 & 0 &0 \\ \hline 1 & 1 & 1 &1 \\ \hline \end{array}$$

Why can't Grover's algorithm apparently solve this simple situation?

The oracle produce the state (the order is $$|q_2 q_1 q_o \rangle$$):

$$-\frac{\sqrt{2}}{4} |000\rangle+\frac{\sqrt{2}}{4} |001\rangle- \frac{\sqrt{2}}{4} |010\rangle+\frac{\sqrt{2}}{4} |011\rangle- \frac{\sqrt{2}}{4} |100\rangle+\frac{\sqrt{2}}{4} |101\rangle+\frac{\sqrt{2}}{4} |110\rangle- \frac{\sqrt{2}}{4} |111\rangle$$

where the solutions clearly are $$|000 \rangle$$ , $$|010 \rangle$$ , $$|100 \rangle$$ and $$|111 \rangle$$, but the code did not find any.

Here is the code

arquivo='002.dimac'
with open(arquivo, 'r') as f:
print(dimacs)  # let's check the file is as promised

# steps 2 & 3 of Grover's algorithm
from qiskit import QuantumCircuit
from qiskit.circuit.library import GroverOperator
from qiskit.circuit.library import PhaseOracle
oracle = PhaseOracle.from_dimacs_file(arquivo)
grover_operator = GroverOperator(oracle)

qc=QuantumCircuit(3)
qc.h([0,1,2])
qc = qc.compose(grover_operator)

qc.measure_all()
qc.draw()

# Simulate the circuit
from qiskit import Aer, transpile
sim = Aer.get_backend('aer_simulator')
t_qc = transpile(qc, sim)
counts = sim.run(t_qc,shots=1024).result().get_counts()

print(counts)



Output:

                c example DIMACS-CNF 3-SAT
p cnf 3 4
-1 2 3 0
1 -2 -3 0
-1 -2 3 0
-1 2 -3 0

┌───┐┌────┐ ░ ┌─┐
q_0: ┤ H ├┤0   ├─░─┤M├──────
├───┤│    │ ░ └╥┘┌─┐
q_1: ┤ H ├┤1 Q ├─░──╫─┤M├───
├───┤│    │ ░  ║ └╥┘┌─┐
q_2: ┤ H ├┤2   ├─░──╫──╫─┤M├
└───┘└────┘ ░  ║  ║ └╥┘
meas: 3/═══════════════╩══╩══╩═
0  1  2

{'001': 122, '110': 119, '101': 125, '100': 110, '111': 138, '011': 139, '010': 126, '000': 145}
$$$$
`
• You're going to get a lot less answers due to needing to be able to read dimacs to understand the question. Try to reproduce the same issue without it? Dec 3, 2023 at 19:27
• Thank you for your advice. I hope the changes I made turn it easier for someone to help me. Dec 4, 2023 at 0:24
• My guess is that the issue is 50% of the answers are solutions, so one Grover step is massively over-rotating. Try a system with less than 25% solutions. Dec 4, 2023 at 0:38
• Prevision for this case is just one iteration. $$R <= \left \lceil~~\frac{\pi}{4}\sqrt{\frac{N}{m}}~~\right \rceil$$ $N=2$ $m=4$ $$R <= \left \lceil~~1.11~~\right \rceil$$ Even after two iterations, no answers appear. Dec 4, 2023 at 1:02

The easiest way to see this (at least it was for me) is by using a visualization of the system state during Grover's search as a unit circle, with horizontal axis being the superposition of all non-solution basis states and the vertical axis - the superposition of all solution basis states (see https://github.com/microsoft/QuantumKatas/blob/main/tutorials/ExploringGroversAlgorithm/VisualizingGroversAlgorithm.ipynb for the visuals). If 50% of the basis states in the search space are solutions, the system starts in the state that is tilted at an angle $$45^{\circ}$$ to the horizontal axis, and each Grover iteration rotates the state by $$90^{\circ}$$, so the state always remains exactly halfway between the vertical and the horizontal axes and always has 50% probability of measuring a state that is an answer.