from qiskit import *
import numpy as np

n = 5

control_reg = QuantumRegister(n, 'c')
target_reg  = QuantumRegister(1, 't')
ancilla_reg = QuantumRegister(1, 'a')
circuit     = QuantumCircuit(control_reg, target_reg, ancilla_reg)

circuit.mct(control_reg[:int(np.ceil(n/2))], ancilla_reg[0])
circuit.mct(control_reg[int(np.ceil(n/2)):] + ancilla_reg[:], target_reg[0])
circuit.mct(control_reg[:int(np.ceil(n/2))], ancilla_reg[0])
circuit.mct(control_reg[int(np.ceil(n/2)):] + ancilla_reg[:], target_reg[0])

circuit.draw('mpl')

def n_m_2_ancilla(circuit, control_reg, target_reg, ancilla_reg):
    n = len(control_reg)
    
    # first mountain
    circuit.ccx(ancilla_reg[-1], control_reg[-1], target_reg[0])
    for i in range(n - 4, -1, -1):
        circuit.ccx(ancilla_reg[i], control_reg[i + 2], ancilla_reg[i + 1])
    circuit.ccx(control_reg[0], control_reg[1], ancilla_reg[0])
    for i in range(0, n - 3):
        circuit.ccx(ancilla_reg[i], control_reg[i + 2], ancilla_reg[i + 1])
    circuit.ccx(ancilla_reg[-1], control_reg[-1], target_reg[0])

    # second mountain, i.e., uncomputation
    for i in range(n - 4, -1, -1):
        circuit.ccx(ancilla_reg[i], control_reg[i + 2], ancilla_reg[i + 1])
    circuit.ccx(control_reg[0], control_reg[1], ancilla_reg[0])
    for i in range(0, n - 3):
        circuit.ccx(ancilla_reg[i], control_reg[i + 2], ancilla_reg[i + 1])

n = 5

control_reg = QuantumRegister(n, 'c')
target_reg  = QuantumRegister(1, 't')
ancilla_reg = QuantumRegister(n - 2, 'a')
circuit = QuantumCircuit(control_reg, target_reg, ancilla_reg)        

n_m_2_ancilla(circuit, control_reg, target_reg, ancilla_reg)

circuit.draw('mpl')

n = 7

control_reg = QuantumRegister(n, 'c')
target_reg  = QuantumRegister(1, 't')
ancilla_reg = QuantumRegister(1, 'a')
circuit     = QuantumCircuit(control_reg, target_reg, ancilla_reg)

for _ in range(2):
    # first gate
    controls = [i for i in range(n) if i % 2 == 0]
    target   = [-1]
    ancilla  = [i for i in range(n) if i not in controls]
    while len(ancilla) != len(controls) - 2:
        ancilla.pop(0)
    n_m_2_ancilla(circuit, controls, target, ancilla)

    circuit.barrier()

    # second gate
    controls = [i for i in range(n) if i % 2 == 1] + [n + 1]
    target   = [-2]
    ancilla  = [i for i in range(n) if i not in controls]
    while len(ancilla) != len(controls) - 2:
        ancilla.pop(0)
    n_m_2_ancilla(circuit, controls, target, ancilla)

    circuit.barrier()

circuit.draw('mpl')