Connectivity in Grover's algorithm on real quantum computers

Question

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()

Answer 1

After ran your code, which have a circuit structure of the form:

However, mapping it to Valencia, which has qubit connectivity map as:

then the transpiled circuit takes the form:

Which after asking Qiskit to spit out the circuit depth and all the gate operations we have:

Transpiled circuit depth 122

Quantum operations used: OrderedDict([('cx', 73), ('u2', 59), ('u1', 21), ('u3', 9), ('measure', 3), ('barrier', 1)])

Then we see that the transpiled circuit is quite long and the probability of the circuit running with succession is not so positive as Valencia only has Quantum Volume of 16.

---

As a note on how to get the transpiled circuit and its depth and different operations, you can do the following:

from qiskit.compiler import transpile
provider = IBMQ.load_account()
Circuit_Transpile = transpile(grover_circuit, provider.get_backend('ibmq_valencia') , optimization_level=3)
print('Transpiled circuit depth', Circuit_Transpile.depth() )
print('Quantum operations used:', Circuit_Transpile.count_ops())
Circuit_Transpile.draw( 'mpl',style={'name': 'bw'}, filename = 'transpiled circuit', plot_barriers= False, initial_state = True, scale = 1)