An introduction to quantum computing for non-physicists

Richard Feynman's observation that certain quantum mechanical effects canno t be simulated efficiently on a computer led to speculation that computatio n in general could be done more efficiently if it used these quantum effect s. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring integers. In quantum systems, the computational space increases exponentially with th e size of the system, which enables exponential parallelism. This paralleli sm could lead to exponentially faster quantum algorithms than possible clas sically. The catch is that accessing the results, which requires measuremen t, proves tricky and requires new nontraditional programming techniques. The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce b asic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantu m cryptography, teleportation, and dense coding. Various approaches to expl oiting the power of quantum parallelism are explained. We conclude with a d iscussion of quantum error correction.