Quaternionic Computing

Thecanonicalvaluesofthequaterbitcorrespondtothecanonicalbasis|0 and|1 ofthatvectorspace,andaregiventhesamesemanticsjustasbefore.Similarly,wecande nen-quaterbitstates,withthesamecanonicalbasisasforrebitsandqubits.Withthisde nition,themeasurementruleinEquation1isstillsoundandweadoptitaxiomatically.

Quaternionsareoftenusedincomputergraphicstorepresentrotationsofthe3DEuclideanspace.However,contrarytorebitsorqubits,wehavenotfoundanicegeometricinterpretationforthestatespaceofevenasinglequaterbit.

4.1.3QuaternionicCircuits

Forthesakeofclarity,letusdistinguishtheconjugatetransposeoperationforquaternionandcomplexmatricesbyrepresentingthemdi erentlywiththe( )and( )symbols,respectively.Asbefore,theonlyrelevantlineartransformationsQthatpreservel2normonthisvectorspacearethequaternionicunitarytransformations,whichhavethesamepropertyQ =Q 1ascomplexunitarytransformations.Theyformtheso-calledsymplecticgroupwhichisrepresentedasSp(N).

Thusarmedwithlinear,inner-productpreservingoperations,wecaninprinciplede nequater-nioniccircuitsinasimilarfashionaswede nedquantumandrealcircuits.Unfortunately,wecannotapplythesamede nitionofcomputationsemanticsasbefore,andthuscannotde nequaternionicalgorithmsinthesamewayeither.Thereasonissimpleandquitesurprising:theoutputofaquaternioniccircuitisnotuniquelyde ned!

Toseethis,considerthefollowingpropertyofthematrixtensorproduct,i.e.thedistributivityofthetensorproductwiththeregularmatrixproduct.

Quaternionic Computing

SupposenowthatthematricesA,B,C,DcorrespondtothegatetransformationsinthecircuitdepictedinFigure6.Then,thefactthatEquation46doesnotholdmeansthatthetwodi erentwaysshownthereofcombiningthegateswillyielddi erentoperatorsforthecircuit.Furthermore,evenifweinitialiseinbothcaseswiththesameinput,wewillobtaindi erentoutputstatistics.

Tofurtherillustratethisparadoxitisusefultothinkofthestatesofacircuitintermsoftemporalcutsinthecircuitgraph(see[10]foramoredetaileddescriptionofthisformalism).Wecanthinkofthesetofallpossiblestatesofagivencircuitgraphasitsdiscrete“space-timecontinuum.”Thecircuittopologyde nesanorderingonthissetthatisnaturallyassociatedwithastatebeing“before”or“after”another.Itishoweveronlypartiallyorderedassomestatesaretemporallyincomparable,i.e.thosecorrespondingtocutsofthegraphthatcrosseachother.Eachtopologicalsortofthecircuitgraphisoneofthemanypossibletotalorderingsofthesetofcuts,orinotherwordsachainintheposet(partially-orderedset)ofcuts,alsocorresponding,aswesawinSection3.3,toanevaluationsequenceofgates.Inmorephysicalterms,eachofthesechainsortotalorderscorrespondstoapossiblepathinthespace-timecontinuumofthecircuit.

WhenEquation46holds,weareguaranteedthattheoveralloperatorovereachandallofthesepathswillbethesame.However,inthecaseofthequaternioniccircuits,wecanexpecteachofthesepathstogiveadi erentanswer.Whichofthesemanypaths(forapoly-sizecircuit,thereareexponentiallymanyofthem)isthe“correct”one?Whichoneissomehowprivilegedbynature?Whichoneshouldwechoosetobethe“computationaloutput”ofthecircuit?Thefactisthatwedonotknowhowtoresolvethisambiguity,andwithoutdoingit,itisnotcompletelyclearwhat“the”modelofquaternioniccomputingshouldconsistof.

Wecangetoutofthisimpassebyallowingfora“parametrised”notionofaquaternionicalgorithm.

beaquaternioniccircuitofsizeDe nition4(OutputofaQuaternionicCircuit).LetC

sandletσ=(σ1,...,σs)representoneofthepossibletopologicalsortsofthecorresponding underσ,whichisobtainedwhencircuitgraph.WedenotebyQσtheoperatorofthecircuitC

thegatesarecombinedone-by-onefollowingtheorderinginσ,i.e.

Qσ=Q(s)Q(s 1)···Q(2)Q(1),

whereQ(i)isthe(in-context)operatorcorrespondingtothei-thgateinσ.

De nition5(QuaternionicAlgorithm).Aquaternionicalgorithmisde nedasaclassical TM,whichon(classical)inputxwillgeneratea(classical)descriptionofaquaternioniccircuitCanda(classical)descriptionofoneofitspossibletopologicalsortsσ.Theresultofmeasurementofthe nalstate|Φ =Qσ|Ψ0 ,where|Ψ0 isthedefaultinitialstate,isthenpost-processedbytheTMtoproduceits nal(classical)answer.

Relativetothissomewhatunsatisfyingnotionofquaternioniccomputation,wearestillabletoobtainthefollowingequivalenceresult.Thistheoremisthemainresultofthisarticle,anditsproofisveryheavilyinspiredfromthatofTheorem2.