# A Quantum Circuit to Construct All Maximal Cliques Using Grover’s Search Algorithm

## Chu Ryang Wie

### DOI: https://arxiv.org/abs/1711.06146v2

import matplotlib
#matplotlib.use('Agg')
import matplotlib.pyplot as plt
from qiskit import *
# IBMQ.load_account()
from qiskit.visualization import *

n = 3 # size of network
psi  = QuantumRegister(n, name='psi') # cliques states
data = QuantumRegister(n**2, name='data') # data A+I states
ancl = QuantumRegister(n**2, name='ancl') # ancilla states
cpsi = ClassicalRegister(n, name='cpsi') # classical register for measurement
cdata = ClassicalRegister(n**2, name='cdata') # classical register for measurement
cancl = ClassicalRegister(n**2, name='cancl') # classical register for measurement

#extra_ancl = QuantumRegister(n**2, name='extra_ancl')
qc   = QuantumCircuit(psi, data, ancl, cpsi, cdata, cancl, name='maximal cliques')

import numpy as np
A = np.array([ # creating adjacency matrix
    [0,1,0],
    [1,0,1],
    [0,1,0]
], dtype=np.int)

AI = A+ np.eye(n, dtype=np.int)


# setting network structure on data qubits
for ij, cij in enumerate(AI.flatten()):
    if cij:
        qc.x(data[ij])

# putting cliques on uniform superposition
for j in range(n):
    qc.h(psi[j])

def V():
    for j in range(n):
        for i in range(n):
            # applying 'intersect operator' as defined in paper
            qc.barrier()
            # standard toffoli
            qc.ccx(psi[j], data[j*n+i], ancl[j*n+i])
            
            # toffoli variant - 1st ctrl qbit works when 0
            qc.x(psi[j])
            qc.ccx(psi[j], data[j*n+i], ancl[j*n+i])
            
            # toffoli variant - 1st & 2nd ctrl qbit work when 0
            qc.x(data[j*n+i])
            qc.ccx(psi[j], data[j*n+i], ancl[j*n+i])
            
            # undoing NOT operations
            qc.x(psi[j])
            qc.x(data[j*n+i])

def W():
    for j in range(n):
        # trying to use multi-controlled toffoli gate available in qiskit (not sure if it works)
        #qc.mct(ancl[j::n], psi[j], extra_ancl)
        #QuantumCircuit.mct(q_controls, q_target, q_ancilla, mode='basic')
        qc.barrier()
        qc.mct(ancl[j::n], psi[j], None, mode='noancilla')

def flip_ket_0():
    for j in range(n):
        qc.x(psi[j])
    qc.h(psi[n-1])
    qc.barrier()
    qc.mct(psi[:-1], psi[-1], None, mode='noancilla')
    qc.barrier()
    qc.h(psi[n-1])
    for j in range(n):
        qc.x(psi[j])

def O():
    qc.barrier()
    V()
    qc.barrier()
    W()
    qc.barrier()
    flip_ket_0()
    qc.barrier()
    W()
    qc.barrier()
    V()


def G():
    qc.barrier()
    for j in range(n):
        qc.h(psi[j])
    qc.barrier()
    for j in range(n):
        qc.x(psi[j])
    
    qc.barrier()
    qc.h(psi[-1])
    
    qc.barrier()
    qc.mct(psi[:-1],psi[-1],None,mode='noancilla')
    
    qc.barrier()
    qc.h(psi[-1])
    
    qc.barrier()
    for j in range(n):
        qc.x(psi[j])
    qc.barrier()
    for j in range(n):
        qc.h(psi[j])

O()
G()



qc.barrier()
qc.measure(psi, cpsi)
qc.measure(data, cdata)
qc.measure(ancl, cancl)

fig = circuit_drawer(qc, output='mpl', filename='circuit.pdf', fold=300)
#fig

res = execute(qc, Aer.get_backend('qasm_simulator'), shots=4096).result()
print(res)
print(res.get_counts())

plot_histogram(res.get_counts())





# Running on IBMQ Experience

# saving account credentials first
#IBMQ.save_account('MY_TOKEN_ID')

# loading IBMQ session
provider = IBMQ.load_account()
backend = provider.backends(simulator=True,operational=True)[0]
res = execute(qc, backend, shots=8192).result()
plot_histogram(res.get_counts())



# TODO: create circuit for n=2 network and test it on melbourne qpu.