language: en

Quantum Computing | A treatise

Prabhat Kumar
October 24, 1996

Abstract Quantum computing has witnessed a surge of activity recently owing to some very exciting discoveries on both the theoretical and practical fronts. In this overview, we sketch an account of the developments in this scientifically intriguing field, starting in the early 80's when the first questions about the computability of quantum processes were raised, and which led to the formal definitions of a Quantum Computer and a Quantum Complexity Theory. Peter Shor's recent remarkable discovery of quantum algorithms to solve the problems of integer factoring and discrete log computing, which are believed to be extremely hard to solve efficiently on classical computers, is a compelling demonstration of the suspected superiority of quantum computing over the classical model that is in use today. We discuss one of his algorithms and the implications it has for classical cryptography. We discuss some of the latest work in this field which has brought us yet closer to achieving a physical realization of a quantum computer. Whenever it happens, if it happens, it would be yet another revolution in the field of computing, and maybe the biggest one to date.

1 Birth of Quantum Computing