Quaternionic Computing

However,onenon-negligibleconsequenceofoursimulationisthatanyparallelismthattheoriginalcircuitmayhavehadislostafterweserialisethecircuitinStep1ofthesimulationalgorithm.WhileitmightbestillpossibletoparallelisepartsoftherealcircuitC′(e.g.wherewehadrealgatesintheC),intheworstcase,ifallgatesinCrequirecomplexamplitudes,thenthetopwireisalwaysusedandthecircuitdepthforC′isequaltoitsgatecounts.Thisisaconsequenceofourdecisiontoreusethesamewireasthe“topwire”foreachgate.However,itispossibletoreducethisdepthincreaseatthecostofusingseveral“topwires”andre-combiningthemtowardstheendofthecircuit.ThiswillresultinonlyaO(logs)increaseincircuitdepth.

Finally,aswehavementionedbefore,theoverallclassicalpre-andpost-processingrequireslittlecomputationale ort.ConvertingadescriptionfortheoriginalcircuitCintoC′requirestimelinearinthesizeofthecircuitdescription,i.e.O(s).Post-processingwillbeexactlythesameasfortheoriginalquantumalgorithm,sincethestatisticsofmeasuringthebottomwiresofC′(oranysubsetthereof)willbeexactlythesameasthoseofmeasuringthewiresofC,asperLemma5.

3.4.2Universality

Weknewalready,fromthepreviousresultsmentionedinSection3.2,thatitispossibletoexpressanyquantumcircuitintermsofrealgatesonly.Ifwehadnotknownalreadythatfact,wecouldhavepresumedthatquantumcircuitswouldbedescribedandgiventousintermssomeuniversalsetofgatescontainingatleastonenon-real,complexgate.Inthatcase,Theorem2wouldprovideaproofthatarealuniversalsetcouldbeconstructed,simplybyreplacinganynon-realgatesbyitsimageunderh.

Oneadvantageofthistechniqueisthatitdoesthisconversionwithverylimitedoverheadintermsofwidth,requiring1extrarebitforthewholecircuit,andnotanextrarebitforeverysubstitutedgate,asmighthavebeenexpected.InadditiontoitsusefulnessinSection4,thisisoneofthereasonthatwebelievethatthisparticularversionoftheequivalencetheoremisinterestingofitsown,whencomparedtopreviouslyknownresults.Inparticular,thefactthatitprovidesamuchtighterboundonsimulationresourcesneeded,mightproveusefulinthestudyoflowerquantumcomplexityclassesandpossiblyinquantuminformationtheory.

3.4.3Interpretation

WithLemma5,weareleftwithacuriousparadox:whilewerequireanextrarebittoperformthesimulation,wedonotcareaboutitsinitialorits nalvalue.Inparticular,itcanbeanything,eventhemaximallymixedstate.So,whatisthisrebitdoing?

LetH0andH1betheorthogonalsubspaces,eachofdimensionN,spannedbythe|b0 and|b1 basevectorsofEquations18and19,respectively.Ifastate|Φ hasonlyrealamplitudesthen|Φ0 ∈H0and|Φ1 ∈H1.Forageneric|Φ ,however,|Φ0 and|Φ1 arenotcontainedineithernsubspace,butinthespacespannedbyboth,i.e.thecompleterebitspaceHR.Inthatcase,thetoprebitwillnotbejust|0 or|1 butsomesuperpositionthereof.