% References

% \bib, bibdiv, biblist are defined by the amsrefs package.
\begin{bibdiv}
\begin{biblist}

\bib{Ajtai:97}{inproceedings}{
      author={Ajtai, M.},
      author={Dwork, C.},
       title={A public-key cryptosystem with worst-case/average-case
  equivalence},
        date={1997},
   booktitle={{Proceedings of the 29th Annual ACM Symposium on Theory of
  Computing}},
       pages={284\ndash 293},
}

\bib{Beals:97a}{inproceedings}{
      author={Beals, R.},
       title={Quantum computation of {F}ourier transforms over symmetric
  groups},
        date={1997},
   booktitle={{Proceedings of the 29th Annual ACM Symposium on Theory of
  Computing}},
   publisher={ACM Press},
     address={New York},
       pages={48\ndash 53},
}

\bib{Bernstein:97a}{article}{
      author={Bernstein, E.},
      author={Vazirani, U.},
       title={Quantum complexity theory},
        date={1997},
     journal={SIAM Journal on Computing},
      volume={26},
      number={5},
       pages={1411\ndash 1473},
}

\bib{Boneh:95a}{inproceedings}{
      author={Boneh, R.},
      author={Lipton, R.},
       title={Quantum cryptoanalysis of hidden linear functions},
        date={1995},
   booktitle={{Advances in Cryptology -- Crypto'95}},
      series={{Lecture Notes in Computer Science}},
      volume={963},
   publisher={Springer-Verlag},
     address={Berlin},
       pages={424\ndash 437},
}

\bib{Brickell:83}{inproceedings}{
      author={Brickell, E.~F.},
       title={Solving low density knapsacks},
        date={1984},
   booktitle={{Advances in Cryptology -- Crypto'83}},
   publisher={Plenum Press},
     address={New York},
       pages={25\ndash 37},
}

\bib{CFG:89}{article}{
      author={Chaimovich, M.},
      author={Freiman, G.},
      author={Galil, Z.},
       title={Solving dense subset-sum problems by using analytical number
  theory},
        date={1989},
     journal={Journal of Complexity},
      volume={5},
      number={3},
       pages={271\ndash 282},
}

\bib{Coster:92}{article}{
      author={Coster, M.~J.},
      author={Joux, A.},
      author={LaMacchia, B.~A.},
      author={Odlyzko, A.~M.},
      author={Schnorr, C.-P.},
      author={Stern, J.},
       title={Improved low-density subset sum algorithms},
        date={1992},
     journal={Computational Complexity},
      volume={2},
      number={2},
       pages={111\ndash 128},
}

\bib{Deutsch:92a}{article}{
      author={Deutsch, D.},
      author={Jozsa, R.},
       title={Rapid solution of problems by quantum computation},
        date={1992},
     journal={Proceedings of the Royal Society of London A},
      volume={439},
       pages={553\ndash 558},
}

\bib{Deutsch:85a}{article}{
      author={Deutsch, D.},
       title={Quantum theory, the {C}hurch-{T}uring principle and the universal
  quantum computer},
        date={1985},
     journal={Proceedings of the Royal Society of London A},
      volume={400},
       pages={97\ndash 117},
}

\bib{Eldar:03a}{article}{
      author={Eldar, Y.~C.},
      author={Megretski, A.},
      author={Verghese, G.~C.},
       title={Designing optimal quantum detectors via semidefinite
  programming},
        date={2003},
     journal={IEEE Transactions on Information Theory},
      volume={49},
      number={4},
       pages={1007\ndash 1012},
}

\bib{Eldar:02}{article}{
      author={Eldar, Y.~C.},
      author={Megretski, A.},
      author={Verghese, G.~C.},
       title={Optimal detection of symmetric mixed quantum states},
        date={2004},
     journal={IEEE Transactions on Information Theory},
      volume={50},
      number={6},
       pages={1198\ndash 1207},
}

\bib{Ettinger:99b}{techreport}{
      author={Ettinger, M.},
      author={H{\o}yer, P.},
       title={A quantum observable for the graph isomorphism problem},
        note={arXiv:quant-ph/9901029},
}

\bib{Ettinger:99a}{techreport}{
      author={Ettinger, M.},
      author={H{\o}yer, P.},
      author={Knill, E.},
       title={Hidden subgroup states are almost orthogonal},
        note={arXiv:quant-ph/9901034},
}

\bib{Ettinger:04a}{article}{
      author={Ettinger, M.},
      author={H{\o}yer, P.},
      author={Knill, E.},
       title={The quantum query complexity of the hidden subgroup problem is
  polynomial},
        date={2004},
     journal={Information Processing Letters},
      volume={91},
      number={1},
       pages={43\ndash 48},
}

\bib{Ettinger:00a}{article}{
      author={Ettinger, M.},
      author={H{\o}yer, P.},
       title={On quantum algorithms for noncommutative hidden subgroups},
        date={2000},
     journal={Advances in Applied Mathematics},
      volume={25},
      number={3},
       pages={239\ndash 251},
}

\bib{FP:05}{inproceedings}{
      author={Flaxman, A.},
      author={Przydatek, B.},
       title={Solving medium-density subset sum problems in expected polynomial time},
        date={2005},
   booktitle={{Proceedings of the 22nd Annual Symposium on Theoretical Aspects
  of Computer Science}},
   publisher={Springer-Verlag},
       pages={305\ndash 314},
}

\bib{Friedl:03a}{inproceedings}{
      author={Friedl, K.},
      author={Ivanyos, G.},
      author={Magniez, F.},
      author={Santha, M.},
      author={Sen, P.},
       title={Hidden translation and orbit coset in quantum computing},
        date={2003},
   booktitle={{Proceedings of the 35th Annual ACM Symposium on Theory of
  Computing}},
   publisher={ACM Press},
     address={New York},
       pages={1\ndash 9},
}

\bib{Frieze:86}{article}{
      author={Frieze, A.},
       title={On the {L}agarias-{O}dlyzko algorithm for the subset sum
  problem},
        date={1986},
     journal={SIAM Journal on Computing},
      volume={15},
      number={2},
       pages={536\ndash 539},
}

\bib{GM:91}{article}{
      author={Galil, Z.},
      author={Margalit, O.},
       title={An almost linear-time algorithm for the dense subset-sum
  problem},
        date={1991},
     journal={SIAM Journal on Computing},
      volume={20},
      number={6},
       pages={1157\ndash 1189},
}

\bib{Gavinsky:04a}{article}{
      author={Gavinsky, D.},
       title={Quantum solution to the hidden subgroup problem for
  {P}oly-{N}ear-{H}amiltonian groups},
        date={2004},
     journal={{Quantum Information and Computation}},
      volume={4},
      number={3},
       pages={229\ndash 235},
}

\bib{Grigni:04a}{article}{
      author={Grigni, M.},
      author={Schulman, L.},
      author={Vazirani, M.},
      author={Vazirani, U.},
       title={Quantum mechanical algorithms for the nonabelian hidden subgroup
  problem},
        date={2004},
     journal={Combinatorica},
      volume={24},
      number={1},
       pages={137\ndash 154},
}

\bib{Hales:99a}{inproceedings}{
      author={Hales, L.},
      author={Hallgren, S.},
       title={Quantum {F}ourier sampling simplified},
        date={1999},
   booktitle={{Proceedings of the 31st Annual ACM Symposium on Theory of
  Computing}},
   publisher={ACM Press},
     address={New York},
       pages={330\ndash 338},
}

\bib{Hales:00a}{inproceedings}{
      author={Hales, L.},
      author={Hallgren, S.},
       title={An improved quantum {F}ourier transform algorithm and
  applications},
        date={2000},
   booktitle={{Proceedings of the 41st Annual Symposium on Foundations of
  Computer Science}},
   publisher={IEEE},
     address={Los Alamitos, CA},
       pages={515\ndash 525},
}

\bib{Hallgren:03}{article}{
      author={Hallgren, S.},
      author={Russell, A.},
      author={Ta-Shma, A.},
       title={The hidden subgroup problem and quantum computation using group representations},
        date={2003},
   journal={SIAM Journal on Computing},
     volume={32}, 
    number={4},  
     pages={916\ndash 934}
}

\bib{HW:94}{article}{
      author={Hausladen, P.},
      author={Wootters, W.~K.},
       title={A `pretty good' measurement for distinguishing quantum states},
        date={1994},
     journal={Journal of Modern Optics},
      volume={41},
      number={12},
       pages={2385\ndash 2390},
}

\bib{Hel76}{book}{
      author={Helstrom, C.~W.},
       title={Quantum Detection and Estimation Theory},
   publisher={Academic Press},
     address={New York},
        date={1976},
}

\bib{Hol78}{article}{
      author={Kholevo (Holevo), A.~S.},
       title={On asymptotically optimal hypothesis testing in quantum
  statistics},
        date={1979},
     journal={Theory of Probability and its Applications},
      volume={23},
      number={2},
       pages={411\ndash 415},
        note={English translation of Teoriya Veroyatnoste{\u{\dotlessi}}
              i ee Primeneniya {\bf 23} (1978), no. 2, 429--432},
}

\bib{Holevo:73b}{article}{
      author={Holevo, A.~S.},
       title={Statistical decisions in quantum theory},
        date={1973},
     journal={Journal of Multivariate Analysis},
      volume={3},
      number={4},
       pages={337\ndash 394},
}

\bib{Hoyer:97a}{techreport}{
      author={H{\o}yer, P.},
       title={Efficient quantum transforms},
        note={arXiv:quant-ph/9702028},
}

\bib{Hoyer:99a}{article}{
      author={H{\o}yer, P.},
       title={Conjugated operators in quantum algorithms},
        date={1999},
     journal={Physical Review A},
      volume={59},
      number={5},
       pages={3280\ndash 3289},
}

\bib{IG:04}{techreport}{
      author={Inui, Y.},
      author={{Le Gall}, F.},
       title={An efficient algorithm for the hidden subgroup problem over a
  class of semi-direct product groups},
        note={arXiv:quant-ph/0412033},
}

\bib{Ip:03a}{unpublished}{
      author={Ip, L.},
       title={Shor's algorithm is optimal},
        date={2003},
}

\bib{Ivanyos:03a}{article}{
      author={Ivanyos, G.},
      author={Magniez, F.},
      author={Santha, M.},
       title={Efficient quantum algorithms for some instances of the
  non-abelian hidden subgroup problem},
        date={2003},
     journal={International Journal of Foundations of Computer Science},
      volume={14},
      number={5},
       pages={723\ndash 739},
}

\bib{Kempe:04a}{inproceedings}{
      author={Kempe, J.},
      author={Shalev, A.},
       title={The hidden subgroup problem and permutation group theory},
        date={2005},
   booktitle={{Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms}},
   publisher={SIAM},
     address={Philadelphia},
       pages={1118\ndash 1125},
}

\bib{Kitaev:95a}{techreport}{
      author={Kitaev, A.},
       title={Quantum measurements and the abelian stabilizer problem},
        note={arXiv:quant-ph/9511026},
}

\bib{KNP:05}{inproceedings}{
 author = {Koiran, P.},
 author = {Nesme, V.}, 
 author = {Porties, N.},
 title = {A quantum lower bound for the query complexity of {S}imon's problem}, 
 date = {2005}, 
   booktitle={{Proceedings of the 32nd International Colloquium on Automata, 
 Languages and Programming}},
      series={{Lecture Notes in Computer Science}},
      volume={3580},
   publisher={Springer}, 
    address = {Berlin},
       pages={1287\ndash 1298}
}

\bib{Kuperberg:05}{article}{
      author={Kuperberg, G.},
       title={A subexponential-time quantum algorithm for the dihedral hidden
  subgroup problem},
   date = {2005},
 journal = {SIAM Journal on Computing},
  volume = {35},
  number = {1},
   pages = {170\ndash 188}
}

\bib{LO:85}{article}{
      author={Lagarias, J.~C.},
      author={Odlyzko, A.~M.},
       title={Solving low-density subset sum problems},
        date={1985},
     journal={Journal of the ACM},
      volume={32},
      number={1},
       pages={229\ndash 246},
}

\bib{Moore:04a}{inproceedings}{
      author={Moore, C.},
      author={Rockmore, D.~N.},
      author={Russell, A.},
      author={Schulman, L.~J.},
       title={The power of basis selection in {F}ourier sampling: Hidden
  subgroup problems in affine groups},
        date={2004},
   booktitle={{Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete
  Algorithms}},
   publisher={SIAM},
     address={Philadelphia},
       pages={1113\ndash 1122},
}

\bib{Moore:05b}{techreport}{
      author={Moore, C.},
      author={Russell, A.},
       title={The symmetric group defies strong {F}ourier sampling: Part~{II}},
        note={arXiv:quant-ph/0501066},
}

\bib{Moore:05a}{inproceedings}{
      author={Moore, C.},
      author={Russell, A.},
      author={Schulman, L.~J.},
       title={The symmetric group defies strong {F}ourier sampling},
        date={2005},
   booktitle={{Proceedings of the 46th Annual Symposium on Foundations of Computer Science}},
     publisher={IEEE},
   address={Los Alamitos, CA},
    pages={479\ndash 490},
}

\bib{NielsenChuang}{book}{
      author={Nielsen, M.~A.},
      author={Chuang, I.~C.},
       title={Quantum computation and quantum information},
   publisher={Cambridge University Press},
     address={Cambridge},
        date={2000},
}

\bib{Peres}{book}{ % See Chapter 9.6, p. 285 for Neumark's theorem 
 author = {Peres, A.}, 
 title = {Quantum theory: concepts and methods},
 publisher = {Kluwer Academic Publishers}, 
 series = {Fundamental theories in physics}, 
 volume = {72}, 
 date = {1993} 
}

\bib{Regev:04a}{techreport}{
      author={Regev, O.},
       title={A subexponential time algorithm for the dihedral hidden subgroup
  problem with polynomial space},
        note={arXiv:quant-ph/0406151},
}

\bib{Regev:04b}{article}{
    author = {Regev, O.},
     title = {Quantum computation and lattice problems},
   journal = {SIAM Journal on Computing},
    volume = {33},
      date = {2004},
    number = {3},
     pages = {738\ndash 760},
}

\bib{Regev:04c}{article}{
    author = {Regev, O.},
    title = {New lattice based cryptographic constructions},
    journal = {Journal of the ACM},
    volume = {51},
    number = {6},
    pages = {899\ndash 942},
    year = {2004}
}

\bib{Roetteler:98a}{techreport}{
      author={R{\"o}tteler, M.},
      author={Beth, T.},
       title={Polynomial-time solution to the hidden subgroup problem for a
  class of non-abelian groups},
        note={arXiv:quant-ph/9812070},
}

\bib{Serre:77a}{book}{
      author={Serre, J.},
       title={Linear representations of finite groups},
      series={Graduate Texts in Mathematics},
      volume={42},
   publisher={Springer},
     address={New York},
        date={1977},
}

\bib{Shor:97}{article}{
      author={Shor, P.~W.},
       title={Polynomial-time algorithms for prime factorization and discrete
  logarithms on a quantum computer},
        date={1997},
     journal={SIAM Journal on Computing},
      volume={26},
      number={5},
       pages={1484\ndash 1509},
}

\bib{Simon:97}{article}{
      author={Simon, D.~R.},
       title={On the power of quantum computation},
        date={1997},
     journal={SIAM Journal on Computing},
      volume={26},
      number={5},
       pages={1474\ndash 1483},
}

\bib{Sloane:04}{techreport}{
      author={Sloane, N. J.~A.},
       title={The on-line encyclopedia of integer sequences},
        date={2004},
        note={\url{http://www.research.att.com/~njas/sequences}},
}

\bib{Yuen:75}{article}{
      author={Yuen, H.},
      author={Kennedy, R.},
      author={Lax, M.},
       title={Optimum testing of multiple hypotheses in quantum detection
  theory},
        date={1975},
     journal={IEEE Transactions on Information Theory},
      volume={21},
      number={2},
       pages={125\ndash 134},
}

\end{biblist}
\end{bibdiv}