



01122nas a2200145   4500008004100000245004600041210004600087260001400133300001100147490000700158520073400165100002300899700001700922856003700939       2010                        eng d00aQuantum algorithms for algebraic problems0 aQuantum algorithms for algebraic problems  c2010/1/15  a1 - 520 v823 a  Quantum computers can execute algorithms that dramatically outperform
classical computation. As the best-known example, Shor discovered an efficient
quantum algorithm for factoring integers, whereas factoring appears to be
difficult for classical computers. Understanding what other computational
problems can be solved significantly faster using quantum algorithms is one of
the major challenges in the theory of quantum computation, and such algorithms
motivate the formidable task of building a large-scale quantum computer. This
article reviews the current state of quantum algorithms, focusing on algorithms
with superpolynomial speedup over classical computation, and in particular, on
problems with an algebraic flavor.
1 aChilds, Andrew, M.1 avan Dam, Wim  uhttp://arxiv.org/abs/0812.0380v1