# Ok to post homework
# Lucy Martinez, 03-25-2025, Assignment 16

with(combinat):

######################
#Problem 2: Read Peter Shor's seminal paper p. 9 and write procedures
# ToffoliMatrix() and FredkinMatrix() that returns the appropriate 8 by 8 matrices


ToffoliMatrix:=proc():
[
[1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0],
[0,0,0,1,0,0,0,0],
[0,0,0,0,1,0,0,0],
[0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,1,0]
]:
end:

FredkinMatrix:=proc():
[
[1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0],
[0,0,0,1,0,0,0,0],
[0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,1,0],
[0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1]
]:
end:


#Problem 3: Write a procedure Sjk(j,k) that expresses the matrix Sj,k
# (Eq. (4.3),# p. 14) in our notation of lists-of-lists
Sjk:=proc(j,k):
if j<k then
 return [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,evalf(exp(I*Pi/2^(k-j)))]]:
fi:
end:


#Problem 4: Write a procedure QFTC(l) that inputs a pos. integer n
# and outputs the quantum circuit of Eq. (4.4) (but replace l by n)
# in the same format at the output of RQC. i,e.
# [n,[R(),[n-1]], .... where R is the Hadamard matrix
QFTC:=proc(n) local R,L,i,k:
R:=C1QG()[7]:
L:=[]:
for i from n-1 by -1 to 1 do
 L:=[op(L), [R,i]]:
 L:=[op(L), seq([Sjk(i-1,k),i-1,k],k=i..n-1)]:
od:
[op(L),[R,0]]:
end:



####################################previous classes:
#C16.txt, March 24, 2025 QFT
Help16:=proc():
print(`QFT(q)`):
end:

#QFT(q): The q by q matrix of the Fast Fourier transform
QFT:=proc(q) local a,c:
[seq([seq(exp(2*Pi*I*a*c/q), c=0..q-1)], a=0..q-1)]:
end:


####
#C1QG(): the list of the seven most imporant one-qubit gates (unitary 2 by 2 matrices) in lists-of-lists format
#in that order: Identity `, ` PauliX `, `PauliY `, `PauliZ `, ` PhaseS `, `TPi/8` , ` Hadamard `
#Try:
#C1QG();
C1QG:=proc():
[
[[1,0],[0,1]],
[[0,1],[1,0]],
[[0,-I],[I,0]],
[[1,0],[0,-1]],
[[1,0],[0,I]],
[[1,0],[0,sqrt(2)/2+sqrt(2)/2*I]],
expand([[1,1],[1,-1]]/sqrt(2))
]:
end: