# 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... Dec 5, 2020 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. Dec 6, 2020 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? Dec 6, 2020 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
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)

• Thank you for your answer. Just to have an idea, how big should the Quantum Volume be to sustain such a depth (more or less)? Dec 6, 2020 at 17:19
• @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. Dec 6, 2020 at 17:33