Definition
A quantum computer is a computer design which uses the principles of quantum physics to increase the computational power beyond what is attainable by a traditional computer. Quantum computers have been built on the small scale and work continues to upgrade them to more practical models.
History of Quantum Computing
Quantum computing tends to trace its roots back to a 1959 speech by Richard P. Feynman in which he spoke about the effects of miniaturization, including the idea of exploiting quantum effects to create more powerful computers. (This speech is also generally considered the starting point of nanotechnology.)
Of course, before the quantum effects of computing could be realized, scientists and engineers had to more fully develop the technology of traditional computers. This is why, for many years, there was little direct progress, nor even interest, in the idea of making Feynman's suggestions into reality.
In 1985, the idea of "quantum logic gates" was put forth by University of Oxford's David Deutsch, as a means of harnessing the quantum realm inside a computer. In fact, Deutsch's paper on the subject showed that any physical process could be modeled by a quantum computer.
Nearly a decade later, in 1994, AT&T's Peter Shor devised an algorith that could use only 6 qubits to perform some basic factorizations ... more cubits the more complex the numbers requiring factorization became, of course.
A handful of quantum computers have been built. The first, a 2-qubit quantum computer in 1998, could perform trivial calculations before losing decoherence after a few nanoseconds. In 2000, teams successfully built both a 4-qubit and a 7-qubit quantum computer. Research on the subject is still very active, although some physicists and engineers express concerns over the difficulties involved in upscaling these experiments to full-scale computing systems. Still, the success of these initial steps do show that the fundamental theory is sound.
How a Quantum Computer Would Work
A quantum computer, on the other hand, would store information as either a 1, 0, or a quantum superposition of the two states. Such a "quantum bit," called a qubit, allows for far greater flexibility than the binary system.
Specifically, a quantum computer would be able to perform calculations on a far greater order of magnitude than traditional computers ... a concept which has serious concerns and applications in the realm of cryptography & encryption. Some fear that a successful & practical quantum computer would devastate the world's financial system by ripping through their computer security encryptions, which are based on factoring large numbers that literally cannot be cracked by traditional computers within the life span of the universe. A quantum computer, on the other hand, could factor the numbers in a reasonable period of time.
Entanglement
Entanglement is a term used in quantum theory to describe the way that particles of energy/matter can become correlated to predictably interact with each other regardless of how far apart they are.
Particles, such as photons, electrons, or qubits that have interacted with each other retain a type of connection and can be entangled with each other in pairs, in the process known as correlation. Knowing the spin state of one entangled particle - whether the direction of the spin is up or down - allows one to know that the spin of its mate is in the opposite direction. Even more amazing is the knowledge that, due to the phenomenon of superposition, the measured particle has no single spin direction before being measured, but is simultaneously in both a spin-up and spin-down state. The spin state of the particle being measured is decided at the time of measurement and communicated to the correlated particle, which simultaneously assumes the opposite spin direction to that of the measured particle. Quantum entanglement allows qubits that are separated by incredible distances to interact with each other immediately, in a communication that is not limited to the speed of light. No matter how great the distance between the correlated particles, they will remain entangled as long as they are isolated.
Entanglement is a real phenomenon (Einstein called it "spooky action at a distance"), which has been demonstrated repeatedly through experimentation. The mechanism behind it cannot, as yet, be fully explained by any theory. One proposed theory suggests that all particles on earth were once compacted tightly together and, as a consequence, maintain a connectedness. Much current research is focusing on how to harness the potential of entanglement in developing systems for quantum cryptography and quantum computing.
QUBIT
a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit. A qubit is a two-state quantum-mechanical system, such as the polarization of a single photon: here the two states are vertical polarization and horizontal polarization. In a classical system, a bit would have to be in one state or the other, but quantum mechanics allows the qubit to be in a superposition of both states at the same time, a property which is fundamental to quantum computing.
Operations on pure qubit states
There are various kinds of physical operations that can be performed on pure qubit states
- A quantum logic gate can operate on a qubit: mathematically speaking, the qubit undergoes a unitary transformation. Unitary transformations correspond to rotations of the qubit vector in the Bloch sphere.
- Standard basis measurement is an operation in which information is gained about the state of the qubit. The result of the measurement will be either ,
with probability 
, or 
, with probability 
. Measurement of the state of the qubit alters the values of α and β. For instance, if the result of the measurement is , α is changed to 1 (up to phase) and β is changed to 0. Note that a measurement of a qubit state entangled with another quantum system transforms a pure state into a mixed state.
Quantum Gate
quantum computing and specifically the quantum circuit model of computation, a quantum gate (or quantum logic gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.
Unlike many classical logic gates, quantum logic gates are reversible. However, classical computing can be performed using only reversible gates. For example, the reversibleToffoli gate can implement all Boolean functions. This gate has a direct quantum equivalent, showing that quantum circuits can perform all operations performed by classical circuits.
Quantum logic gates are represented by unitary matrices. The most common quantum gates operate on spaces of one or two qubits, just like the common classical logic gates operate on one or two bits. This means that as matrices, quantum gates can be described by 2 × 2 or 4 × 4 unitary matrices.
Commonly used gates
- Hadamard gate
- Pauli-X gate
- Pauli-Y gate
- Pauli-Z gate
- Phase shift gates
- Swap gate
- Controlled gates
- Toffoli gate
- Fredkin gate
Shor's algorithm
named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994. Informally it solves the following problem: Given an integer N, find its prime factors.
On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input). Specifically it takes time O((log N)3), demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is substantially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — aboutO(e1.9 (log N)1/3 (log log N)2/3). The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squaring
Shor's algorithm consists of two parts:
1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
2. A quantum algorithm to solve the order-finding problem.
Classical part
1. Pick a random number a < N.
2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
3. If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.
4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:
i.e. the order r of α in 
, which is the smallest positive integer r for which 
,or 
5. If r is odd, go back to step 1.
6. If a r /2 ≡ −1 (mod N), go back to step 1.
7. gcd(ar/2 ± 1, N) is a nontrivial factor of N. We are done.
Explanation of the algorithm
- Obtaining factors from period
- Finding the period
- The bottleneck
Referense :
is
divided into four sections. 
