Introduction

Information as accessed by the human mind, and the myriad ways of process-

ing it, is what has set humankind apart in the animal world. The ability to use

the physical systems around us to encode and then to process information has

been evolving in leaps and bounds ever since the dawn of our race! The earliest

form of computation was probably in the form of account-keeping by counting

pebbles or on the fingers. This developed into the abacus, writing symbols,

the computing machine, and now, a laptop or a supercomputer: everywhere

we represent information by means of a physical system, and perform ma-

nipulations on that system to process the information in many desired ways,

including communication. The stress here is on the realization that the basis

of information is a physical system. The more advanced that system is and

the set of rules it functions on, the more capable our means of information

processing and communication. When the underlying physical system used for

encoding and processing information is a quantum system, we have quantum

information processing.

While technological advances have made it possible to reach astounding

speeds and processing power, the basic paradigm of current day information

processing is binary logic with currents or voltages in the semiconductor cir-

cuitry at the heart of the modern computer processors. However, it is impor-

tant to realize that the behavior of these high and low states of the circuit

is based on laws of classical physics. We know now that at the most funda-

mental level, physical systems obey the laws of quantum mechanics. These

laws are fundamentally different in many ways from classical laws of physics.

Therefore, the basic paradigm of information processing is different when we

come to quantum information processing. Not only are the algorithms and

the processing mechanism different, but there are distinct advantages of the

quantum over the classical.

According to recent data, the fastest current day supercomputer is capable

of performing at a speed of hundreds of Gflop/s.

1

The quantum paradigm

affords a speedup to many algorithms that are very slow to perform even on

this computer! Much of modern-day information security, for instance secure

online cash transactions, is based on classical cryptography. This has been

proved to be vulnerable if a quantum computer is used to crack the code!

I’ve been trying to motivate the need to study quantum information. But

1

Gigaflop per second, Giga = 10

12

, FLOP = floating point operation.

3

4 Introduction to Quantum Physics and Information Processing

the inquisitive scientific mind will no doubt want to grasp the basics of the

physical laws that make complex information processing possible: the laws of

quantum mechanics. Professor Richard Feynman of Caltech was supposed to

have famously said that no one understands quantum mechanics! How then are

we basing modern technology on it? With this book I’d like to show you that

despite its “weirdness”, by which I mean its distance from our common sense

understanding which appears wired to classical physics, the laws of quantum

mechanics can be apprehended by an undergraduate student, to be used as a

set of rules by which the game is played. The more philosophically inclined will

be drawn to ponder meaning and interpretation of these rules. And this latter

exercise is also rewarding, in bringing out fascinating new facets of quantum

theory, to be exploited in our ever-expanding game of information processing.

Several considerations make the transition to the quantum inevitable while

exploring efficient information processing. One is from the perspective of hard-

ware engineering, where miniaturization and the need to pack more structure

in less space must eventually lead to the limit set by the structure of matter:

the atomic or even electronic level. At this level, classical laws of physics are

no longer valid and we have to consider the essentially quantum nature of the

physical system used to store and manipulate information.

However, from the angle of the basic physical laws of quantum mechanics,

more complex ways of processing information should be possible. The manner

in which a quantum system evolves, transforms information and conveys it

in an experiment via a measurement, is fundamentally different from classi-

cal information. This was realized first by Feynman [33] in the 1980s when

he pointed out that a quantum process cannot be efficiently simulated on a

classical computer. He showed, however, that such a system may be efficiently

simulated on a quantum computer.

In the process of studying how this is possible, we are led into a deeper

probing of the foundations of quantum physics. In implementing a quantum

computer, physicists need to access and control individual quantum states,

prepare them, manipulate them and finally, measure them. The question also

arises of how to deal with practical systems that are not ideal and isolated from

their environments, but are subject to noise or errors due to inadvertent en-

vironmental effects. These considerations lead us into an experimental regime

of testing our ideas of quantum reality, and into discovering new quantum

phenomena.

