Quaternionic Computing

wherewealsousedthefollowinggenericmatrixidentities

Re(A )=Re(A)t

Im(A )= Im(A)t.(16)

Inparticular,wehavethatOt=h(U)t=h(U )=h(U 1)=O 1,andwearedoneprovingTheorem3.

Thefactthathisagroupisomorphismisimportant,becauseitimpliesthatGNispreservedunder“serial”circuitconstruction.Inotherwords,itmeansthatifwehaverealcircuitsthatsimulatethequantumcircuitswithoperatorsUandV,thenwecansimulateaquantumcircuitwithoperatorUVbysimplyputtingbothrealcircuitstogether.Thissuggestsawayinwhichtodecomposetheproblemofsimulatingagenericquantumcircuit,i.e.byconstructingtherealcircuitonelevelatatime.

3.3.2TheSimulationAlgorithm

LetCbeagenericn-qubitquantumcircuitwithoperatorUC,composedofselementarygates.Thesimulationalgorithmwillconsistofthefollowingsteps:

Step1.Serialisethegivencircuitby ndinganorderingofitsgates,sothattheycanbe

evaluatedinthatorder,onebyone.Inotherwords, ndatotalorderofthecircuitgates,suchthatUC=U(s)U(s 1)...U(2)U(1).

Step2.Foreachgateg∈{1,...,s}intheaboveordering,replacethen-aryoperationU(g),

correspondingtotheg-thgate,withanadequaterealcircuitO(g)simulatingit.

Step3.ConstructtheoverallrealcircuitC′byconcatenatingthecircuitsforeachlevelg,in

thesameorderasde nedinStep1.Thisis,ifOCistheoperatorforC′,thenletOC=O(s)...O(2)O(1).

Step4.WriteadescriptionoftherealcircuitC′andofitsinputstateandaskthereal

computing“oracle”toprovidetheresultofameasurementonits nalstate.

Step5.Performtheclassicalpost-processingontheresultofthemeasurementandprovidea

classicalanswer.

Thealgorithm,asdescribedsofar,isnotcompletelyde ned.Inwhatfollows,wewillderive,onebyone,themissingdetails.

First,thetotalorderinStep1canbeobtainedbydoingatopologicalsortofthecircuit’sdirectedgraph.Thiscanbedonee cientlyintimepolynomialinthesizeofthecircuit5.Thee ectsofStep1onCaredepictedinFigure1.