8.1. Introduction

So far, we studied algorithms in the area of cryptology, that can be implemented on classical computers (Turing machines or von Neumann’s stored-program computers). Now, we shift our attention to a different paradigm of computation, known as quantum computation. The working of a quantum computer is specified by the laws of quantum mechanics, a branch of physics developed in the 20^th century. However counterintuitive, contrived or artificial these laws initially sound, they have been accepted by the physics community as robust models of certain natural phenomena. A bit, modelled as a quantum mechanical system, appears to be a more powerful unit than a classical bit to build a computing device.

This enhanced power of a computing device has many important ramifications in cryptology. On one hand, we have polynomial-time quantum algorithms to solve the integer factorization and the discrete-log problems. This implies that most of the cryptographic algorithms that we discussed earlier become (provably) insecure. On the other hand, there are proposals for a quantum key-exchange method that possesses unconditional (and provable) security.

Unfortunately, it is not clear how one can manufacture a quantum computer. Technological difficulties involved in the process appear enormous and a section of the crowd even questions the feasibility of building such a machine. However, no laws or proofs rule out the possibility of success in the (near or distant) future. Myth has it that Thomas Alva Edison, after several hundred futile attempts to manufacture an electric light bulb, asserted that he knew hundreds of ways how one cannot make an electric bulb. Edison succeeded eventually and dream turned into reality.

But we will not build quantum computers in this chapter. That is well beyond the scope of this book, or, for that matter, of computer science in general. It is thoroughly unimportant to understand the I-V curves of a transistor (or even to know what a transistor actually is), when one designs and analyses (classical) algorithms. In order to design and analyse quantum algorithms, it is equally unimportant to know how a quantum computer can be realized.