Absolutely every computer nowadays, from the “dumb machine” a person uses to stalk in Facebook , to the ultra-powerful technologies utilized to compute multiple calculations at CERN, Switzerland, are defined as Turing Machines, a concept that is highly applicable to every single device of our modern geeky- environment.
Impressively, none of those aforementioned computers, is more sophisticated than the first Turing machine built long time ago; the principle remains the same: The Universal Turing Machine is the essence of contemporary technology.
The computers we buy at iSHOP, are still machines operating in “sequential routines”; executing elemental (or advanced) operations over a variety of functions with this tactic. The problem arises when that basic principle of operation, limits computational tasks totally, considering the resources involved and overalls, the complexity of the procedures we are dealing with.
For instance you cannot intend to solve problems outside of “PTIME” (refer to MIT news). We know that problems in PTIME have resolution algorithms describing a polynomic function when measuring performance time (depending on data input). Discrete logarithm calculus is NOT a PTIME problem. But we are not saying it cannot be “solved”, because certainly a computer or a human can theoretically do it, however in order to execute the operation, you will require a “really enormous capacity” of computational resources, so finding a solution appears to be impractical. In this case, quantum computing is not only useful “to attack” this kind of “utopic problems”; it also opens a big space of possibilities for computer hardware-improvement such as enhancing efficiency, speed or by adding particular properties of natural physics’ phenomena, directly from quantum mechanics, to artificial devices.
For example, one possibility could be the creation of quantum algorithms via Quantum Fourier Transforms or “Quantum Walks”, which would be a considerable practical technique for disentangling complex problems, as we are going to describe briefly.
The inspiration of creating “walks” governed by the laws of quantum mechanics, are the widely famous “random walks”. The basic idea relies on the movement of a particle, called “the walker”, over discrete points in a single line without any restriction. The walker’s movement (to the right or left) depends on a probabilistic pattern (a coin, maybe).
The equation describing the position of our walker, from an initial start in 0 and after N movements, (the coin has been thrown N times) is a binomial distribution which variance is proportional to the number of steps done.
We have briefly defined that random walks are procedures built with a probabilistic distribution, and they are a scheme extensively used by conventional computers for many purposes. This type of paradigm has many applications on NP problem solving, (like Discrete Logarithm calculus), because many effective algorithms are based on stochastic processes and random walks, so it is possible to find “less resource-consuming” solutions; otherwise you will require a brute-force algorithm exploring each possibility of the problem’s universe.
In quantum walks, the stochastic element (the coin) is replaced by an “evolution operator” called “unitary operator” applied over the particle. But, if this particle is measured at any step, “Decoherence” appears and the “main quantum process” transforms into a “normal” stochastic process. This “Decoherence” is probably one of the most interesting phenomena occurring in the quantum world and we will explain it shortly.
Let’s bring the first coin; this can only have two “states”, heads or tails, and when we play coin tossing in the “real world”, which inherently has only two possible and equally likely otucomes, it can have one and ONLY ONE state at a time. On the other hand, in quantum mechanics, if two states of a coin are taking place, then combinations are existing in parallel. Basically, a quantum coin is able to check in two states at the same time: heads and tails, half head – half tails, but in this case, what happen when we try to catch it? What we see? Half tails? Half heads? Both of them? Here is the magic of quantum physics: the superposition (what we call head AND tails) can be sustained only if we don’t see it, because when we have a quick look at the coin, “coherence” disappears. And, how it is possible to say that superposition exists, if we are not able to see it or measure it? Well, this “strange condition” leave some evidences describing precise characteristics that we are going to skip for the purposes of the article.
Getting back to the quantum walks, the particle should remain “untouched” to acquire its natural “coherence” with specific criteria. Just as the first example, the walker moves to the left and right simultaneously, and after several N steps, the quantum walker obtains a “superposition” of many places. Only when we measure, we obtain a precise position, but of course, with the immediate consequence of eliminating the other states. This “parallelism” is key to develop quantum algorithms, based on quantum walks in order to improve operations in a more efficient way than we can currently.
Generally speaking, quantum walks are very powerful, and could also be used as models of universal and natural occurrences. If you aren’t convinced of the capabilities of quantum walks, maybe you want to take your applications and numbers outside of theoretical computer science, and into the “real world” of natural sciences, then you can also use quantum walks just like in computers: to classify and understand certain natural processes. The incredible example of this, is for modeling photosynthesis (Rebentrost, P., Mohseni, M., Kassal, I., Lloyd, S., & Aspuru-Guzik, A.. «Environment-assisted quantum transport». New Journal of Physics, 11, 033003).
In conclusion, we can be amazed of how quantum computing is handling a vast amount of topics in many subjects, just by reading the research completed through the last years. It is a solid field of exciting matters for many professionals like physicists, biologists, mathematicians, engineers, and computer scientists. From this perspective we can choose the problems which will serve best to our area of study, and then go to: Qubits, Quantum Information Theory, Error Correction, Decoherence, Quantum Cryptography, Quantum Complexity and Construction of Quantum Computers, etc.
Please, select the one that fits you.