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