A

SEMINAR REPORT
(course code no)
On

Quantum-Computing
SUBMITTED IN THE PARTIAL FULFILLMENT OF THE
REQUIREMENT FOR THE DEGREE OF
Master of Technology
In

Computer Science and Engineering

Proposed By

Pavana Chakradhar Jada

Enrollment No: 2312051074

Under the guidance of

Supervisor Co-Supervisor
Dr. Payal Ms. Meenakshi Gupta
Assistant Professor Assistant Professor

Department of Computer Science & Engineering

DPG Institute of Technology & Management
Gurugram, Haryana
 Index

Sl No Description Page No
Abstract 1
01 Introduction 2
02 History 3
03 Quantum Mechanics 4
04 Elements of Quantum Computing 6
05 Quantum Computers 11
06 Projected Benefits Of Quantum Computing 15
07 Projected Problems Of Quantum Computing 16
08 Availability of Quantum Computers 17
09 Conclusion 18
10 References 19
 1

ABSTRACT

A quantum computer is a computation device that makes direct use of quantum

mechanical phenomena, such as the superposition and entanglement of atoms,
photons, electrons etc., to perform operations on data. Quantum computers are
different from digital computers based on transistors [1]. Whereas digital
computers require data to be encoded into binary digits (bits), quantum
computation uses quantum properties to represent data and
perform operations on these data. A theoretical model is the quantum Turing
machine, also known as the universal quantum computer. Quantum computers
shared theoretical similarities with non-deterministic and probabilistic
computers [1, 5, and 8]. It has the potential to perform calculations, billions of
time faster than any silicon based computer.
 2

1. INTRODUCTION

Civilization has advanced as people discovered new ways of exploiting various

physical resources such as materials, forces and energies. In the twentieth century
information was added to the list when the invention of computers allowed
complex information processing to be performed outside human brains. The
history of computer technology has involved a sequence of changes from one
type of physical realization to another --- from gears to relays to valves to
transistors to integrated circuits and so on.

Today’s computers are classical, a fact which is actually not entirely obvious. A
basis of modern computers rests on semiconductor technology. Transistors,
which are the “neurons” of all computers, work by exploiting properties of
semiconductors. Classical computers are in a certain, restricted, sense quantum
mechanical, because, as far as we understand today, everything is quantum
mechanical. No, classical computers, although based on quantum physics, are not
fully quantum, because they do not use “quantumness” of matter at the
information-theoretical level, where it really matters.

Gordon Moore proposed Moore’s law in 1965, which originally stated that
processor power and speed would double in size every eighteen months (this was
later revised to two years). This law still holds but is starting to falter, and
components are getting smaller. Soon they will be so small, being made up of a
few atoms that quantum effects will become unavoidable, possibly ending
Moore’s law. There are ways in which we can use quantum effects to our
advantage in a classical sense, but by fully utilizing those effects we can achieve
much more. This approach is the basis for quantum computing.
 3

2. HISTORY

The fled of quantum computation is largely a body of theoretical promises for

some impressively fast algorithms which could be executed on quantum
computers. However, since the first significant algorithm was proposed in 1994
experimental progress has been rapid with several schemes yielding two and
three quantum-bit manipulations [2].
Quantum computers were first discussed by Paul Benioff in the context of
simulating classical Turing machines (very elementary conventional computers)
with quantum unitary evolution [4]. Feynman considered the converse question
of how well classical computers can simulate quantum systems [3]. He concluded
that classical computers invariably super from an exponential slow-down in
trying to simulate quantum systems, but that quantum systems could, in principle,
simulate each other without this slowdown. It was Deutsch, however, who first
suggested that quantum superposition might allow quantum evolution to perform
many classical computations in parallel [5, 6].
 4

3. QUANTUM MECHANICS

The Quantum mechanics is generally about the novel behaviour of very small
things. At this scale matter becomes quantized, this means that it can’t be
subdivided no more. Quantum mechanics has never been wrong, it explains why
the stars shine, how matter is structured, the periodic table, and countless other
phenomena [10].

