Complex Systems and Computing
– Quantum Computing

The most important reasons to study quantum computing and quantum information theory can be summarized as follows: Computation, realized in any manner is always a physical process. As the most accurate known description of the physical world is quantum physical, it implies that to study fundamental limits of computing and information processing, one should indeed study their realizations in quantum mechanical environment. Thus, to study quantum information processing is to study the fundamental limits of computing given by the nature itself.

The nature of quantum information provides considerable advantage over traditional information processing for some computational tasks. The most famous example of the said benefit was given by P. Shor in 1994, when he introduced a polynomial-time algorithm for factoring integers and thus breaking major public-key cryptosystems. Another known example of quantum information processing begin different from its traditional counterpart is quantum cryptography, whose security is based rather on the physical nature of quantum information than on the computational complexity of breaking the cipher.

As a coherent quantum state can only take place in a microsystem and is extremely vulnerable to external noise, it is evident that the technical realizations of quantum information processing are difficult to construct. The persistent development work lasting over two decades has presented commercial solutions to quantum cryptography already since the beginning of the new millenium, but quantum computers capable of universally handling hundreds of quantum bits are still outside of the technological realm of the mankind.

While the desired technology is unreachable, the theory of quantum computing has a strong tradition, already. The computing models and their basic properties have been translated from classical to quantum area. That translation work has also brought forth many basic questions to be resolved: For example, the many of the relationship questions between classical and quantum complexity classes is are difficult problems, open since they were first considered.

M. Hirvensalo of the Fundim group has been interested in the mathematical foundations of quantum computing. Especially he has studied the finite quantum automata and the decidability properties therein, as well as the potential generalization of current models.

Some recent work on quantum computing:

• M. Hirvensalo: Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages. LNCS 4362, pp. 309-319 (2007).
• M. Hirvensalo: Various Aspects of Finite Quantum Automata. Lecture Notes in Computer Science 5257, pp. 21-33 (2008)
• M. Hirvensalo (ed): Quantum and Probabilistic Automata (Theoretical Computer Science; Vol 410, issue 20, 2009)
• M. Hirvensalo (ed): Quantum Computing area of Handbook of Natural Computing (Springer 2010)
• M. Hirvensalo: Mathematics for Quantum Information Processing, Chapter in the handbook (Springer 2010)
• M. Hirvensalo: Quantum Automata with Open Time Evolution. International Journal of Natural Computing Research 1, 2010.