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