# Grover's algorithm for 3SAT problem gives erroneous results

I'm writing a code in python with qiskit that implements Grover's algorithm to solve the 3-SAT problem, but when I run it it doesn't give the correct annswer. I've checked the circuit with the QuantumCircuit.draw() function and I can't find any error. The result should be one of the possible answers that satisfy the function. Here's the code and the circuit together with the result it outputs:

from qiskit import (QuantumCircuit, execute, Aer, IBMQ)
import math
import random
from qiskit.visualization import plot_histogram
import qiskit

variables = 3
clausules = 2
treball = variables - 2
temp = clausules - 1
total = variables + clausules + treball + temp

funcio = [['0', '-1', '-2'], ['0', '1', '2']]

pro_vars = []
pro_vals = []

# Process input
for i in range(len(funcio)):
pro_vars.append([])
pro_vals.append([])

for j in range(len(funcio[i])):

if funcio[i][j][0] == '-':
pro_vals[i].append(0)
pro_vars[i].append(int(funcio[i][j][1]))

else:
pro_vals[i].append(1)
pro_vars[i].append(int(funcio[i][j]))

#Quantum algorithm
opt_iter = 1#int(math.pi / 4 * math.sqrt(2**variables))

simulator = Aer.get_backend('qasm_simulator')

circuit = QuantumCircuit(variables + clausules + treball + temp + 1, variables)

# Qubit inicialization
for i in range(variables):
circuit.h(i)

circuit.h(total)
circuit.x(total)

def grover():

#Set work qubits to state 0
for i in range(variables, variables + treball):
circuit.reset(i)

#Oracle
for i in range(clausules):
for j in range(3):

if (pro_vals[i][j] == 0):
circuit.x(int(pro_vars[i][j]))

control = circuit.qbit_argument_conversion(range(variables))

work = circuit.qbit_argument_conversion(range(variables, variables + treball))

target = circuit.qbit_argument_conversion(variables + treball + i)

circuit.barrier()
circuit.OR(control, target[0], work)
circuit.barrier()

for k in range(treball):

circuit.reset(variables + k)

for j in range(len(pro_vars[i])):

if pro_vals[i][j] == 0:
circuit.x(pro_vars[i][j])

circuit.ccx(variables + treball, variables + treball + 1, variables + treball + clausules)

for i in range(0, temp - 1):
control1 = variables + treball + 2 + i
control2 = variables + treball + clausules + i
targetf = control2 + 1
circuit.ccx(control1,control2, targetf)

circuit.cx(total - 1, total)
circuit.barrier()

#Grover diffusion operator
for i in range(variables):
circuit.h(i)
circuit.x(i)

circuit.h(variables-1)

circuit.ccx(0,1,variables)

for i in range(0,variables-3):
circuit.ccx(i+2, variables + i, variables + 1 + i)
t1 = variables + 1 + i
circuit.cx(2 * (variables - 1) - 1, variables - 1)
circuit.barrier()
circuit.h(variables-1)
circuit.barrier()
for i in range(variables):
circuit.x(i)
circuit.h(i)

for i in range(opt_iter):
grover()

circuit.measure(range(variables), range(variables))

job = execute(circuit, simulator, shots=1024)
result = job.result()
counts = result.get_counts(circuit)

print("function: ", funcio)

plot_histogram(counts)

#circuit.draw()


• Hello :) could you give an example of the output you are getting? – met927 Jan 14 at 19:15