The following are main parts of quantum mechanics that are important for
quantum computing:

• Superposition and interference

• Uncertainty
• Entanglement
• Linear algebra
• Dirac notation
• Representing information

3.1 Superposition
Superposition means a system can be in two or more of its states
simultaneously. For example a single particle can be traveling along two
different paths at once. This implies that the particle has wave-like properties,
which can mean that the waves from the different paths can interfere with each
other. Interference can cause the particle to act in ways that are impossible to
explain without these wave-like properties. The ability for the particle to be in a
superposition is where we get the parallel nature of quantum computing: If
each of the states corresponds to a different value then, if we have a
superposition of such states and act on the system, we effectively act on all the
states simultaneously.

3.2 Uncertainty
The quantum world is irreducibly small so it’s impossible to measure a
quantum system without having an effect on that system as our measurement
device is also quantum mechanical. As a result there is no way of
accurately predicting all of the properties of a particle. There is a trade off - the
properties occur in complementary pairs (like position and momentum, or
vertical spin and horizontal spin) and if we know one property with a high
degree of certainty then we must know almost nothing about the other property.
That unknown property’s behavior is essentially random. An example of this is
a particle’s position and velocity: if we know exactly where it is then we know
nothing about how fast it is going. This indeterminacy is exploited in quantum
cryptography. It has been postulated (and currently accepted) that particles in
fact DO NOT have defined values for unknown properties until they are
measured. This is like saying that something does not exist until it is looked at.

3.3 Entanglement
In 1935 Einstein (along with colleagues Podolski and Rosen) demonstrated a
paradox (named EPR after them) in an attempt to refute the undefined nature of
 5

quantum systems. The results of their experiment seemed to show that quantum
systems were defined, having local state BEFORE measurement. Although the
original hypothesis was later proven wrong (i.e. it was proven that quantum
systems do not have local state before measurement). The effect they
demonstrated was still important, and later became known as entanglement.
Entanglement is the ability for pairs of particles to interact over any distance
instantaneously. Particles don’t exactly communicate, but there is a statistical
correlation between results of measurements on each particle that is hard to
understand using classical physics. To become entangled, two particles are
allowed to interact; they then separate and, on measuring say, the velocity of one
of them (regardless of the distance between them), we can be sure of the value
of velocity of the other one (before it is measured). The reason we say that they
communicate instantaneously is because they store no local state and only have
well defined state once they are measured. Because of this limitation particles
can’t be used to transmit classical messages faster than the speed of light as we
only know the states upon measurement. Entanglement has applications in a wide
variety of quantum algorithms and machinery.

3.4 Linear Algebra

Quantum mechanics leans heavily on linear algebra. Some of the concepts of
quantum mechanics come from the mathematical formalism, not thought
experiments, that’s what can give rise to counter intuitive conclusions.

3.5 Dirac Notation

Dirac notation is used for quantum computing. We can represent the states of a
quantum system as kets. For example, an electron’s spin can be represented as
|0> spin up and |1> as spin down. The electron can be thought of as a little
magnet, the effect of a charged particle spinning on its axis. When we pass a
horizontally traveling electron through an inhomogeneous magnetic field, in
say, the vertical direction, the electron either goes up or down. If we then repeat
this with the up electron it goes up, with the down electron it goes down. We
say the up electron after the first measurement is in the state |0> and the down
electron is in state |1>. But, if we take the up electron and pass it through a
horizontal field it comes out on one side 50% of the time and on the other side
50% of the time. If we represent these two states as | + > and | - > we can say
that the up spin electron was in a superposition of the two states |+> and | - > :
such that, when we make a measurement with the field horizontal we project
the electron into one or the other of the two states, with equal probabilities 1/2

3.6 Representing Information

Quantum mechanical information can be physically realized in many ways. To
have something analogous to a classical bit we need a quantum mechanical
System with two states only, when measured. Methods for representing binary
information in a way that is capable of exhibiting quantum effects (e.g.
entanglement and superposition) are: electron spin, photon direction,
polarization of photons and nuclear spins.
 6

