Everytime I execute Grover's search algorithm on IBM real quantum computers I get a wrong answer (it doesn't find the correct winner state) unless I use only 2 qubits. For any higher number of qubits it fails. I've already maximized the number of shots and tried with every free device. Also, the algorithm works perfectly in every simulation with any number of qubits. Could this be a connectivity problem? Do I need each qubit to be connected to all the other ones in the circuit for Grover's algorithm to work?
Here is the Python code I am using. It implements a generalized Grover's algorithm for n qubits.
import matplotlib.pyplot as plt
import numpy as np
from math import *
from qiskit import *
from qiskit.tools.visualization import circuit_drawer, plot_histogram
from qiskit.quantum_info.operators import Operator
def computational_basis(number_of_qubits, space_dimension):
basis = []
for i in range(space_dimension):
a = bin(i)[2:]
l = len(a)
b = str(0) * (number_of_qubits - l) + a
basis.append(b)
return basis
def scalar_product(a, b): # Where a and b are two items of the "basis" list
if a == b:
return 1
else:
return 0
def oracle_generator(space_dimension, winner_state):
for i in range(space_dimension):
if basis[i] == winner_state:
mark = basis.index(basis[i])
oracle_matrix = np.identity(space_dimension)
oracle_matrix[mark, mark] = -1
oracle = Operator(oracle_matrix)
return oracle
def diffuser_generator(space_dimension):
diffuser_matrix = np.empty((space_dimension, space_dimension))
for i in range(space_dimension):
for j in range(space_dimension):
diffuser_matrix[i, j] = (2 * scalar_product(basis[i], basis[0]) * scalar_product(basis[0], basis[j])) - scalar_product(basis[i], basis[j])
diffuser = Operator(diffuser_matrix)
return diffuser
def grover_iteration(number_of_qubits, circuit, qr):
all_qubits_list = []
for i in range(n):
all_qubits_list.append(i)
circuit.unitary(oracle, all_qubits_list, label='oracle')
for i in range(number_of_qubits):
circuit.h(qr[i])
circuit.unitary(diffuser, all_qubits_list, label='diffuser')
for i in range(number_of_qubits):
circuit.h(qr[i])
# Number of qubits
n = 3
# Space dimension
N = int(pow(2, n))
# Winner state
winner = '111'
# Make a list of computational basis vectors (strings)
basis = computational_basis(n, N)
# Build a quantum circuit for n-qubit Grover's algorithm
oracle = oracle_generator(N, winner)
diffuser = diffuser_generator(N)
qr = QuantumRegister(n, 'q')
cr = ClassicalRegister(n, 'c')
grover_circuit = QuantumCircuit(qr, cr)
for i in range(n):
grover_circuit.h(qr[i])
if n == 2:
grover_iteration(n, grover_circuit, qr)
else:
for i in range(int(sqrt(N))):
grover_iteration(n, grover_circuit, qr)
grover_circuit.measure(qr, cr)
# Draw Grover circuit
circuit_drawer(grover_circuit, output='mpl')
plt.show()
# Execute circuit
IBMQ.load_account()
provider = IBMQ.get_provider('ibm-q')
qcomp = provider.get_backend('ibmq_valencia')
job = execute(grover_circuit, backend=qcomp, shots=8192)
result = job.result()
# Results
plot_histogram(result.get_counts(grover_circuit))
plt.show()