[attachment=10069]
CHAPTER 1
INTRODUCTION
1.1 GENERAL INTRODUCTION
Quantum computing is a combination of physics, mathematics and computer science. Quantum algorithm exponentially “speed up” classical computation.
The basic paradigm for quantum algorithm is the quantum circuit model, which is composed of the basic quantum units of information(qubits) and quantum gates.
By interacting with each other while being isolated from the external environment, qubits can perform certain calculations exponentially faster than conventional computers.
The quantum computer, following the laws of quantum physics, would gain enormous processing power through the ability to be in multiple states, and to perform tasks using all possible permutations simultaneously.
By doing a computation on many different numbers at once, then interfering the results to get a single answer, a quantum computer has the potential to be much more powerful than a classical computer of the same size.
1.2 QUANTUM ALGORITHMS
The main quantum algorithms are:
 Quantum circuit based algorithm
The Deutsch Oracle
The Deutsch Jozsa Oracle
The Simon Oracle
Shor’s Algorithm
Grover’s Algorithm
 Adiabatic algorithm
 Measurement based algorithm
 Topological quantum field theory(TQFT) algorithm
1.3 ENEMIES OF QUANTUM COMPUTING
There are two known enemies of quantum computing:
a) Decoherence
If we keep on putting quantum gates together into circuits we will quickly run into some serious practical problems. The more interacting qubits are involved the harder it tends to be to engineer the interaction that would display the quantum interference. Apart from the technical difficulties of working at single-atom and single-photon scales, one of the most important problems is that of preventing the surrounding environment from being affected by the interactions that generate quantum superposition. The more components the more likely it is that quantum computation will spread outside the computational unit and will irreversibly dissipate useful information to the environment. This process is called “Decoherence”. Even though we try to isolate the quantum system from the environment much as we can, we cannot supply total isolation. Therefore, the interaction of the quantum system and the environment result in “Decoherence” of the quantum state, which is equivalent to a partial measurement of the state by the environment.
b) Gate Inaccuracies
Decoherence is not the only problem with quantum computing. Gates, whether they are classical or quantum, are not perfect. The gates are usually combined together. So small errors in gates can combine together during computation and eventually causing failure, and it is not clear how to correct these small errors.
The simplest example of error correcting code is a repetition code: replacing the bit we want to protect by 3 copies of the bit,
0 → (000)
1→ (111)
Now an error may occur that causes one of the three bits to flip; If it’s the first bit, say,
(000) → (100)
(111) → (011)
Now in spite of the error, the bit can be encoded correctly, by majority voting.
CHAPTER 2
CONCEPTS OF QUANTUM COMPUTING
2.1 ELEMENTS OF QUANTUM COMPUTING
Generally we’ll think of a quantum computer as a classical computer with a quantum circuit attached to it with some kind of interface between conventional
and quantum logic. Since there are only a few things a quantum computer does better than a classical computer it makes sense to do the bulk of the processing on the classical machine.
1) Bits and Qubits
These are the”nuts and bolts” of quantum computing. It describes qubits, gates, and circuits. Quantum computers perform operations on qubits which are analogous to conventional bits but they have an additional property in that they can be in a superposition.
A quantum register with 3 qubits can store 8 numbers in superposition simultaneously, and a 250 qubit register holds more numbers (superposed) than
there are atoms in the universe.
Representation of data-qubits
2) Single Qubit
Classical computers use two discrete states to represent a unit of information, this state is called a binary digit (or bit for short). A bit has the following two values:
0 and 1
There is no intermediate state between them, i.e. the value of the bit cannot be in a superposition.
Quantum bits, or qubits, can on the other hand be in a state ”between” 0 and
1, but only during the computational phase of a quantum operation. When
measured, a qubit can become either:
The | > symbolic notation is part of the Dirac notation.
3) Multiple Qubit
The potential amount of information available during the computational phase
grows exponentially with the size of the system, i.e. the number of qubits.
This is because if we have n qubits the number of basis states is 2n. E.g. if
we have two qubits, forming a quantum register then there are four (=22)
computational basis states: forming

Here |01> means that qubit 1 is in state |0> and qubit 2 is in state |1>, etc.
2.2 CONCEPTS OF QUANTUM COMPUTING
The following concepts are important for quantum computing:
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.
2) 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 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) 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 behaviour 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.