Diamant

Hidden subgroup minicourse

October 30-November 3 2006, CWI Amsterdam

Gábor Ivanyos,

MTA SZTAKI & TU/e

• Introduction/motivation

• Weak version of Shor's order finding and discrete log
• slides: pdf

• Groups

• Introduction to the structure of groups we encounter
• slides: pdf

• Representation theory

• Introduction to the representation theory of finite groups
• slides: pdf

• Abelian Fourier sampling

• for the HSP of abelian groups
• generalizing the HSP modell
• application: HSP in groups with small center
• an attempt to reducing to HSP of normal subgroups and factor groups: function value superposition and hidden shifts
• [Ivanyos, Magniez, Santha: http://arxiv.org/abs/quant-ph/0102014]
• slides: pdf
  

• Abelian hidden shifts

• Dihedral HSP
• [Ettinger, Hoyer: http://arxiv.org/abs/quant-ph/9807029]
• Hidden shift in Z_p^n
• [Friedl, Ivanyos, Magniez, Santha, Sen: http://arxiv.org/abs/quant-ph/0211091]
• slides: pdf

• HSP and hidden shifts in  "smooth" groups

• via permutation problems: stabilizer and orbit membership
• [Friedl, Ivanyos, Magniez, Santha, Sen: http://arxiv.org/abs/quant-ph/0211091]
• slides: pdf
  

• Noncommutative Fourier sampling

• The query complexity of the HSP
• [Ettinger, Hoyer, Knill, http://arxiv.org/abs/quant-ph/0401083]
  
• The noncommutative Fourier transform of coset states and hidden subgroup states
• Partly [Hallgren, Rotteler, Sen: http://arxiv.org/abs/quant-ph/0511148]
• and [Moore, Rockmore,Russell: http://arxiv.org/abs/quant-ph/0304064]
• Weak Fourier Sampling, Normal HSP
• [Hallgren, Russell, Ta-Shma: http://doi.acm.org/10.1145/335305.335392]
• [Grigni, Schulman, Vazirani, Vazirani: http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/s00493-004-0009-8]
• Strong Fourier Sampling
  
• [Moore, Russell: http://arxiv.org/abs/quant-ph/0504067]
• Kuperberg's multiregister technique for the dihedral group
  
• [Kuperberg: http://arxiv.org/abs/quant-ph/0302112]
  
• only if time, no slides
  
• Missing harmonic
• [Moore, Russell: http://arxiv.org/abs/quant-ph/0504067]
• only if time, no slides
  
• slides pdf

• Pretty good measurement

• POVM and PGM introduction
• [Bacon, Childs, van Dam: http://arxiv.org/abs/quant-ph/0501044]
• PGM for the HSP Heisenberg group
• [Bacon, Childs, van Dam: http://arxiv.org/abs/quant-ph/0504083]
• slides pdf

• HSP in extraspecial groups

• A "twisted" mutliregiaster technique
  
• [Ivanyos, Sanselme, Santha,  manuscipt]
• slides pdf

• Limitations of the techniques - only if time

• A short survey and/or something from:
• limitations of single-register approaches [
• Kempe, Shalev: http://arxiv.org/abs/quant-ph/0406046], 
• [Moore, Russell, Schulman: http://arxiv.org/abs/quant-ph/0501056, http://arxiv.org/abs/quant-ph/0501066]
• lower bounds on the number of entangled coset states 
• [Hallgren, Rotteler, Sen: http://arxiv.org/abs/quant-ph/0511148] 
• [Childs-Wocjan: http://arxiv.org/abs/quant-ph/0510185]
  
• [Moore, Russell: http://arxiv.org/abs/quant-ph/0511149]
• relation to lattice problems and cryptogaphy
• [Regev: http://arxiv.org/abs/quant-ph/0406151, http://arxiv.org/abs/cs.DS/0304005]
• No slides