from qiskit import QuantumCircuit
from qiskit import QuantumRegister, QuantumCircuit
c = QuantumRegister(1, 'control')
t = QuantumRegister(2, 'target')
cu = QuantumCircuit(c, t, name="Controlled 13^x mod 35")

# Your code goes here

# easy (non-optimal) solution:

cu.ccx(c, t[0], t[1])
cu.cx(c, t[0])

# end solution

cu.draw()

c = QuantumRegister(1, 'control')
t = QuantumRegister(2, 'target')
cu2 = QuantumCircuit(c, t)

# Your code here

# Non-optimal solution:
cu2 = cu.compose(cu)
# end solution

cu2.draw()

c = QuantumRegister(1, 'control')
t = QuantumRegister(2, 'target')
cu4 = QuantumCircuit(c, t)

# Your code here

# VERY bad solution (to be removed):
cu4 = cu2.compose(cu2)
# end solution

cu4.draw()

cqr = QuantumRegister(3, 'control')
tqr = QuantumRegister(2, 'target')
cux = QuantumCircuit(cqr, tqr)
solutions = [cu, cu2, cu4]
for i in range(3):
    cux = cux.compose(solutions[i], [cqr[i], tqr[0], tqr[1]])
cux.draw()

# To be removed before the challenge
from qiskit.circuit.library import QFT
from qiskit import transpile
import numpy as np
cqr = QuantumRegister(3, 'control')
tqr = QuantumRegister(2, 'target')
cux2 = QuantumCircuit(cqr, tqr)
cux2.append(QFT(2, do_swaps=False), [3, 4])
cux2.cz(0, 3)
cux2.cp(np.pi/2, 0, 4)
cux2.cz(1, 4)
cux2.append(QFT(2, inverse=True, do_swaps=False), [3, 4])
display(cux2.draw())

t_cux2 = transpile(cux2, basis_gates=['u','cx'], optimization_level=3)
display(t_cux2.draw())
t_cux2.count_ops()['cx']

from qiskit.circuit.library import QFT
from qiskit import ClassicalRegister
cr = ClassicalRegister(3)
shor_circuit = QuantumCircuit(cqr, tqr, cr)
shor_circuit.h(cqr)

shor_circuit.compose(cux2, inplace=True)

shor_circuit.append(QFT(3, inverse=True, do_swaps=True), cqr)
shor_circuit.measure(cqr, cr)
shor_circuit.draw()

from qiskit.test.mock import FakeAthens
from qiskit import assemble
from qiskit.visualization import plot_histogram

# we can do some more transpiling to squeeze out extra performance, but this isn't necessary
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import HoareOptimizer
athens = FakeAthens()
tqc = transpile(shor_circuit, athens, optimization_level=3)
pm = PassManager(HoareOptimizer())
tqc = pm.run(tqc)
counts = athens.run(assemble(tqc)).result().get_counts()
plot_histogram(counts)