Quaternionic Computing(2)

Quaternionic Computing

variationfromstandardQuantumComputingisthatinwhichwechangethedomainofthestatevectoramplitudes,andhencethedomainoftheirallowedlineartransformations.

Itwas rstshownthatrestrictingourselvestorealamplitudesdoesnotdiminishthepowerofquantumcomputing[7],andfurther,thatinfactrationalamplitudesaresu cient[1].BoththeseresultswereprovenintheQuantumTuringMachinemodel,andtherespectiveproofsarequitetechnical.Directproofsofthe rstresultforthequantumcircuitmodelstemfromthefactthatseveralsetsofgatesuniversalforquantumcomputinghavebeenfound[14,8,19,18],whichinvolveonlyrealcoe cients.

Inthispaper,weintroduceanotherpossiblevariationonquantumcomputinginvolvingquater-nionicamplitudes,andproveanequivalenceresultthatshowsthatnofurthercomputationalshouldreasonablybeexpectedinthismodel.InSection2,wewillstartbyrede ningquantumcomputinginanaxiomaticfashion,whichwillmakeitpossibletoeasilygeneralisethemodelforothernon-complexHilbertspaces.Wewillrede neandreviewtheresultsknownforcom-putingonrealHilbertspacesinSection3,alsoprovidinganewgenericandstructuralproofoftheequivalenceofthismodeltostandardcomplexquantumcomputing.WewillintroducethequaternioniccomputingmodelinSection4,discusssomeofitspeculiarities,andthenshowhowtheaboveproofcanbeeasilyadaptedtothequaternioniccase.InSection5,wediscusssomeofthisresultintermsofcomputationalcomplexityandalsooftheparticularitiesofthequaternionicmodeloninitspossible“physical”interpretations.Finally,wesummariseourconclusionsandproposefurtheropenquestionsinSection6.

2QuantumComputingRevisited

ThebasictenetsofQuantumComputing,areasfollows:

States.Thepurestatesdescribingtheinternalcon gurationofannqubitcomputingdevice

arede nedas1-dimensionalraysina2n-dimensionalvectorspaceoverthecomplexnumbers.Oversuchavectorspace,theusualinner-productde nesthestandardL2-norm,whichinturnde nesaproperHilbertspace1.Withrespecttothisnorm,statesarenormallyrepresentedasunitvectors,uptoanarbitraryphasefactoreiθ,with0≤θ<2π.Measurement.Thecanonicalbasisofthisvectorspaceisgivenspecialmeaning,andcalled

thecomputationalbasis,inthatitrepresentsstateswhichalwaysgivethesameoutcomewhen“queried”abouttheirinformationcontent.Thestatesareusuallylabelledbyn-bitstringsb=b1...bn.Foragenericpurestate|Φ ,theprobabilitiesofmeasurementoutcomesaregivenbythefollowingrule

Pr(|Φ →“b”)=| Φ|b |2

where|b issomecomputationalbasisvector.(1)