Quaternionic Computing

Quaternionic Computing

QuaternionicComputing

Jos´eM.Fernandez,WilliamA.Schneeberger

arXiv:quant-ph/0307017v2 5 Nov 2004February1,2008AbstractWeintroduceamodelofcomputationbasedonquaternions,whichisinspiredonthequantumcomputingmodel.Purestatesarevectorsofasuitablelinearspaceoverthequaternions.Otheraspectsofthetheoryarethesameasinquantumcomputing:super-positionandlinearityofthestatespace,unitarityofthetransformations,andprojectivemeasurements.However,onenotableexceptionisthefactthatquaternioniccircuitsdonothaveauniquelyde nedbehaviour,unlessatotalorderingofevaluationofthegatesisde ned.Givensuchanorderingauniqueunitaryoperatorcanbeassociatedwiththequaternioniccircuitandapropersemanticsofcomputationcanbeassociatedwithit.Themainresultofthispaperconsistsinshowingthatthismodelisnomorepowerfulthanquantumcomputing,aslongassuchanorderingofgatescanbede ned.Moreconcretelyweshow,thatforallquaternioniccomputationusingnquaterbits,thebehaviourofthecircuitforeachpossiblegateorderingcanbesimulatedwithn+1qubits,andthiswithlittleornooverheadincircuitsize.Theproofofthisresultisinspiredofanewsimpli edandimprovedproofoftheequivalenceofasimilarmodelbasedonrealamplitudestoquantumcomputing,whichstatesthatanyquantumcomputationusingnqubitscanbesimulatedwithn+1rebits,andinthiswithnocircuitsizeoverhead.Beyondthispotentialcomputationalequivalence,however,weproposethismodelasasimplerframeworkinwhichtodiscussthepossibilityofaquaternionicquantummechanicsorinformationtheory.Inparticular,italreadyallowsustoillustratethattheintroduction

ofquaternionsmightviolatesomeofthe“natural”propertiesthatwehavecometoexpectfromphysicalmodels.

1Introduction

QuantumComputingrepresentsyetanotherdisconcertingpuzzletoComplexityTheory.Whatweknowtodayisthatquantumcomputingdevicescane cientlysolvecertainproblems,which,inappearance,classicalorprobabilisticcomputerscannotsolvee ciently.EventhoughwewouldliketobelievethatquantumcomputingviolatesthestrongChurch-Turingthesis,thesoretruthisthattheknownresultsdonotprovideusaproof,onlyconstituting,atbest,“strongevidence”thereof.

Yet,eventhoughwecannotprovideastrictseparationbetweenthesemodels,wedoknowcertaininclusionsbetweenvariationsofthesecomputingmodels.Perhapsthemostnatural

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)

Quaternionic Computing

Transformations.Generallyspeaking,thetransformationsthatareallowedarelinearmap-

pings.Inaddition,inorderforthequantitiesabovetobeproperprobabilities,thesetransformationsmustpreserveL2-norm.TheonlyrelevantlinearandL2-normpreserv-ingoperationsareunitarytransformations2.Theseareusuallyrepresentedinthematrixforminwhichthecolumnvectorsaretheimagesofthecanonicalbasisunderthegiventransformation,listedinlexicographicalorder.

Circuits.Thecomputationaldeviceismodelledasacircuit,which,withoutlossofgenerality,

canbeassumedtohavethefollowingcharacteristics

Theinputtothecircuitisanypurestate. Thecircuitisanarrayofelementaryuniversalgates.

Forexample,wecanchoosethe2-qubitCNOTgateandarbitrary1-qubitrotationsasauniversalset.Furthermore,weallowgatestooperateonanytwoarbitrarywires,notnecessarilycontiguous3.

Algorithms.AquantumalgorithmcanbeformallydescribedasaclassicalTuringMachine,

whichgivenaclassicalstringxwillgeneratea(classical)descriptionforaquantumcircuit.Thequantumcomputercanthenproduceananswerbasedontheresultofmeasurementsoftheoutputwiresofthequantumcircuit.Withoutlossofgenerality,wecanassumethatthecircuitistobeevaluatedwiththegroundstate(theallzerocomputationalbasevector)asitsinitialstate.Thealgorithmissaidtobee cientifthecorrespondingTMrunsintimepolynomialonthesizeoftheinputx,whichinturnsimpliesthatcircuitsizeisalsopolynomial.