4. ELEMENTS OF QUANTUM COMPUTING

The basic element of quantum computing includes the qubits, the quantum gates,
quantum circuits and quantum algorithms [12].

4.1 The Qubit

The qubit is the quantum analogue of the bit, the classical fundamental unit of
information [20]. It is a mathematical object with specific properties that can be
realized physically in many different ways as an actual physical system. Just as
the classical bit has a state (either 0 or 1), a qubit also has a state. Yet contrary
to the classical bit, 0 and 1 are but two possible states of the qubit, and any
linear combination (superposition) thereof is also physically possible. In
general, thus, the physical state of a qubit is the superposition.

ψ = α0 + β1 (Where α and β are complex numbers).

The state of a qubit can be described as a vector in a two-dimensional Hilbert

space, a complex vector space. The special states 0 and 1 are known as the
computational basis states, and form an orthonormal basis for this vector space.
According to quantum theory, when we try to measure the qubit in this basis in
order to determine its state, we get either 0 with probability α² or 1 with
probability β². Since α² + β² = 1 (i.e., the qubit is a unit vector in the
aforementioned two-dimensional Hilbert state), we may (ignoring the overall
phase factor) effectively write its state as ψ = cos(θ)0 + eiφsin(θ)1, where the
numbers θ and φ define a point on the unit three-dimensional sphere, as shown
here. This sphere is often called the Bloch sphere, and it provides a useful
means to visualize the state of a single qubit.
Theoretically, a single qubit can store an infinite amount of information, yet
when measured it yields only the classical result (0 or 1) with certain
probabilities that are specified by the quantum state. In other words, the
measurement changes the state of the qubit, “collapsing” it from the
superposition to one of its terms. The crucial point is that unless the qubit is
measured, the amount of “hidden” information it stores is conserved under the
dynamic evolution (namely, Schrödinger's equation). This feature of quantum
mechanics allows one to manipulate the information stored in unmeasured qubit
with quantum gates, and is one of the sources for the putative power of
quantum computers.
 7

1
Fig. 4.1 The Bloch Sphere
(Stanford Encyclopedia, Quantum Computing)[18]
To see why, let us suppose we have two qubits with us. If these were classical
bits, then they could be in four possible states (00, 01, 10, and 11).
Correspondingly, a pair of qubits has four computational basis states (00, 01,
10 and 11). But while a single classical two-bit register can store these numbers
only one at a time, a pair of qubits can also exist in a superposition of these four
basis states, each of which with its own complex coefficient (whose mod square,
being interpreted as probability, is normalized). As long as the quantum system
evolves unitarily and is unmeasured, all four possible states are simultaneously
“stored” in a single two-qubit quantum register. More generally, the amount of
information that can be stored in a system of n unmeasured qubits grows
exponentially in n. The difficult task, however, is to retrieve this information
efficiently.

4.2 Quantum Gates

Classical computational gates are Boolean logic gates that perform
manipulations of the information stored in the bits. In quantum computing these
gates are represented by matrices, and can be visualized as rotations of the
quantum state on the Bloch sphere. This visualization represents the fact that
quantum gates are unitary operators, i.e., they preserve the norm of the quantum
state (if U is a matrix describing a single qubit gate, then U†U=I, where U† is the
ad joint of U, obtained by transposing and then complex-conjugating U). As in
the case of classical computing, where there exists a universal gate (the
combinations of which can be used to compute any computable function),
namely, the NAND gate which results from performing an AND gate and then a
NOT gate, in quantum computing it was shown that any multiple qubit logic gate
may be composed from a quantum CNOT gate (which operates on a multiple
qubit by flipping or preserving the target bit given the state of the control bit, an
 8

operation analogous to the classical XOR, i.e., the exclusive OR gate) and single
qubit gates. One feature of quantum gates that distinguishes it from classical
gates is that they are reversible: the inverse of a unitary matrix is also a unitary
matrix, and thus a quantum gate can always be inverted by another quantum gate
[13].

Fig. 4.2: The CNOT Gate

Unitary gates manipulate the information stored in the quantum register, and in
this sense ordinary (unitary) quantum evolution can be regarded as computation
(showed how a small set of single-qubit gates and a two-qubit gate is universal,
in the sense that a circuit combined from this set can approximate to arbitrary
accuracy any unitary transformation of n qubits)[2]. In order to read the result of
this computation, however, the quantum register must be measured. The
measurement gate is a non-unitary gate that “collapses” the quantum
superposition in the register onto one of its terms with the corresponding
probability. Usually this measurement is done in the computational basis, but
since quantum mechanics allows one to express an arbitrary state as a linear
combination of basis states, provided that the states are orthonormal (a condition
that ensures normalization) one can in principle measure the register in any
arbitrary orthonormal basis. This, however, doesn't mean that measurements in
different bases are efficiently equivalent. Indeed, one of the difficulties in
constructing efficient quantum algorithms stems exactly from the fact that
measurement collapses the state, and some measurements are much more
complicated than others.

4.3 Quantum Circuits

Quantum circuits are similar to classical computer circuits in that they consist of
wires and logical gates. The wires are used to carry the information, while the
gates manipulate it (note that the wires do not correspond to physical wires; they
may correspond to a physical particle, a photon, moving from one location to
another in space, or even to time-evolution). Conventionally, the input of the
quantum circuit is assumed to be a computational basis state, usually the state
 9

consisting of all 0. The output state of the circuit is then measured in the
computational basis, or in any other arbitrary orthonormal basis. The first
quantum algorithms were constructed in this paradigm [2, 3, and 20]. Additional
paradigms for quantum computing exist today that differ from the quantum
circuit model in many interesting ways. So far, however, they all have been
demonstrated to be computationally equivalent to the circuit model (see below),
in the sense that any computational problem that can be solved by the circuit
model can be solved by these new models with only a polynomial overhead in
computational resources.

4.3. Important Properties of Quantum Circuits

Quantum circuit diagrams have the following constraints which make them
different from classical diagrams.

⚫ They are acyclic (no loops).

⚫ No FANIN, as FANIN implies that the circuit is NOT reversible, and
therefore not unitary.
⚫ No FANOUT, as we can’t copy a qubits state during the computational
phase because of the no-cloning theorem.

4.4 Quantum Algorithms

Algorithm design is a highly complicated task, and in quantum computing it
becomes even more complicated due to the attempts to harness quantum
mechanical features to reduce the complexity of computational problems and to
“speed-up” computation [2]. Before attacking this problem, we should first
convince ourselves that quantum computers can be harnessed to perform
standard, classical, computation without any “speed-up”. In some sense this is
obvious, given the belief in the universal character of quantum mechanics, and
the observation that any quantum computation that is diagonal in the
computational basis, i.e., involves no interference between the qubits, is
effectively classical. Yet the demonstration that quantum circuits can be used to
simulate classical circuits is not straightforward (recall that the former are
reversible while the latter use gates which are inherently irreversible). Indeed,
quantum circuits cannot be used directly to simulate classical computation, but
the latter can still be simulated on a quantum computer using an intermediate
gate, namely the Toffoli gate. This gate has three input bits and three output bits,
two of which are control bits, unaffected by the action of the gate. The third bit
is a target bit that is flipped if both control bits are set to 1, and otherwise is left
alone. This gate is reversible (its inverse is itself), and can be used to simulate
all the elements of the classical irreversible circuit with a reversible one.
Consequently, using the quantum version of the Toffoli gate one can simulate,
although rather tediously, irreversible classical logic gates with quantum
reversible ones. Quantum computers are thus capable of performing any
computation which a classical deterministic computer can do [16].
What about non-deterministic computation? Not surprisingly, a quantum
computer can simulate also this type of computation by using another famous
quantum gate, namely the Hadamard gate, which receives as an input the state 0
and produces the state (0 + 1)/√2. Measuring this output state yields 0 or 1 with
50/50 probability, which can be used to simulate a fair coin toss.
 10

Fig. 4.3: The Hadamard Gate

 11

5 .QUANTUM COMPUTERS

A quantum computer looks like this, taking n input qubits, the register V,
and producing n output qubits, the register W:

Fig 5.1 Quantum Computer

The input register can be prepared as a superposition of states, e.g. an equal

n
superposition of all integers from 0 to 2 :

n
The computer then calculates in parallel the function applied to all 2 integers
simultaneously. From QMP (Quantum Measurement Postulate), when we
measure W, it will choose a Boolean for each bit of the output register
according to the resulting entangled wave function of the output qubits. Design
F so that it maximizes the probability that the output we measure is the answer
we want.

Measuring the output collapses the wave function: get Boolean values for all
the qubits in W. The result is one of the possible outputs.

Imagine that F is (integer) square root W =√V. Prepare V as the superposition of

n
all integers from 0 to 2 , run the computer, then measure W. Result will square
n
root of some number between 0 and 2 . The square root of any such number, with
equal probability. F calculates the square roots of all the integers in parallel, but
QMP says we can only find out about one. For real problems, arrange F so the
probability amplitudes of the output state strongly favor the desired output from
F. .

A quantum computer is probabilistic: we may need to run it multiple times before

we get the answer we want.
 12

5.1 What quantum computers can do?

The biggest success so far -- and the event which ignited the current explosive
growth of the field of quantum computing -- was Peter Shor's 1994 discovery of
an efficient quantum algorithm for finding the prime factors (factoring) of large
integers[8].

By making clever use of superposition’s, interference, quantum parallelism, and

some classical number theory, Shor's algorithm finds a factor of a number N in
time roughly the square of the length of the input (which is log N bits). In
contrast, every known classical algorithm requires exponential time to factor.
Since factoring is one of the most elementary aspects of number theory, the oldest
mathematical discipline, and centuries of efforts by the greatest mathematicians
have not yielded better methods, it is widely believed that such better methods
either do not exist or are prohibitively difficult to find. In fact, this belief
underlies most of current public-key cryptography, notably the RSA system,
ubiquitously used on the Internet and in the financial world. Such crypto-systems
can be broken if one can factor large numbers fast. Accordingly, the advent of
quantum computing compromises all such systems: if a quantum computer can
be built, then most of current cryptography becomes totally insecure, and, for
example, electronic money can be forged. What quantum computing takes away
with one hand (classical public-key crypto), it gives back in another form with
the other (quantum secret-key crypto).In 1984, Bennett and Brassard found a
scheme which allowed two distant parties to obtain a shared secret key via
quantum mechanical communication. Their scheme was always believed to be
fully secure against any type of spy or eavesdropper, and recently this has indeed
been formally proven. On the other hand, some other parts of electronic
transactions, like unforgivable signatures, appear to be beyond the power of
quantum methods.

A third application is Grover's 1996 algorithm for searching databases. Consider

finding some specific record in a large unordered database of N items.
Classically, there is no smarter method than just to go through all records
sequentially, which will requires expected N / 2 time steps for a record in general
position. Grover's algorithm, however, uses quantum superposition’s to examine
all records ``at the same time'', and finds the desired record in roughly √N steps.
12
Examining a 10 records with unit microsecond probes, this is the difference
between about two months of computing and one second of computing! His
algorithm also allows to solve the widespread and notoriously hard NP-complete
problems (such as the traveling salesman problem) quadratic ally faster than
known classical methods--reducing say exponential time with exponent N to
exponential time with exponent N / 2.

A fourth application was initially conceived and primarily developed in

collaboration with the CWI (Centrum voor Wiskunde en Informatics, University
of Amsterdam) group. It deals with the setting where two separated parties, Alice
and Bob, want to compute some function f(x,y) depending on x (only known to
Alice) and y (only known to Bob).

A simple scheme would be for Alice to send her x to Bob and then let Bob do all
the work by himself, but this may take a lot of bits of communication and often
there are much more clever schemes requiring less communication. The field of
 13

communication complexity examines the optimal number of bits that have to be

communicated in order to compute the function at hand. What happens if we
generalize this setting to the quantum world and allow Alice and Bob the use of
quantum computers and qubit-communication?
It turns out that some tasks can be solved with significantly less communication
if we allow such quantization. We have obtained similar advantages by sticking
to classical communication, but allowing Alice and Bob the use of pre-
established ``entangled'' qubits. Both approaches beat the limits provable for just
classical communication.
The above developments suggested the vision that all computation can be
enormously speeded up by quantum computers. But not so! CWI's researchers
obtained strong and general limitations of quantum computers as well. Grover's
algorithm is quadratically faster than classical search algorithms. It was already
known that such a quadratic speed-up is the best quantum computers can achieve
for searching a database, so exponential speed-ups cannot be obtained for this
problem.

CWI-researchers recently showed that the same holds for all problems in the
database-setting of Grover's algorithm: for all such problems, quantum
computers can be at most polynomially faster than classical computers.
Limiting results like the above, of course, do not preclude exponential speed-ups
in different settings, like Shor's, or a clever future setting as yet unknown.
Exploring this potential of quantum computation remains an exciting and
important task for computer scientists and physicists alike.

5.2 How Quantum Computers Do It?

The above results are very promising, but so far mostly theory. How about
actually building quantum computers which can run the fast algorithms like
Shor's, Grover's, or CWI's? To date only very small quantum algorithms (and
slightly bigger quantum crypto devices) have been implemented, but the physical
realization of quantum computers is still in its infancy [9].