The third perspective is from the theory of computation. The foundations

of modern computer science may be said to have been laid by the work of Alan

Turing in the 1930s [69], on abstract models of computing embodied in what

is now known as the Turing Machine. The Universal Turing Machine (UTM)

is an idealization of a model of computation that can execute any computable

algorithm, in short, any task that can be run on a modern programmable

computer. Notions of computability of problems and efficiency of algorithms

were developed. In rough terms, an algorithm is said to be efficient if it takes

polynomial time for execution. This means that the time required to run it

Introduction 5

grows as a polynomial in the number n of input bits, i.e., at most as a power

of n. A computationally hard problem is one for which the best algorithm is

exponential in the number of input bits, i.e., grows as a

n

where a is some

constant.

As Feynman pointed out, the evolution of a quantum system is one prime

example of a problem that cannot be simulated efficiently on a Turing machine,

while a quantum computer could quite naturally do so! This was a challenge

to the Church–Turing thesis that any computation can be efficiently simulated

on a Turing Machine. This thesis had been modified to include probabilistic

machines (based on fuzzy logic) but now has been extended to a quantum

version.

Problems in computational complexity have now been extended to include

the quantum Turing machine and the possibilities are exciting. While the

basic notion of computability of a given problem does not change when quan-

tum machines are included, problems that were hard classically may become

easy. Quantum computation may also resolve other questions in the area of

computational complexity.

FIGURE 1.1: Three approaches to the quantum.

These three approaches (Figure (1.1) have historically motivated the study

of this field, which at present however, is rapidly blooming in several different

directions unforeseen in the last century.

6 Introduction to Quantum Physics and Information Processing

1.1 Bits and Qubits

So what is the fundamental difference between classical and quantum com-

puting?

Computation and information processing as we know it today is built upon

Boolean logic and algebra. Boolean algebra is binary, requiring two logical

units called bits. You can think of them as the possible answers to a decision

question: yes or no. The idea is that almost any problem can be reformulated

as a series of decision questions, and therefore can be encoded in bits. A

bit, or binary digit, is a physical system that can take on two logical states

represented by 0 and 1. In a typical digital computer these states are the low

and high voltage states in the microcircuitry.

To extend the capabilities of the computational system, probabilistic al-

gorithms are based on the notion of fuzzy bits, that can take the value 0 with

a probability p or 1 with probability 1 − p. This is the basis of probabilistic

computation, or so-called fuzzy logic.

When the logic is extended to binary states of a quantum system, we ar-

rive at the qubit, a quantum bit. A qubit can take values 0 or 1 but with

probabilities given by the mod-squared of complex numbers! A physical qubit

is a quantum system that will represent our Boolean units. The system can

therefore take on two quantum states that we will now represent in the nota-

tion |0i and |1i, to distinguish them from the states 0 and 1 of the classical

bit. This angular bracket notation is due to physicist Paul Dirac [29]. This

notation is very versatile and by itself a useful calculational tool.

A qubit is generically represented as a linear superposition of the basis

states:

|ψi = α|0i + β|1i. (1.1)

The coefficients α and β are called probability amplitudes, and satisfy such

that |α|

2

+ |β|

2

= 1.

The way to understand this statement is that upon measurement, the

generic qubit takes on one of the definite states |0i or |1i with a probability |α|

2

or |β|

2

. In this sense, a qubit is similar to a classical bit in that measurement

only gives one of two values. It is sometimes useful to think of these values,

or the basis states of the qubit, as classical bits.

Though the qubit is probabilistic, it differs from the fuzzy bit because

of the possibility of interference. This is characteristic that is captured by

the complex amplitudes. A complex number has a magnitude and well as a

phase. While composing two or more such numbers, the phases could result

in reinforcement or reduction in the strength of the resultant. The physical

implications of this is familiar to us through the phenomenon of interference

in optics. When two beams of light, described by electric fields having defi-

nite phase relationships to each other, are combined, then there are regions