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