Many have heralded quantum computing as the next great technology to take us beyond the limits of Moore's law. But exactly what can these new machines accomplish? We will survey the computer science view on quantum computers - assuming that physicists can solve the technological challenges and build large-scale quantum computers, what problems can these computers solve quicker than our usual machines? We also describe the author's own research in the area, including his view of quantum computing as fitting into the standard computing hierarchy, the limitations of these machines and some results on property testing in the quantum model.
