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} ```
Improve this question
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Dec 4, 2023 at 1:02

1 Answer 1

Reset to default
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.

Improve this 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$ Commented 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$ Commented Dec 4, 2023 at 5:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.