The main problem is that quantum superpositions are extremely vulnerable and
any interactions with its environment will quickly cause errors, which degrade
the performance of the computer. Quantum versions of error-correcting codes
have been developed recently which to a large extent solve this problem in
theory, but not yet in the brittle practice of the physical lab (let alone the brittle
practice of our desktops).

This is related to development of Quantum Information Theory--the quantum

extension of classical information theory. CWI's group has contributed to this
research, and to related notions of the information in individual quantum states:
Quantum Kolmogorov Complexity.

Building large quantum computers presents formidable problems to

experimental physicists reminiscent of the initial barriers to classical computing:
unreliable components, physically large components, memory, organization,
communication, and programming. The theory of quantum mechanics is
currently extended, partially by CWI research, in particular with respect to the
algebraic analysis of ``quantum entanglement''--a vital notion in many quantum
algorithms, apparently not yet thoroughly investigated in quantum theory.
 14

5.3 Comparison of Classical and Quantum Computers

Classical computing relies, at its ultimate level, on principles expressed by

Boolean algebra, operating with a (usually) 7-mode logic gate principle, though
it is possible to exist with only three modes (which are AND, NOT, and COPY).
Data must be processed in an exclusive binary state at any point in time - that is,
either 0 (off / false) or 1 (on / true). These values are binary digits, or bits. The
millions of transistors and capacitors at the heart of computers can only be in one
state at any point. While the time that the each transistor or capacitor need be
either in 0 or 1 before switching states is now measurable in billionths of a
second, there is still a limit as to how quickly these devices can be made to switch
state. As we progress to smaller and faster circuits, we begin to reach the physical
limits of materials and the threshold for classical laws of physics to apply [21].
The Quantum computer, by contrast, can work with a two-mode logic
gate: XOR and a mode we'll call QO1 (the ability to change 0 into a superposition
of 0 and 1, a logic gate which cannot exist in classical computing). In a quantum
computer, a number of elemental particles such as electrons or photons can be
used (in practice, success has also been achieved with ions), with either their
charge or polarization acting as a representation of 0 and/or 1. Each of these
particles is known as a quantum bit, or qubit, the nature and behavior of these
particles form the basis of quantum computing. The two most relevant aspects of
quantum physics are the principles of superposition and entanglement.

