In this article, we underline and compare different quantum and deterministic models of computation by means of a probabilistic point of view. The main models used for this are deterministic, probabilistic and quantum Turing machines (DTM, PTM and QTM, respectively). Then we suggest that extending PTM with only part of quantum features is not useful to implement real quantum supremacy if we don’t incorporate them fully. This is done reviewing some notorious quantum physical experiments and quantum algorithms, showing that generally PTM does not fit for them, also if in some particular cases it fits.Here we compare probabilistic and quantum models of computation to underline some common features and differences.
In this article, we underline and compare different quantum and deterministic models of computation by means of a probabilistic point of view. The main models used for this are deterministic, probabilistic and quantum Turing machines (DTM, PTM and QTM, respectively). Then we suggest that extending PTM with only part of quantum features is not useful to implement real quantum supremacy if we don’t incorporate them fully. This is done reviewing some notorious quantum physical experiments and quantum algorithms, showing that generally PTM does not fit for them, also if in some particular cases it fits.Here we compare probabilistic and quantum models of computation to underline some common features and differences.
Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.
Abstract In this chapter, we introduce the definitions of automata Turing machines. We present different flavors of Turing machines including deterministic, probabilistic, and multi-tape machines. We present several complexity classes, i.e. collections of problems that can be solved by a machine with similar resources, including the P and NP classes. We present the Church-Turing thesis, which states that if a problem can be solved by a physical machine, then it can also be solved by any deterministic Turing machine. In the last part of the chapter, we introduce quantum Turing machines and the quantum circuit model. We study the complexity class BQP. This is the class of problems that can be solved by a quantum computer with polynomial resources and a small error probability. Finally, we introduce QMA, the quantum version of the complexity class NP. We present the k-LOCAL problem, and we show that this problem is in QMA
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).
Parallelism represents an essential aspect of human mind/brain activities. One can recognize some common features between psychological parallelism and the characteristic parallel structures that arise in quantum theory and in quantum computation. The article is devoted to a discussion of the following questions: a comparison between classical probabilistic Turing machines and quantum Turing machines.possible applications of the quantum computational semantics to cognitive problems.parallelism in music.
This manuscript is intended for readers who have a general interest in the subject of quantum computation and provides an overview of the most significant developments in the field. It begins by introducing foundational concepts from quantum mechanics—such as superposition, entanglement, and the no-cloning theorem—that underpin quantum computation. The primary computational models are discussed, including gate-based (circuit) quantum computing, adiabatic quantum computing, measurement-based quantum computing and the quantum Turing machine. A selection of significant quantum algorithms are reviewed, notably Grover’s search algorithm, Shor’s factoring algorithm, and Quantum Singular Value Transformation (QSVT), which enables efficient solutions to linear algebra problems on quantum devices. To assess practical performance, we compare quantum and classical implementations of support vector machines (SVMs) using several synthetic datasets. These experiments offer insight into the capabilities and limitations of near-term quantum classifiers relative to classical counterparts. Finally, we review leading quantum programming platforms—including Qiskit, PennyLane, and Cirq—and discuss their roles in bridging theoretical models with real-world quantum hardware. The paper aims to provide a concise yet comprehensive guide for those looking to understand both the theoretical foundations and applied aspects of quantum computing.
The work includes the analyses of the theoretical capabilities of quantum-mechanical versus classical computer models in terms of their universality, their application domain, their efficacy in solving the problems and their technological feasibility. The concepts of deterministic Turing machine, probabilistic Turing machine and quantum-mechanical Turing machine are exposed. The concept of basic information unit of quantum-mechanical computer modelqubit is introduced and the qubit is represented through the use of Bloch sphere. The use of Dirac's bra-ket notation in description of quantum-mechanical state is explained, and the notation is used to form state equation of a quantummechanical Turing machine cell. Especially, consequences of quantum parallelism, quantum interference and wave function collapse are studied in respect to capabilities of quantum-mechanical computer models. The interrelationship between classes of problems that can be efficiently solved by quantum mechanical and/or classical computer models is displayed.