Fromapurelyabstractpointofview,itcanbeinferredthattheonlyrequirementsofthismodelisthatthestatespacehasalinearstructureandapropernorm-inducinginnerproduct,sothatthemeasurementruleisalwayssound.Traditionally,quantumcomputinghasbeendescribedintermsofcomplexHilbertspaces,butinprinciple,aswejustdiscussed,asoundmodelofcomputationcanbede nedonanyotherHilbertspace.Inparticular,inthispaperwestudymodelsofrealcomputingandquaternioniccomputing,basedonthe2n-dimensionalvectorspacesontherealsandthequaternions,respectively.

3

3.1RealComputingDe nitions

Intuitively,therealcomputingmodelisde nedasarestrictedversionofquantumcomputing,whereallamplitudesinthestatevectorsarerequiredtoberealnumbers.Conjugationis

Quaternionic Computing

equivalenttotheidentityoperationandbrasaresimplytransposedkets.Similarlythematrixdaggeroperator( )canbereplacedwiththematrixtransposeoperator(t).

Inthiscase,wemustreplaceunitarytransformationswithorthonormaltransformations,asthesearetheonlyinner-productpreservingoperationsonthisinner-productspace.Onecouldconceiveamodelinwhichthestatevectorsalwayshaverealamplitudes,butinwhicharbitraryunitarytransformations(onthecomplexHilbertspace)areallowed,aslongastheendresultisstillarealamplitudevector.Itiselementarytoshowthatorthonormaltransformationsaretheonlyonesthathavethisproperty,andhencethismodelisasgeneralascanbe,giventhefactthatweinsistthattheamplitudesbereal.

RebitsandStates

Inquantumcomputingandquantuminformationtheory,wede nethequbitasthemostelementaryinformation-containingsystem.Abstractly,thestateofaqubitcanbedescribedbya2-dimensionalstatevector

|Φ =α|0 +β|1 ,s.t. Φ 2=

a2+b2=1(4)

Inthiscase,thearbitraryphasefactorcanonlybe+1or 1,andtherebitequivalencerelationwhichreplacesEquation3is

Φ≡Φ′ |Φ =eiθ|Φ′ ,whereθ∈{0,π} |Φ =±|Φ′ (5)(6)

Similarlyasforqubits,singlerebitstatesdohaveanicegeometricalinterpretation:theyareisomorphictothecircumference,having|0 and|1 atoppositeextremes.OnewaytoseethisistoconsiderthelocusofpointsintheBlochsphereforwhicheiθ=1,orinotherwords,thosewithnocircularpolarisation.Unfortunately,thereisnosuchnicegeometricrepresentationofanarbitraryn-qubitstate,andwebelievethesameistrueforn-rebitstates.

Thecomputationalbasisvectorsforarebitarestill|0 and|1 ,andforarbitraryn-rebitsystemstheycanalsoberepresentedasn-bitstrings.Themeasurementruleinde ningtheprobabilitiesofobtainingthecorrespondingbitstringasaresultisessentiallythesameasEquation1,

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

(7)

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

Quaternionic Computing

problemswhicharee cientlysolvedbyaquantumalgorithmalsobesolvedbyane cientrealalgorithm?

FortheQuantumTuringMachinemodel,theanswerwaspreviouslyknowntobe“Yes”.Eventhough,itisnotexplicitlystatedassuch,thefollowingtheoremistraditionallyattributedtoBernsteinandVazirani,asitcanbeeasilydeducedfromtheresultsin[7].

Theorem1(Bernstein,Vazirani).AnyQuantumTuringMachinecanbeapproximatedsu cientlywellbyanother,whosetransitionmatrixonlycontainscomputablerealnumbersoftheform±cos(kR)andsin(kR),wherekisanintegerand

R=∞ i=11/22.i