Table 5.1 Summary of Comparison between classical and quantum

Computing
 15

6. PROJECTED BENEFITS OF QUANTUM COMPUTING

Quantum computing offers many potential benefits to the organizations of

tomorrow. This new conceptualization of computing power will result in three
main benefits: increases in computing power, advances in security, and the ability
for firms to use the sci-fi concept of teleportation. Each of these opportunities
can overcome the limitations of the current computational paradigm [7].

Quantum Computation: Increase in Computing Power

Utilizing quantum parallelism, a quantum computer can calculate or factor any

huge number that is currently infeasible to be analyzed on a classical computer.
For example, factoring a number with 400 digits will take the existing fastest
supercomputers billions of years to accomplish. A quantum computer can obtain
the answer within a year. Therefore, quantum computers well serve the purpose
of searching information in unsorted databases or performing difficult
mathematical calculations that are impossible using semiconductor computers.

Quantum Crypt-ology: Advances in Security

Linked with the first benefit (the increase in computing power) then comes the
possibility for advancements in computing security. Quantum cryptography
allows two parties to exchange public keys in a private channel and thus secure
privacy in quantum communication. The technical aspect of quantum
cryptography requires tremendous amount of physics knowledge; the basic idea
is that quantum mechanics will not allow any eavesdropper to obtain the private
key. Two legitimate parties will reveal a random subset of the key bits and
check the error rate to test for eavesdropping. In so doing, even though
eavesdropping will not be prevented, any attempt, regardless how subtle and
complicated, to break into the communication channel will be detected.

