Daniel Simons 1994 upptäckt av en effektiv kvantalgoritm för att lösa det dolda subgruppsproblemet (HSP) över Z n 2 gav ett av de första algebraiska problemen för vilka kvantdatorer är exponentiellt snabbare än sina klassiska motsvarigheter. I detta dokument studerar vi generaliseringen av Simons problem till godtyckliga grupper. Fastställande av en ändlig grupp G, Detta är problemet med att återvinna en involutionm = (m 1,. .., m n ) G n från en orakel f med den egenskap som f (x) = f (x · på)  på... I nuvarande parlans, detta är den dolda subgrupp problem (HSP) över grupper av formen G n, där G är en icke-abelian grupp av konstant storlek, och där den dolda subgruppen är antingen trivialt eller har ordning två. Även grupper av formen G n har en enkel produktstruktur, de delar viktiga representationteoretiska egenskaper med de symmetriska grupperna S n, där en lösning på HSP skulle ge en kvantalgoritm för Graph Isomorphism. I synnerhet kräver lösningen av deras HSP med den så kallade "standardmetoden" mycket insnärjda mätningar på tensorprodukten från många coset-stater. Här ger vi kvantalgoritmer med tids komplexitet 2 O( ε n log n) som återvinner dolda involutioner m = (m 1,. ., m n ) G n där, som i Simons problem, varje m i är antingen identiteten eller konjugatet av ett känt element m och det finns ett tecken χ för G som χ(m) = −χ(1). Vår strategi kombinerar den allmänna idén bakom Kuperbergs sikt för dihedralgrupper med Moores och Russells "missande harmoniska" tillvägagångssätt. Dessa är de första icke-triviala dolda subgruppsalgoritmer för gruppfamiljer som kräver mycket insnärjd *
En av dem är att begrunda Simons problem över allmänna grupper, för vilka Ref. REF föreslog en effektiv kvantalgoritm med tids komplexitet 2 O ( ε n log n).
Quantum algorithms for Simon's problem over general groups
{'venue': "SODA '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}