Abstract:
Quantum
computers don't exist. Or better, they don't exist outside of world of papers and
labs. Quantum computation is not something that happens inside any microchip
obtainable in the market today. Although some quantum phenomena do occur inside
solid state components of modern computers, the result of the computation is in
ultimate analysis, classical, not taking any advantages of quantum mechanics in
the computation itself. All algorithms and result computations, nevertheless
how sophisticated they seem, are performed in physical devices
that are implementations of a machine, a Universal Turing Machine (UTM), which
is governed by laws of classical physics and, as Feynman noted, is unable to
simulate quantum systems efficiently.
Quantum
computers are able of new modes of computation in a fashion that is unfeasible
to a UTM. Its very own characteristics provide elements that could achieve high
parallelism in such way to compute problems classified as intractable by
current computer theory.
In
this presentation I briefly discuss Quantum Computing in general and present
three models of quantum computers: Quantum Turing Machines, Quantum Circuits
and Quantum Cellular Automata.