Selected topics in quantum programming theory (Q2902529)

The current level of technology demands a significant increase of available computational power that, in turn, leads to developing the computational models generalizing the von Neumann's machine designed in the 1940s -- in most cases, the mid-range models offer the computing performance on the level of from 350 to 500 GFlops (billion floating point operations per second) -- and enabling a straightforward speed-up of solving the existing problems. Two new models of information processing have recently and intensively been discussed in this regard. One is based on the DNA chains processing. The other is based on the quantum theory. Both are unified by the fact that the information processing takes place at the physical level which relies on the laws governing in nature.NEWLINENEWLINENEWLINE The present book aims to discuss these two models of information processing and particularly, first, the development of the big-step operational semantics theory with the appropriate definition of the predicate for the quantum computational model, and second, to build a quantum computing virtual machine or a quantum computing simulator, QCS. These two objectives of the book determines its layout consisting of five chapters. The first chapter aims to provide a basic information about the aforementioned problems. Chapter 2 is a short introduction to quantum computational science and outlines the mathematical structures which lie at the basis of the quantum processing model, the basic theorems about illegal operations in the context of quantum programming languages, especially the theorem on no-cloning, no-deleting, and no-comparing of quantum states, and includes the concept of the entanglement. The next chapter, ``Quantum operational semantics'', discusses the data related to the use of operational semantics within the context of quantum programs and algorithms. It contains the main technical theorem about the possibility of creating operational semantics to describe the quantum algorithm and addresses in particular the concept of the so-called simple quantum predicates. Chapter 4 presents the QCS package which software allows simulation of circuits built on qubits and also on qudits. Some examples of the QCS package are applied for simulating quantum walks with the use of universal graphics processors (aka GPU) and compared with the QWalk package [\textit{F. L. Marquezino} and \textit{R. Portugal}, Comput. Phys. Commun. 179, No. 5, 359--369 (2008; Zbl 1197.81090)] which is nowadays available for this purpose, and for sorting quantum states due to some entanglement. Finally, Chapter 5 summarizes all topics covered in the book and outlines the directions of further research.