Information Technology Reference
In-Depth Information
Feynman noted, the real world performs quantum mechanical computations exponen-
tially faster than can classical simulations
”.
As we can see, real world computing is breaking the Turing paradigm [28]. In follow-
ing we briefly summarize two main representatives of real world alternative comput-
ing (quantum, DNA computation) and discuss its properties.
Both, quantum and DNA are not restricted to silicon chip HW platform (dealing
physical walls), come from nature, real world observation, both are massive parallel
(dealing theoretical walls) and promising to be more efficient.
3.1 Quantum Computation
There is still an open question whether all quantum mechanical events are Turing-
computable, although it is known that classical TM is the same powerful as quantum
TM and vice versa [7]. However Deutsch [7], Bernstein and Vazirani [4] shoved that
there exist problems that quantum TM solve problems faster than classical one, can be
more efficient.
For instance, Grover's quantum searching algorithm compute with
N
entries in
O(
N
1/2) time and using O(log
N
) storage space [9]. In contrast to classically, search-
ing an unsorted database requires a linear search, which is O(
N
) in time. Also Shor
[27] demonstrated that a quantum computer could efficiently solve a well-known
problem of integer factorization, i.e. finding the factors of a given integer
N
, in a time
which is polynomial in log
N
. This is exponentially faster than the best-known classi-
cal factoring algorithm. Quantum computing was also successfully used to “
treat
”
(finding better “
solutions
” than classical computation can reach) some of artificial
intelligence NP-hard problems [23, 15].
Although quantum computing is promising to overcome physical walls of classical
silicon chip design and decrease time complexity at case of certain theoretical prob-
lems, it cannot be used in practice due to its „
own
“ walls as seems today. Main disad-
vantages are:
•
Expensive to fabricate.
•
Today quantum 16-qubit chip (D-Wave) is not enough.
•
Decoherence, unwanted interaction with environment during the computation, the
lost of superposition state.
3.2 DNA Computation
Operations of molecular genetics can be understood as operations over strings/strands
and by proper sequence of such operations we are able to execute required computa-
tion. In 1994 Adleman [1], inventor of DNA computation, demonstrated how to use
DNA to solve a well-known NP-complete problem, the "
travelling salesman
" prob-
lem in polynomial time. The goal of the problem is to find the shortest route between
numbers of cities, going through each city only once. Adleman chose to find the
shortest route between 7 cities. In later years DNA computation was generalized to
solve other NP-complete problems and other specific problems like SAT problem, 3-
SAT problem [5]. Although the DNA computing is also promising to overcome
physical walls of classical silicon chip design and solve NP-complete problems
