1
$\begingroup$

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:
    dimacs = f.read()
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}
```
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$ Dec 3, 2023 at 19:27
  • $\begingroup$ Thank you for your advice. I hope the changes I made turn it easier for someone to help me. $\endgroup$
    – Hadamard
    Dec 4, 2023 at 0:24
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 4, 2023 at 0:38
  • $\begingroup$ 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. $\endgroup$
    – Hadamard
    Dec 4, 2023 at 1:02

1 Answer 1

5
$\begingroup$

In this case exactly 50% of the basis states in the search space of the problem are correct answers, so any number of Grover iterations don't improve the probability of getting the answer when measuring the state - it remains 50%.

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.

$\endgroup$
2
  • $\begingroup$ Thank you for answering it. In the link you posted, there is a perfect explanation in the section "2. What happens if the solutions make up exactly half of the search space?" $\endgroup$
    – Hadamard
    Dec 4, 2023 at 4:11
  • $\begingroup$ I know, I reviewed that pull request :-) StackExchange sites encourage the answer authors to include the actual answer in the post and not just post a link, since this way the content at the link changing does not invalidate the answer. $\endgroup$ Dec 4, 2023 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.