Teleportation

Perhaps the most astounding of the claimed for benefits of quantum computing
is teleportation, the favoured local transportation mechanism in Star Trek
episodes. Teleportation is the capability to make an object or a person
disintegrates in one place while a perfect replica appears in another. In physics,
teleportation has never been taken seriously because of the uncertainty principle.
According to the uncertainty principle, the duplicating process will disturb or
destroy the original objects; the more an object is duplicated, the more it is
destroyed. The detail information regarding how the duplication is made and how
the original object is destroyed is unknown. Therefore, it will reach a point where
one cannot extract enough information from the original to make a perfect
replica.
 16

7. PROJECTED PROBLEMS OF QUANTUM COMPUTING

Even though the benefits sound promising, there are tremendous obstacles still
to be overcome. Some of the problems with quantum computing are as follows :
⚫ Technology required is currently beyond our reach
⚫ Not practical for certain applications (word processing, etc)
⚫ Three technical obstacles:
⚫ De-coherence (quantum decay)
⚫ Error correction
⚫ Hardware architecture
 17

[Link] WILL QUANTUM COMPUTERS BE AVAILABLE?

It has been more than three decades since IBM Fellow, Rolf Landauer, first put
forward the theory of quantum information. A decade later, David Deutsch and
other research fellows proposed the concept of a quantum computer. Since then
progress in the technical development of quantum computing has moved slowly.
Currently, IBM has a three-bit quantum computer while Alamos National
Laboratory announced a seven-bit NMR (Nuclear Magnetic Resonance)
computer not long ago. Even though IBM research fellows promise that a ten-bit
computer will emerge soon, a useful quantum computer will require at least
hundreds and perhaps thousands of qubits. Unfortunately, it appears almost
impossible to develop more than 10 qubits. This is because room temperature
and other conditions will be changed exponentially as the qubits are added
resulting in disturbing the atom’s quantum behaviour. As IBM Research Fellow
Isaac Chuang, a leading scientist in quantum computing research, said “Quantum
mechanics goes away when you look at it. So you have to make sure that the
computer is extremely well isolated from the rest of the world.” In other words,
the commercial development of quantum computing is still limited. The real life
use of quantum computers therefore will not affect our everyday life in the near
future. However, Chuang is very optimistic about it: “Quantum computing
begins where Moore’s law ends—about the year 2020, when circuit features are
predicted to be the size of atoms and molecules”. Other scientists estimate the
birth of commercial quantum computers will be in at least another three decades.
 18

