from qiskit import *
import numpy as np
import matplotlib as mpl
from qiskit.tools.visualization import plot_histogram, plot_state_city
from qiskit.tools.monitor import job_monitor

state_sim = Aer.get_backend('statevector_simulator')
qasm_sim = Aer.get_backend('qasm_simulator')
unitary_sim = Aer.get_backend('unitary_simulator')

qiskit.__qiskit_version__   #developed in q0.14.0, q-terra0.11.0

# Definition of c_Increment, c_Decrement gates

def increment(qc,qr):
    """controlled-increment gate, cf. PhysRevA.72.032329"""
    for i in range(num_qubits - 1):
        qc.mct(qr[0:num_qubits - 1 - i], qr[num_qubits - 1 - i] , qr_aux)
        
def decrement(qc,qr):
    """controlled-decrement gate, cf. PhysRevA.72.032329"""
    for i in range(num_qubits - 1):
        qc.mct(qr[0:i+1], qr[i+1], qr_aux)
        
# Definition of QW cycle

def quantum_walk(qc,qr):
    """implement DTQW on a previously defined circuit and register cf. PhysRevA.72.032329"""
    # coin operator
    qc.h(qr[0])
    
    # conditional shift
    increment(qc,qr)
    qc.x(qr[0])
    decrement(qc,qr)
    qc.x(qr[0])
        
def get_tot_gates(qc):
    """get the total number of basic gates of a circuit"""
    tot_gates = 0

    for key in qc.decompose().count_ops():
        tot_gates = tot_gates + qc.decompose().count_ops()[key]
    
    return tot_gates

def get_cx_gates(qc):
    """get the total number of cx gates of a circuit"""
    cx_gates = qc.decompose().count_ops()['cx']
    
    return cx_gates

# Analysis of gate number

x = []  # number of qubits
y = []  # number of gates of one QW step

for q in range(4,30):
    # Total number of qubits (nodes + coin)
    num_qubits = q
    
    # Define qRegister and qCircuit
    qr = QuantumRegister(num_qubits, 'qr')
    cr = ClassicalRegister(num_qubits - 1, 'cr')

    # We need (num_control - 2) aux qubits for mct
    if num_qubits > 3:
        qr_aux = QuantumRegister(num_qubits - 3, 'aux')
        qc = QuantumCircuit(qr,qr_aux,cr)
    else:
        qr_aux = None
        qc = QuantumCircuit(qr,cr)

    # Running the QW

    quantum_walk(qc,qr)
    
    x.append(q)
    y.append(get_cx_gates(qc))

print(x,y)
mpl.pyplot.plot(x,y)
mpl.pyplot.xlabel('number of qubits')
mpl.pyplot.ylabel('number of gates')
mpl.pyplot.title('Number of CX gates required for a QW step')
mpl.pyplot.grid(True)
mpl.pyplot.show()

