Archive for Mei 2014
QUANTUM COMPUTING
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.
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 
, 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
Reference :
