Quantum computing is essentially harnessing and exploiting the amazing
laws of quantum mechanics to process information. A traditional computer
uses long strings of “bits,” which encode either a zero or a one. A
quantum computer, on the other hand, uses quantum bits, or qubits.
What's the difference? Well a qubit is a quantum system that encodes the
zero and the one into two distinguishable quantum states. But, because
qubits behave quantumly, we can capitalize on the phenomena of
"superposition" and "entanglement."Quantum computing is the area of study focused on developing computer technology based on the
principles of quantum
theory, which explains the nature and behavior of energy and matter on the quantum (atomic and
subatomic) level. Development of a quantum computer, if
practical, would mark a leap forward in computing capability far greater than that from the abacus to a modern day
supercomputer, with
performance gains in the billion-fold realm and beyond. 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. Current centers of research in
quantum computing include MIT, IBM, Oxford University, and the Los Alamos National Laboratory.
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. Entanglement Particles (such as photons, electrons, or qubits) that have interacted at some point retain a type of connection and can be entangled with each other in pairs, in a process known as correlation . Knowing the spin state of one entangled particle - 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 superpostition, 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. This is a real phenomenon (Einstein called it "spooky action at a distance"), the mechanism of which cannot, as yet, be explained by any theory - it simply must be taken as given. Quantum entanglement allows qubits that are separated by incredible distances to interact with each other instantaneously (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.
A qubit is a quantum bit , the counterpart in quantum computing to the binary digit or bit of classical computing. Just as a bit is the basic unit of information in a classical computer, a qubit is the basic unit of information in a quantum computer . 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 qubit; the nature and behavior of these particles (as expressed in quantum theory ) form the basis of quantum computing. The two most relevant aspects of quantum physics are the principles of superposition and entanglement .
A quantum gate or quantum logic gate is a rudimentary quantum circuit operating on a small number of qubits. They are the analogues for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible, unlike many classical logic gates. Some universal classical logic gates, such as the Toffoli gate, provide reversibility and can be directly mapped onto quantum logic gates. Quantum logic gates are represented by unitary matrices.The most common quantum gates operate on spaces of one or two qubits. This means that as matrices, quantum gates can be described by 2 x 2 or 4 x 4 matrices with orthonormal rows.
Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor. The algorithm is significant because it implies that public key cryptography might be easily broken, given a sufficiently large quantum computer. RSA, for example, uses a public key N which is the product of two large prime numbers. One way to crack RSA encryption is by factoring N, but with classical algorithms, factoring becomes increasingly time-consuming as N grows large; more specifically, no classical algorithm is known that can factor in time O((log N)k) for any k. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.
Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.
The algorithm is composed of two parts. The first part of the algorithm
turns the factoring problem into the problem of finding the period of a
function, and may be implemented classically. The second part finds the
period using the quantum Fourier transform, and is responsible for the
quantum speedup.
- Obtaining factors from period
- Finding the period
reference :