Theneedforhavingsuchtranscendentalamplitudeswaseventuallyremoved.Byusingtran-scendentalnumbertheorytechniques,Adleman,Demarrais,andHuangshowedin[1],that,infact,onlyafewrationalamplitudeswererequired,inparticularonlytheset{0,±1,±3/5,±4/5}.ItisimportanttonotethatTheorem1doesnotapplydirectlytocircuits,oratleastnotinacompletelytrivialmanner.TheconstructionsintheproofarerelativelyelaborateandrelyheavilyontechniquesofTuringMachineengineering.Nonetheless,quantumcircuitswereshowntobeequivalenttoQuantumTuringMachinesbyA.C.-C.Yaoin[21].Inprinciple,theconstructionofthatproofcouldbeusedtoshowthatquantumcircuitsdonotrequirestateswithcomplexamplitudestoachievethesamepowerasanycomplex-valuedcircuitorQTM.However,thecelebrateduniversalityresultofBarenco,Bennett,Cleve,DiVicenzo,Margolus,Shor,Sleator,Smolin,andWeinfurter[4]providesa rststeptowardsaproofofthatfact,astheyshowthatCNOTandarbitrary1-qubitgatesformauniversalsetofgatesforquantumcircuits.Whilearbitrary1-qubitgatescancontaincomplexamplitudetransitions,morerecentresultshaveproducedeversmallersetsofuniversalgates,whicharecomprisedonlyofrealamplitudetransitions.Thefollowingisjustasamplelistofsuchresults:

TOFFOLI,HADAMARD,andπ/4-rotation,byKitaev[14]in1997.

CNOT,HADAMARD,π/8-rotationbyBoykin,Mor,Pulver,Roychowdhury,andVatan[8]in2000.

TOFFOLIandHADAMARD,byShi[19]in2002,withasimplerproofbyAharonov[3]in2003. Controlledθ-rotations,byRudolphandGrover[18]in2002

Themotivationbehindtheseresultswastocomeupwiththesimplestpossiblegates,giventhefactthatquantumstatesinnaturecanandwillhavearbitrarycomplexamplitudes,andthus,sowilltheirunitarypropagators.Thefactthatthesimplersetsinvolveonlyrealnumberswasapriorijusta“desirableside-e ect.”Ourmotivation,however,iscompletelydi erent.Weplayadi erentgame:supposethatallwehadwerethesemysterious“rebits,”unabletoentercomplexamplitudes.Whatcouldwedothen?Becauseofthismotivation,ourproofwillhaveadi erent avour.Infact,theproofiscompletelygeneralinthatitworkswithanyuniversal

Quaternionic Computing

setofgates.Inparticular,itwillworkwithgateswhichhavearbitrarycomplextransitionamplitudes.Inotherwords,inprovingthefollowing,moregeneraltheorem,wewillcompletelyignoretheaboveresults.ThatwillallowustorecycleitsprooflateroninSection4.

Theorem2.Anyn-qubitquantumcircuitconstructedwithgatesofdegreedorless(possiblyincludingnon-standardcomplexcoe cientsgates)canbeexactlysimulatedwithann+1rebitcircuitwiththesamenumberofgatesofdegreeatmostd+1.

3.3

3.3.1ANewProofofEquivalenceTheUnderlyingGroupTheory

TheideabehindtheproofistomakeuseofthefactthatthegroupSU(N)canbeembeddedintothegroupSO(2N).Weprovideanexplicitembeddingh.4Whilethismappingisnotunique,whatisspecialaboutitisthatithasallthenecessarypropertiesforustode neasoundsimulationalgorithmbasedonit.Thismappingisde nedasfollows.GivenanarbitraryunitarytransformationU,itsimageO=h(U)is

Re(U)hU→O=h(U) Im(U)

Independently,Aharonov[3]hasalsousedthismappingrecentlytoprovideasimpleproofthatTOFFOLIandHADAMARDareuniversal.4

Quaternionic Computing

Proof.The rststepistoobtainasimplematrixmultiplicationruleformatrices,usingtheoperatorsReandIm.Forarbitrarycomplexnumbersαandβ,wehavethat

Re(αβ)=Re(α)Re(β) Im(α)Im(β)

Im(αβ)=Re(α)Im(β)+Im(α)Re(β)(11)

Sincetheserulesholdfortheproductsofalloftheirentries,itistheneasytoseethatthissamemultiplicationrulewillalsoholdforcomplexmatrices.Inotherwords,wecansubstituteαandβinEquation11withanytwoarbitrarycomplexmatricesAandBwhicharemultipliable,toget

Re(AB)=Re(A)Re(B) Im(A)Im(B)

Im(AB)=Re(A)Im(B)+Im(A)Re(B)

Wearenowequippedtoverifyourclaim

h(A)h(B)=(T A)(T B) Re(A)Im(B)= Im(A)Re(B) Re(A)Re(B) Im(A)Im(B)= Im(A)Re(B) Re(A)Im(B) Im(AB)

