ABSTRACT
Historic developments in information technology have had an unprecedented impact on society. The past few decades have witnessed an explosion of computing capacity consistent with Moore’s law, which asserts that processor power doubles every 18 months. This trend has been accompanied by a commensurate increase in processor
density, one that cannot continue unchecked without dramatic changes to the basic circuit elements of modern processors. Indeed, existing circuit elements are reaching the quantum limit, the size scale where quantum phenomena begin to dominate the physics governing their behavior. While this prediction itself motivates the study of “quantum” information and computation, discoveries of the last decade have revealed that quantum phenomena can be exploited to yield a qualitatively new computational paradigm, one that offers provable speedup over its classical counterpart for a wide variety of computational problems. Indeed, efficient quantum algorithms have been designed for problems believed to be intractable for classical computation, like integer factorization or large database search [1,2].
