The Study of Entangled States in Quantum Computati

arXiv:0808.1546v1[quant-ph]11Aug2008TheStudyofEntangledStatesinQuantumComputationandQuantumInformationSciencebyHyeyounChungSubmittedtotheDepartmentofElectricalEngineeringandComputerScienceinpartialfulfillmentoftherequirementsforthedegreeofMasterofEngineeringinElectricalEngineeringandComputerScienceattheMASSACHUSETTSINSTITUTEOFTECHNOLOGYJune2008'HyeyounChung,MMVIII.Allrightsreserved.TheauthorherebygrantstoMITpermissiontoreproduceanddistributepubliclypaperandelectroniccopiesofthisthesisdocumentinwholeorinpart.Author..............................................................DepartmentofElectricalEngineeringandComputerScienceMay20,2008Certifiedby..........................................................IsaacL.ChuangAssociateProfessorThesisSupervisorAcceptedby.........................................................ArthurC.SmithChairman,DepartmentCommitteeonGraduateTheses2TheStudyofEntangledStatesinQuantumComputationandQuantumInformationSciencebyHyeyounChungSubmittedtotheDepartmentofElectricalEngineeringandComputerScienceonMay20,2008,inpartialfulfillmentoftherequirementsforthedegreeofMasterofEngineeringinElectricalEngineeringandComputerScienceAbstractThisthesisexplorestheuseofentangledstatesinquantumcomputationandquan-tuminformationscience.Entanglement,aquantumphenomenonwithnoclassicalcounterpart,hasbeenidentifiedasanimportantandquantifiableresourceinmanyareasoftheoreticalquantuminformationscience,includingquantumerrorcorrection,quantumcryptography,andquantumalgorithms.Wefirstinvestigatetheequivalenceclassesofaparticularclassofentangledstates(knownasgraphstatesduetotheirassociationwithmathematicalgraphs)underlocaloperations.Weprovethatforgraphstatescorrespondingtographswithneithercyclesoflength3nor4,theequivalenceclassescanbecharacterizedinaverysimpleway.Wealsopresentsoftwareforanalyzingandmanipulatinggraphstates.Wethenstudyquantumerror-correctingcodeswhosecodewordsarehighlyentan-gledstates.AnimportantareaofinvestigationconcerningQECCsistodeterminewhichresourcesarenecessaryinordertocarryoutanycomputationonthecodetoanarbitrarydegreeofaccuracy,whilesimultaneouslymaintainingahighdegreeofresistancetonoise.Weprovethattransversalgates,whicharedesignedtopre-ventthepropagationoferrorsthroughasystem,areinsufficienttoachieveuniversalcomputationonalmostallQECCs.Finally,westudytheproblemofcreatingefficientquantumcircuitsforcreat-ingentanglingmeasurements.Entanglingmeasurementscanbeusedtoharnesstheapparentextracomputingpowerofquantumsystemsbyallowingustoextractinfor-mationabouttheglobal,collectivepropertiesofaquantumstateusinglocalmeasure-ments.Weconstructexplicitquantumcircuitsthatcreateentanglingmeasurements,andshowthatthesecircuitsscalepolynomiallyintheinputparameters.ThesisSupervisor:IsaacL.ChuangTitle:AssociateProfessor34AcknowledgmentsIwouldliketothankProfessorIsaacChuangforacceptingmeintohisresearchgroup,andforgivingmetheopportunitytocarryoutmyMEngthesisprojectunderhissupervision.Iamgratefulforhiseffortstohelpmebecomeabetterscientist,byteachingmehowtoapproachresearchquestions,andremindingmetothinkaboutthemotivationbehindeveryproblem,andtheconsequencesoffindingasolution.IwouldalsoliketothankProfessorChuangforhelpingtoimprovemycommunicationskills,intheday-to-dayenvironmentoftheresearchgroupaswellasingivingpresentationsandwritingpapers.IwouldalsoliketothankallthemembersoftheQuantagroupfortheirinsights,conversations,andjokesduringourweeklygroupmeetingsandotherget-togethers,andforansweringmyquestionsabouttheirresearchandmyown.IamalsogratefultoDaveBaconforpatientlyansweringmyquestionsabouthispapers,bothinpersonandviae-mail.Finally,Iwouldliketothankmyparentsfortheirunfailinglove,encouragement,andsupport.56Contents1Introduction171.1History...................................181.2Entanglementasaresourceinquantumcomputationandquantuminformation................................191.2.1Entanglement:FundamentalConcepts.............191.2.2EntangledStatesinQuantumAlgorithms...........201.2.3ComputingOnEntangledStates................211.2.4ClassifyingEntangledStates...................221.3OverviewofThesis............................231.3.1StructureoftheThesis......................252BackgroundInformation272.1Basicsofquantumcomputation.....................272.1.1Qubits...............................272.1.2Modelsofquantumcomputing:quantumcircuits.......282.1.3Quantumgates..........................292.2Basicsofquantumerrorcorrection...................322.2.1Simplequantumerrorcorrectingcodes.............322.2.2Generaltheoryoferrorcorrectingcodes............372.2.3StabilizercodesandtheStabilizerformalism..........382.2.4Stabilizerstates..........................392.2.5StabilizersandCliffordoperations................393LocalUnitaryvs.LocalCliffordEquivalenceofStabilizerStates413.1BackgroundInformation.........................413.1.1StabilizerStates..........................413.1.2Graphstates...........................423.2Motivation:Classifyingstabilizerstates.................433.3TheProblem...............................443.4MinimalSupportsandtheMinima