Quantum random walks - an introductory overview

Quantumrandomwalks:anintroductoryoverviewJ.KEMPEThisarticleaimstoprovideanintroductorysurveyonquantumrandomwalks.Startingfromaphysicaleffecttoillustratethemainideaswewillintroducequantumrandomwalks,reviewsomeoftheirpropertiesandoutlinetheirstrikingdifferencestoclassicalwalks.Wewilltouchuponbothphysicaleffectsandcomputerscienceapplications,introducingsomeofthemainconceptsandlanguageofpresentdayquantuminformationscienceinthiscontext.Wewillmentionrecentdevelopmentsinthisnewareaandoutlinesomeopenquestions.Goddoesnotplaydice.AlbertEinstein1.OverviewEversincethediscoveryofquantummechanicspeoplehavebeenpuzzledbythecounter-intuitivecharacterofthelawsofnature.OvertimewehavelearnedtoacceptmoreandmoreeffectsthatareunimaginableinaclassicalNewtonianworld.Moderntechnologyexploitsquantumeffectsbothtoourbenefitanddetriment—amongthememorableexam-plesweshouldcitelasertechnologyandnotomittheatomicbomb.Inrecentyearsinterestinquantuminformationtheoryhasbeengeneratedbytheprospectofemployingitslawstodesigndevicesofsurprisingpower[1].Newideasincludequantumcryptography[2,3]andquantumcomputation.In1994Shor[4]discoveredaquantumalgorithmtofactornumbersefficiently(thatisintimethatgrowsonlypolynomicallywiththelengthofthenumbertobefactored).Thishasunleashedawaveofactivityacrossabroadrangeofdisciplines:physics,computerscience,mathematicsandengineering.Thisfruitfulaxisofresearchhasuncoveredmanyneweffectsthatarestrikinglydifferentfromtheirclassicalcounterparts,bothfromthephysicalpointofviewaswellasfromacomputerscienceandcommunicationtheoryperspective.Overtimethesecommunitieshavegainedagreaterunderstandingoftheconceptsandnotionsoftheother.Theideathatinformationcannotbeseparatedfromthephysicaldevicethatiscarryingit(‘informationisphysical’)hasfirmlysettledamongthemandhasledtofascinatingnewinsights.Acquaintancewiththebasicnotionsofeachofthesefieldsseemsinstrumentalintheunderstandingofmodernquantuminformationprocessing.Inthisarticlewewillfollowthetrajectoryofoneofthemanysurprisingaspectsofquantuminformation;itisdedicatedtoquantumrandomwalks.Wewillgiveathoroughintroductiontothenecessaryterminologywith-outoverburdeningthereaderwithunnecessarymathe-matics.Startingwithaveryintuitiveandphysicalexamplewewillstepbystepintroducethelanguageandnotationofpresentdayquantuminformationscience.Wewillpresentthenecessarybackgroundfromcomputerscienceneededforaphysicisttounderstandandappreciatethedevelop-mentsandresults,assumingsomerudimentarybackgroundofquantummechanics,butnoknowledgeofcomputerscienceorquantuminformationtheory.Anexcellentcomprehensiveintroductiontoquantuminformationandcomputationcanbefoundin[1].Inthisjourneyattheinterfaceofseveraltraditionaldisciplineswewillfollowquantumrandomwalksboththroughphysicsandcomputerscience.Thistourthroughquantuminformationsciencewillallowustosurveysomeofitsmostpertinentconceptsandideastoday,likequantumalgorithms,quantumcomputingmachines,speed-ups,physicalimplementation,quantumcircuitsanddecoherence.Itwillbeourmissiontoshowhowphysicalphenomenatranslateintonewcomputersciencealgorithmsandviceversa.TheideaisthatareaderfamiliarwiththestandardidiomofquantummechanicsbutunaccustomedAuthor’saddress:CNRS-LRI,UMR8623,Universite´deParis-Sud,91405Orsay,France,andComputerScienceDivisionandDepartmentofChemistry,UniversityofCalifornia,Berkeley,USA.ContemporaryPhysics,volume44,number4,July–August2003,pages307–327ContemporaryPhysicsISSN0010-7514print/ISSN1366-5812online#2003Taylor&FrancisLtd:10.1080/00107151031000110776tothelanguageof‘qubits’and‘gates’willlearnaboutquantuminformationsciencewhilelearningaboutquan-tumrandomwalksandtheirfascinatingbehaviour.Wewillsurveysomerecentdevelopmentsandresultsomittingmostproofsbuttryingtodevelopanintuition.Thisarticleaimstobringtheinterestedreadertoapointwhereheorshecanreadandunderstandcurrentresearcharticlesonthetopicanddevelopanunderstandingfortheinterestingproblemsandopenquestionsinthearea.Thestructureofthisarticleisasfollows:firstwegivesomephysicalintuitionforrandomwalks,providingageneralflavourofthephenomenoninaphysicalsetting(section2).Thisisfollowedbyamorerigorousdefinitiontogetherwithsomenecessaryterminologytointroducethetwomainmodelsofquantumrandomwalksinsection3.Wethenpresentsomecomputerscienceandprobabilitybackgroundandmentionsomeoftheimportantalgorith-micresultsstemmingfromquantumrandomwalksinsection4.Section5switchesbacktophysicsandstudieshowtheserandomwalkscouldbeimplementedinsomerealphysicalsystem.Finallywedealwiththemorephilosophicalquestionofhowtheclassicalworldemergesfromquantumbehaviourviadecoherenceusingrandomwalksasourexample(section6).Allalongthewaywewilloutlineopenquestionsandfuturedirections.2.AgentleintroductionToillustratequantumrandomwalksandgiveanintuitionforwhatfollowswestartwithanexample.Thisexample—whichmightbethoughtofasaprecursortolatermodels—istakenfromtheworkofthreephysicistsin1993,Y.Aharonov,L.DavidovichandN.Zagury[5].Theirworkforthefirsttimecoinstheterm‘quantumrandomwalk’.Imagineaparticleonalinewhosepositionisdescribedbyawave-packetjcx0ilocaliz