Quaternionic Computing

whereinthiscasewecandropthemodulusoperator|·|,becauseitisredundant.

Onephysicalinterpretationthatcanbegivenforrebitsorrebitsystemsisthatofasystemofphotons,whereweusethepolarisationintheusualmannertocarrytheinformation.However,thesephotonsarerestrictedtohavingzerocircularpolarisation,andbeingoperateduponwithpropagatorswhichneverintroducecircularpolarisation,i.e.orthonormaloperators.Thecomputationalbasismeasurementsarestillsimplepolarisationmeasurementsinthevertical-horizontalbasis.

RealCircuitsandRealComputationalComplexity

Wecanalsode neandconstructrealcircuits,asarestrictionofquantumcircuits.Topologically,theyarethesame,aswewillstillrequirethemtobeconstructedonlywithreversiblegates.Sinceorthonormalmatrices,likeunitarymatrices,arepreservedunderthetensoralgebrathatdescribescircuitconstructions(see[5,6]formoredetailsonthisformalism),itissu cienttorequirethattheelementarygatesbeorthonormal.Withthis,weareassuredthattheoverallcircuittransformationwillbenorm-preserving.Wecanthende neameasurementruleforcircuitstates,whichwillyieldclassicalresultswithprobabilitiesexactlyasinEquation7.Aswasnotedbefore,thisruleiscompletelygeneralanddoesnotdependonthe eldonwhichtheinner-productspaceofstatesisde ned.

RealAlgorithms

Tocompletethede nitionofthiscomputationalmodel,wemustde newhatitmeansforsuchrealcomputingdevicesto“compute”orto“solveaproblem.”Forthat,wesimplyrestrictthede nitionofaquantumalgorithmgivenabove.

De nition2(RealAlgorithm).Arealalgorithmisde nedasaclassicalTM,whichon(classical)inputxwillgeneratea(classical)descriptionofarebitcircuit.Theresultofmea-surementofthe nalstate|Φ oftherebitcircuitispost-processedbytheTMtoproduceits nal(classical)answer.

TheTMcanbeviewedashavingaccesstoauniversalcircuitevaluatorororacle,whichwillproduceaclassicalanswerb,withtheprobabilitiesde nedinEquation7.Itisimportanttonotethatnomatterwhatclassicalpost-processingtheclassicalTuringMachinedoesafterobtainingananswerfromtheOracle,its nalanswerultimatelyonlydependsontheoutcomeprobabilities.Inotherwords,fromtheTM’spointofview,itdoesnotmatterifthecircuitisphysicallyconstructedorjustsimulatedbytheOracle,nordoesitmatterwhattechnologywasusedorwhatmathematicalabstractionwasemployedinitssimulation.WhatmattersisthattheoutcomeprobabilitiesoftheOraclebethesameasthoseofcircuitdescriptionprovidedbytheTM.

3.2PreviouslyKnownResults

FromaComplexityTheorypointofview,the rstquestionthatarisesnaturallyishowdoesthisrealcomputingmodelcomparewiththequantumcomputingone.Inotherwords,canthe