Re(AB)

=T AB=h(AB)(13)(12)

Finally,wewanttoshowthatGN SO(2N).ThisisequivalenttoshowingthatalltheimagesO=h(U)areorthonormal,i.e.thatOt=O 1.SincebyLemma1hisagrouphomomorphism,itmapsinverseelementsintoinverseelements,i.e.h(U 1)=h(U) 1.SinceUisunitary,wehavethat

O 1=h(U) 1=h(U 1)=h(U )(14)

whilethefollowinglemmawillgiveusanexpressionforOt.

Lemma2.LetAbeanarbitraryN×Ncomplexmatrix,thenh(A )=h(A)t.

Proof.Byde nitionofhandbytranspositionrulesofblockmatrices,wehave

h(A)t=(T A)t

Re(A)= Im(A)

Im(A)t

Re(A)t

=Re(A )

Im(A )

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.

Quaternionic Computing

3.3.3InonthegatesdenoteUgN-aryofthetheInnotj1,...,1≤jwhereiandgate.thisandAsforlevelsonOg=

Quaternionic Computing

extrad+1dofHCWeuseNoteh1aretensorTheintegervectorsTheseOgtostate|in

Quaternionic Computing

theweC.thedAtnasWeC′.O(gfor

Quaternionic Computing

U (g)

O(g )Og

S 2, j

1

S 3, k

1

S 3, k

1

S 2, j

1

Og j Ug j+1 Og I k+1 Og

k

Ug

Figure 4: Obtaining an expression for the (N+ 1)-ary circuit O (g) .O (1) O ( 2) O ( 3) O ( 4)

O1 U2 U3 U4 U1 U3 O1 O3 O2 O3 O4

Figure 5: Simulation of a quantum circuit by a real circuit. What is remarkable about this scheme, is that despite its simplicity, it gives precisely what we wanted, this is, that the nal operator OC be in some sense as similar as possible to the operator UC of the original circuit. In fact, we have the following third nice property of our simulation. Lemma 3. The inverse image of OC is precisely UC, i.e. OC= h(UC ). Proof. Because of the serialisation of Step 1, we have that UC= U (s) . . . U (2) U (1) . We use this and the group isomorphism properties of h from Lemma 1 to obtain the following expression for its image h(UC )= h(U (s) . . . U (1) )= h(U (s) ) . . . h(U (1) )s 1

=i= 0, g=s i

h(U (g) )

Quaternionic Computing

WecannowusetheexpressionofEquation17tosubstituteforU(g),

=h(Sg(Ug In 2)Sg) =h(Sg)h(Ug In 2)h(Sg)

SinceSgiscomposedonlyof0’sand1’s,wehavethatRe(Sg)=SgandIm(Sg)=0.Fur-

′thermore,wehavethatSg=I1 Sgfromtheirde nitioninEquations(17)and(22),and

thus,

=(I1 Sg)h(Ug In 2)(I1 Sg) ′′=Sgh(Ug In 2)Sg

However,thetensorproductisjustaformaloperation,anditsassociativitypropertyholdsevenwithatensorofoperatorslikeT.Hence,wehave

′′=Sg[T (Ug In 2)]Sg ′′=Sg[(T Ug) In 2]Sg ′′=Sg[h(Ug) In 2]Sg ′′=Sg(Og In 2)Sg

whichwiththepaddingexpressionofO(g)inEquation22 nallygives

=s 1 O(g)=OC.(23)

i=0,g=s i

3.3.4CircuitInitialisationandMeasurement

HavingdescribedhowtoconstructtherealcircuitC′fromtheoriginalcircuitC,westillhavetoaddresstheissueofhowtoinitialiseC′inStep4,andfurthermoreofhowtointerpretanduseitsmeasurementstosimulatetheinitialquantumalgorithminStep5.

Let|Ψ representtheinitialstategiventoC,andlet|Φ beitsimageunderUC,i.e.the nalstateofthecircuitbeforemeasurement.Ifwethinkbackofthetwohomomorphismsh0and

NNh1fromHCtoHC,inducedbyh,wehavetwologicalchoicesforinitialisingthecorrespondingrealcircuitOC,thestates|Ψ0 and|Ψ1 .Whichshouldwechoose,andineithercasewhatwilltheoutputlooklike?Theanswertothelatterquestionisgivenbythefollowinglemma.Lemma4.Theimagesof|Ψ0 and|Ψ1 intherealcircuitC′are

OC|Ψ0 =T0 |Φ =|Φ0 OC|Ψ1 =T1 |Φ =|Φ1

(24)(25)

Quaternionic Computing

Proof.AsintheproofofLemma1,allwerequirearethematrixmultiplicationrulesofEqua-tion12

OC|Ψ0 =(T UC)(T0 |Ψ0 ) Re(UC)= Im(UC)Im(|Ψ0 ) Re(UC)Re(|Ψ0 )+Im(UC)Im(|Ψ0 )=

=T0 (UC|Ψ0 )=T0 |Φ =|Φ0 Im(UC|Ψ0 )(26)

Withthesamemethod,wecanobtainasimilarexpressionforΦ1,i.e.

OC|Ψ1 =(T UC)(T1 |Ψ1 ) Re(UC)= Im(UC)

=T1 |Φ =|Φ1 Re(|Ψ1 )=...

(27)

Letusassumeforamoment—andinfact,thisiswithoutlossofgenerality—thattheoriginalcircuitwastobeinitialisedwithsomebasevector|x ,witha nalstate|Φ =U|x .Again,therearetwopossiblechoicesforinitialisingthecorrespondingrealcircuit,namely|x0 =|0 |x and|x1 =|1 |x .Whatwouldthenbetheoutputofthesimulatedcircuitineithercase?Intheveryspecialcasethat|Φ isalsoabasevector,thenwewouldhave|Φ0 =|0 |Φ and|Φ1 =|1 |Φ ,andthus,ineithercase,thebottomn-wireswouldcontaintherightanswerandwecanignorethetopwire.Butwhen|Φ issomearbitrarypurestate,neitherpurelyrealnorpurelyimaginary,wecannotgivesuchanicesemantictothetopwire.Inparticular,itmightbeentangledwiththerestofthewires,andhencewecannotfactorthe nalstate.

Nonetheless,whatissurprisingisthatifwetraceoutthetopwire,inallcaseswewillgetthesamestatisticsandfurthermorethatwewillobtaintherightstatistics,i.e.thesameasifwehadusedtheoriginalquantumcircuitC.Moreformally,wehave

Lemma5.Let|Φ beanarbitraryn-qubitpurestate,andletρ0=Tr1|Φ0 Φ0|andρ1=Tr1|Φ1 Φ1|representthepartialtracesobtainedbytracingout(i.e.forgettingabout)thetopwire.Thenwehavethat

ρ0=ρ1,

Diag(ρ0)=Diag(ρ1)=Diag(|Φ Φ|).(28)(29)

Proof.Thepartialtraceofthe rstwireofanarbitrarydensityoperatorgiveninblockmatrixform Aρ=C

Quaternionic Computing

isgivenby,

Tr1(ρ)=[In|0]ρ[In|0] +[0|In]ρ[0|In]

=A+D

Inparticular,wehavethat

|Φ0 Φ0|=(T0 |Φ )(T0 |Φ )t

whichbyapplyingtranspositionrulesforblockmatricesandEquation12gives

=

= Re(|Φ )Re(|Φ )Re( Φ|)

Im(|Φ )Re( Φ|)Im( Φ|) (30)

Im(|Φ )Re( Φ|)

Re(|Φ )Re( Φ|) (32)

Bysymmetry,wethushavethesameexpressionforbothpartialtraces

ρ0=ρ1=Re(|Φ )Re( Φ|) Im(|Φ )Im( Φ|)

=Re(|Φ Φ|)(33)

Since|Φ Φ|ishermitian,itsdiagonalentriesareallreal,andthereforeithasthesamediagonalentriesasρ0andρ1.

Inotherwords,combiningthiswithLemma4,wearrivetotheconclusionthatitdoesnotmatterwhatwesetastheinitialvalueofthetopwire,|0 or|1 .Furthermore,itiseasytoverifythatany1-rebitstatewilldo,whetherpureoreventotallymixed,aslongasitisunentangledanduncorrelatedwiththebottomwires.

3.4

3.4.1FurtherConsiderationsandConsequencesComplexityofsimulation

Ingeneral,ifweinitiallyhavead-qubitgate,thenewgatewillbea(d+1)-rebitgate.However,ifUgcontainsonlyrealentries,thenOg=I Ug,whichmeansthatinthisparticularcasethetoprebitneednotbeinvolved,andthereforethenewgateisthesameastheoriginal.Ifthewholequantumcircuitwearegivenisconstructedwithsuchrealgates,thenweareinluckandwedonotrequiretheextrarebitatall.Inthegeneralcomplexcase,however,thecircuitwidthisatmostonemorethanthatoftheoriginalcircuit.

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.

Quaternionic Computing

Inotherwords,itsomehowkeepstrackofthephase(angle)oftherepresentationof|Φ inrebitspacewithrespecttothesesubspaces.TheCNOTgate(oranyotherrealgate)doesnotchangethisphasefactor.However,asarbitrarygateswithcomplextransitionamplitudesa ectthisphasefactor,theire ectissimulatedby“recording”thischangeinthetoprebit.Howweinitialisethetoprebitgivesanarbitraryinitialphasetotherepresentationof|Φ ,butaswesaw,thisinitialphasedoesnota ectstatisticsofthebottomwires,andthuscanbesettoanyvalue.However,howthisphasehasbeenchangedbypreviouscomplexgateswilla ectthebottomrebitsinsubsequentcomplexgates,inasimilarfashionasthephasekickbackphenomenoninmanyquantumalgorithms7.Thatiswhythattoprebitisneeded.

4QuaternionicComputing

ThissectioncloselymimicsSection3.Firstwede newhatwemeanbyquaternioniccomputing,makingsurethatitisasensiblemodel.Wethenproveanequivalencetheoremwithquantumcomputing,byusingthesametechniquesasthoseofTheorem2.

4.1

4.1.1De nitionsQuaternions

QuaternionswereinventedbytheIrishmathematicianWilliamRowanHamiltonin1843,asageneralisationofcomplexnumbers.Theyformanon-commutative,associativedivisionalgebra.Aquaternionisde nedas

α =a0+a1i+a2j+a3k(34)

wherethecoe cientsaarerealnumbersandi,j,andkobeytheequations

ii=jj=kk=ijk= 1(35)

Multiplicationofquaternionsisde nedbyformallymultiplyingtwoexpressionsfromEqua-tion34,andrecombiningthecrosstermsbyusingEquation35.Itisveryimportanttonotethatwhileallnon-zeroquaternionshavemultiplicativeinversestheyarenotcommutative8.Thus,theyformwhatiscalledadivisionalgebra,sometimesalsocalledaskew eld.Thequaternionconjugationoperationisde nedasfollows:

α =a0 a1i a2j a3k(36)

whereforclarity,werepresentwiththe(non-standard)symbol( )inordertodistinguishitfromcomplexconjugationrepresentedwith( ).Withthisconjugationrule,wecande nethemodulusofaquaternionas

|α |=√222a20+a1+a2+a3(37)

Quaternionic Computing

Furthermore,theusualvectorinnerproducthastherequiredproperties(i.e.itisnormde ning),andaproperHilbertspacecanbede nedonanyquaternioniclinearspace.

Itisalsopossibletocomplexifythequaternions,thisis,torepresentthemintermsofcomplexnumbersonly.Letα beanarbitraryquaternion,thenwede neitscomplexandweirdpartsas

Co( α) a0+a1i

Wd( α) a2+a3i.

Wecanthendecomposeα initscomplexandweirdpartasfollows:

α =a0+a1i+a2j+a3k

=(a0+a1i)+(a2+a3i)j

=Co( α)+Wd( α)j

Thisequationallowsustoderivemultiplicationrules,similartothoseofEquation11

)=Co( ) Wd( )Co( αβα)Co(βα)Wd (β

)=Co( )+Wd( )Wd( αβα)Wd(βα)Co (β(41)(38)(39)(40)

wherewede neCo ( α) [Co( α)] ,andsimilarlyfortheweirdpartWd ( α) [Wd( α)] .Itisinterestingtonotehowthenon-commutativityofquaternionsismadeapparentbythefactthat ,unliketheirequivalentfor andβneitheridentityinEquation41issymmetricwithrespecttoα

complexnumbers(Equation11),becauseingeneralCo ( α)=Co( α)andWd ( α)=Wd( α).WecanalsorewriteEquation37forthemodulusas

|α |=

|2|α |2+|β

uptoanarbitraryquaternionicphasefactor.Indeed,wehavethat

Φ≡Φ′ |Φ =η |Φ′ ,where|η |=1.(44)(45)

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.

本文来源：https://www.bwwdw.com/article/isx4.html