The hidden subgroup problem and quantum computatio

THEHIDDENSUBGROUPPROBLEMANDQUANTUMCOMPUTATIONUSINGGROUPREPRESENTATIONS∗SEANHALLGREN†,ALEXANDERRUSSELL‡,ANDAMNONTA-SHMA§SIAMJ.COMPUT.c2003SocietyforIndustrialandAppliedMathematicsVol.32,No.4,pp.916–934Abstract.Thehiddensubgroupproblemisthefoundationofmanyquantumalgorithms.Anefficientsolutionisknownfortheproblemoverabeliangroups,employedbybothSimon’salgorithmandShor’sfactoringanddiscretelogalgorithms.Thenonabeliancase,however,remainsopen;anefficientsolutionwouldgiverisetoanefficientquantumalgorithmforgraphisomorphism.Wefullyanalyzeanaturalgeneralizationofthealgorithmfortheabeliancasetothenonabeliancaseandshowthatthealgorithmdeterminesthenormalcoreofahiddensubgroup:inparticular,normalsubgroupscanbedetermined.Weshow,however,thatthisimmediategeneralizationoftheabelianalgorithmdoesnotefficientlysolvegraphisomorphism.Keywords.quantumcomputation,quantumalgorithms,computationalcomplexity,represen-tationtheory,finitegroupsAMSsubjectclassifications.81P68,68Q17DOI.10.1137/S009753970139450X1.Introduction.PeterShor’sseminalarticle[27]presentedefficientquantumalgorithmsforcomputingintegerfactorizationsanddiscretelogarithms,problemsthoughttobeintractableforclassicalcomputationmodels.Aprimaryingredientinthesealgorithmsisanefficientsolutiontothehiddensubgroupproblemforcertainabeliangroups;indeedcomputingdiscretelogarithmsdirectlyreducestothehiddensubgroupproblem.Formally,thehiddensubgroupproblemisthefollowing.Definition1.1.Hiddensubgroupproblem(HSP).Givenanefficientlycom-putablefunctionf:G→S,fromafinitegroupGtoasetS,thatisconstanton(left)cosetsofsomesubgroupHandtakesdistinctvaluesondistinctcosets,determinethesubgroupH.Thegeneralparadigm,whichgivesrisetoefficientquantumalgorithmsforthisproblemoverabeliangroups,isthefollowing.Experiment1.1(experimentfortheabelianHSP).1.Preparethestate1
|G|g∈G|g,f(g)andmeasurethesecondregisterf(g).Asftakesdistinctvaluesontheleftcosetsof∗ReceivedbytheeditorsAugust28,2001;acceptedforpublication(inrevisedform)December16,2002;publishedelectronicallyJune10,2003.ApreliminaryversionofthisarticleappearedinProceedingsofthe32ndAnnualACMSymposiumonTheoryofComputing,Portland,OR,2000,pp.627–635.ThebulkofthisresearchwascompletedwhiletheauthorswereattheUniversityofCalifornia,Berkeley.†ComputerScienceDepartment,Caltech,MC256-80,Pasadena,CA91125([e-mail]).ThisauthorwassupportedinpartbyanNSFMathematicalSciencesPostdoctoralFellowship,anNDSEGfellowship,aGAANNfellowship,andNSFgrantCCR-9800024.‡DepartmentofComputerScienceandEngineering,UniversityofConnecticut,Storrs,CT06269([e-mail]).ThisauthorwassupportedbyNSFCAREERawardCCR-0093065,NSFgrantCCR-0220264,NSFgrantEIA-0218443,NSFNYIgrantCCR-9457799,andaDavidandLucilePackardFellowshipforScience.§ComputerScienceDivision,Tel-AvivUniversity,Israel69978([e-mail]).916THEHIDDENSUBGROUPPROBLEM917H,theresultingstateis1
|H|h∈H|ch,f(ch),(1.1)wherecisanelementofGselecteduniformlyatrandom.2.ComputetheFouriertransformofthe“coset”state(1.1),resultinginρ∈ˆG1|G|1|H|h∈Hρ(ch)|ρ,whereˆGdenotesthesetofhomomorphisms{ρ:G→C}.3.Measurethefirstregisterandobserveahomomorphismρ.Akeyfactaboutthisprocedureisthattheresultingdistributionoverρisinde-pendentofthecosetcHarisingafterthefirststage(asthesupportofthefirstregisterin(1.1)).Thus,repetitionsofthisexperimentresultinthesamedistributionoverˆG.Wenotethatbytheprincipleofdelayedmeasurement(see,e.g.,[21]),measuringthesecondregisterinthefirststepcaninfactbedelayeduntiltheendoftheexperiment.ItiswellknownthatanefficientsolutiontotheHSPforthesymmetricgroupSngives,inparticular,anefficientquantumalgorithmforgraphisomorphism.ItisalsoknownhowtoefficientlycomputetheFouriertransformovermanynonabeliangroups,mostnotablyoverSn[2].ThisarticleprovidesthefirstgeneralunderstandingoftheHSPovernonabeliangroups:WestudyanaturalgeneralizationofExperiment1.1tononabeliangroupsandexplicitlydescribetheresultingmeasurementdistribution.Specifically,westudythefollowingexperiment.Experiment1.2.1.Preparethestateg∈G|g,f(g)andmeasurethesecondregisterf(g).Theresultingstateish∈H|ch,f(ch),wherecisanelementofGselecteduniformlyatrandom.Asabove,thisstateissupportedonaleftcosetcHofH.2.LetˆGdenotethesetofirreduciblerepresentationsofGand,foreachρ∈ˆG,fixabasisforthespaceonwhichρacts.Letdρdenotethedimensionofρ.ComputetheFouriertransformofthe“coset”state,resultinginρ∈ˆGdρidρjdρ|G|1|H|h∈Hρ(ch)i,j|ρ,i,j.3.Measurethefirstregisterandobservearepresentationρ.AbriefdiscussionoftherepresentationtheoryoffinitegroupsandtheassociatedFouriertransformappearsinsection2.Asbefore,wewishtheresultingdistributiontobeindependentoftheactualcosetcH(andsodependonlyonthesubgroupH).Thisisguaranteedbymeasuringonlythenameoftherepresentationρandleavingthematrixindices(thevaluesiandj)unobserved.ThequestionwestudyiswhetherthisprocedureretainsenoughinformationtodetermineHor,moreprecisely,whetherO(log(|G|))samplesofthisdistributionareenoughtodetermineHwithhighprob-ability.OuranalysisofExperiment1.2dependsonthefollowingtheorem,whichdescribesthedistributi