# Connectivity in Grover's algorithm on real quantum computers

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

• Can you specify which device you were using and maybe a printout of your circuit etc. The answer has to do with the circuit depth, which in turn also have to do with the qubit connectivity... – KAJ226 Dec 5 '20 at 19:42
• Could you please post the circuit or code? What about results on simulator? If everything is righ in thi case, the problem is in quantum hardware - circuit depth and decoherece. – Martin Vesely Dec 6 '20 at 6:50
• I added the code in the post. The depth grows with the number of qubits because Grover's iteration must be repeated sqrt(N) times, where N is 2^n and n is the number of qubits. Does this mean n=3 already leads to a critic depth? – Alfred Dec 6 '20 at 8:30

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

• @Alfred That is a tricky question as Quantum Volume is calculated from square circuit. That is, quantum volume of 16 means you can run a depth 4 (before transpiled circuit which is much longer after transpilation..) where each depth involves the application of $SU(4)$ gate which is a combination of CNOTS and single qubit gates. And it just means that your circuit will success 2/3 of the time with the set-up. It doesn't correspond to any particular algorithm of anything like that. So maybe mentioning QV16 directly is not the best idea here...I just wanted to say that current device are limited. – KAJ226 Dec 6 '20 at 17:33