# OK to post homework
# Aurora Hiveley, 3/26/25, Assignment 16

Help := proc(): print(`ToffoliMatrix(), FredkinMatrix(), Sjk(j,k), QFTC(n)`): end:



# ToffoliMatrix(): and FredkinMatrix()
# return the appropriate 8 by 8 permutation matrices corresponding to each gate
# i.e. the permutation matrix representing which of the 8 gates each input is mapped to as an output

ToffoliMatrix := proc() local i: 
[seq([0$(i-1),1,0$(8-i)], i=1..6),[0$7,1],[0$6,1,0]]:
end:


FredkinMatrix := proc() local i:
[[1,0$7],[0$2,1,0$5],[0,1,0$6],seq([0$(i-1),1,0$(8-i)], i=4..8)]:
end:



# expresses the matrix Sj,k (Eq. (4.3), p. 14) in our notation of lists-of-lists
Sjk := proc(j,k) : 
[[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,e^(I*Pi/2^(k-j))]]:
end:


# QFTC(n): 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

read `QC.txt`:
R := C1QG()[7]:

QFTC := proc(n) local M,L,j:
L := seq( op([ [[-j],R], [[-j-1,-j+1], Sjk(-j-1,-j+1)], [[-j-1,-j], Sjk(-j-1,-j) ] ]), j=-(n-2)..-1 ):
M := [ [[[n-1],R]], [[n-2,n-1], Sjk(n-2,n-1)] , L , [[0],R] ]:

[n, M]:
end:


# test symbollically by changing Sjk to S and commenting out definition of R 
# sure enough, QFTC(3) matches with Shor's paper