[Link]

It is important that making a practical quantum computing is still far in the

future. Programming style for a quantum computer will also be quite different.
Development of quantum computer needs a lot of money. Even the best scientists
can’t answer a lot of questions about quantum physics. Quantum computer is
based on theoretical physics and some experiments are already made. Building a
practical quantum computer is just a matter of time.
Quantum computers easily solve applications that can’t be done with help of
today’s computers. This will be one of the biggest steps in science and will
undoubtedly revolutionize the practical computing world.
 19

10. REFERENCES

[1] Michael Nielsen, Isaac Chuang, “Quantum Computation and Quantum

Information" , Cambridge University Press (2000).

[2] Peter Shor, “Algorithms for Quantum Computation: Discrete Logarithms

and Factoring," Proceedings of aaaaaathe 35th Annual Symposium on
Foundations of Computer Science 124-134(1994).

[3] R. Feynman Simulating physics with computers, Internat. J. Theoret.

Phys., 21, pp. 467–488(1982).

[4] P. Benioff The computer as a physical system: A microscopic quantum

mechanical Hamiltonian model of computers as represented by Turing
machines, J. Statist. Phys., 22, pp. 563–591(1980).

[5] D. Deutsch, “Quantum theory, the Church–Turing principle and the

universal quantum computer”, Proc. Roy. Soc. London Ser. A, 400, pp. 96–
117(1985).

