Quaternionic Computing

setofgates.Inparticular,itwillworkwithgateswhichhavearbitrarycomplextransitionamplitudes.Inotherwords,inprovingthefollowing,moregeneraltheorem,wewillcompletelyignoretheaboveresults.ThatwillallowustorecycleitsprooflateroninSection4.

Theorem2.Anyn-qubitquantumcircuitconstructedwithgatesofdegreedorless(possiblyincludingnon-standardcomplexcoe cientsgates)canbeexactlysimulatedwithann+1rebitcircuitwiththesamenumberofgatesofdegreeatmostd+1.

3.3

3.3.1ANewProofofEquivalenceTheUnderlyingGroupTheory

TheideabehindtheproofistomakeuseofthefactthatthegroupSU(N)canbeembeddedintothegroupSO(2N).Weprovideanexplicitembeddingh.4Whilethismappingisnotunique,whatisspecialaboutitisthatithasallthenecessarypropertiesforustode neasoundsimulationalgorithmbasedonit.Thismappingisde nedasfollows.GivenanarbitraryunitarytransformationU,itsimageO=h(U)is

Re(U)hU→O=h(U) Im(U)

Independently,Aharonov[3]hasalsousedthismappingrecentlytoprovideasimpleproofthatTOFFOLIandHADAMARDareuniversal.4