[6] A. Berthiaume, D. Deutsch, and R. Jozsa , “The stabilisation of quantum

computations”, in Proceedings of the Workshop on Physics of Computation:
PhysComp ’94, IEEE Computer Society Press, Los Alamitos, CA, pp. 60–
62(1994).

[7] C. Bennett, E. Bernstein,G. Brassard, and U. Vazirani. “Strengths and

weaknesses of quantum computing”. SIAM Journal on Computing, 26(5):1510–
1523(1997).

[8] D. Simon” On the power of quantum computation”, in Proceedings of the

35th Annual Symposium on Foundations of Computer Science, IEEE Computer
Society Press, Los Alamitos, CA, pp. 116–123(1994).

[9] S. Lloyd , A potentially realizable quantum computer, Science, 261, pp.

1569–1571(1993).

[10] R. Landauer , “Is quantum mechanics useful?” Philos. Trans. Roy. Soc.
London Ser. A(1995).

[11] O. Goldreich. “On promise problems” (a survey in memory of Shimon

Even [1935–2004]). Electronic Colloquium on Computational Complexity,
Report TR05-018, (2005).

[12] Barenco, A. et al. , ‘Elementary gates for quantum computation’, Phys.

Rev., A 52: 3457–3467(1995).

[13] DiVicenzo, D. ‘Two-bit gates are universal for quantum computation’,

Phys. Rev., A 51: 1015–1022(1995).
 20

[14] Deutsch, D. and Jozsa, R.‘Rapid solution of problems by quantum

computer’, Proc. Roy. Soc. Lond, A 439: 553–558(1992).

[15] E. Knill. Quantum randomness and nondeterminism. Technical Report

LAUR-96- 2186, Los Alamos National Laboratory, 1996. Available as [Link]
e-Print quant-ph/9610012.

[16] A. Kitaev. “Quantum NP”. Talk at AQIP’99: SecondWorkshop on

Algorithms in Quantum Information Processing, DePaul University. (January
1999)

[17] A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation,

volume 47 of Graduate Studies in Mathematics, American Mathematical Society,
(2002).

[18] Quantum Computing (Stanford Encyclopedia of Philosophy)

[19] R. Landauer , Is quantum mechanically coherent computation useful? in

Proceedings of the Drexel-4 Symposium on Quantum Nonintegrability—
Quantum Classical Correspondence, D. H. Feng and B-L. Hu, eds., International
Press (1995)

Research work done from the following URL:-

[1] [Link]
[2] [Link]
[3] [Link]

[4] [Link]

[5] [Link]