quantum automata and computation



1 Topic on Quantum Automata and Quantum Computations

1.1 Introduction

A quantum automatonPlanetmathPlanetmath can be simply described as an extensionPlanetmathPlanetmathPlanetmath of an automatonMathworldPlanetmath with quantum states instead of the sequentially determined states, inputs and outputs of a sequential, or state machine. The precise mathematical definitions of quantum automaton, variable automaton, and quantum computation were first introduced formally in refs. [1] and [2] in relationMathworldPlanetmathPlanetmathPlanetmath to relational models in Quantum Relational Biology (loc.cit).

1.2 Historical Note

Quantum computation and quantum machinesMathworldPlanetmath (or nanobots) were much publicized in the early 1980’s by Richard Feynman (Nobel Laureate in Physics: QED),and, subsequently, a very large number of papers- too many to cite all of them here- were published on this topic by a rapidly growing number of quantum theoreticians and some applied mathematicians.

1.3 Quantum Automata

Definition 1.1.

A simple definition of quantum automaton is obtained by considering instead of the transition function of a classical sequential machine, the (quantum) transitions in a finite quantum system with definite probabilities determined by quantum dynamics. The quantum state spacePlanetmathPlanetmath of a quantum automaton is thus defined as a quantum groupoidPlanetmathPlanetmathPlanetmath over a bundle of Hilbert spaces, or over rigged Hilbert spacesPlanetmathPlanetmath. Formally, whereas a sequential machine, or state machine with state space S, input set I and output set O, is defined as a quintuple: (S,I,O,δ:S×SS,λ:S×IO), a quantum automaton is defined by a triple (H,Δ:HH,μ), where H is either a Hilbert space or a rigged Hilbert space of quantum states and operators acting on H, and μ is a measure related to the quantum logicPlanetmathPlanetmath, LM, and (quantum) transition probabilities of this quantum system.

Remark 1.1.

Quantum computation becomes possible only when macroscopic blocks of quantum states can be controlled via quantum preparation and subsequent, classical observation. Obstructions to building, or constructing quantum computers are known to exist in dimensionsPlanetmathPlanetmath greater than 2 as a result of the standard K-S theoremMathworldPlanetmath. Subsequent definitions of quantum computers reflectPlanetmathPlanetmath attempts to either avoid or surmount such difficulties often without seeking solutions through quantum operator algebrasPlanetmathPlanetmathPlanetmath and their representations related to extended quantum symmetries which define fundamental invariantsMathworldPlanetmath that are key to realizing quantum computation.

Definition 1.2.

: alternatively, as a quantum algebraic topology object, a quantum automaton is defined by the triplet (𝖦,H-𝖦,Aut(𝖦)), where 𝖦 is a locally compact quantum groupoid, H-𝖦 are the unitary representationsMathworldPlanetmath of 𝖦 on rigged Hilbert spaces 𝖦 of quantum states and quantum operators on H, and Aut(𝖦) is the transformationPlanetmathPlanetmath, or automorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, groupoidPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of quantum transitions.

Remark. Other definitions of quantum automata and quantum computations have also been reported that are closely related to recent experimental attempts at constructing quantum computing devices.

Two examples of such definitions are briefly considered next.

Definition 1.3.

: quantum automata were defined in refs.[1] and [2] as generalized, probabilistic automata with quantum state spaces. Their next-state functions operate through transitions between quantum states defined by the quantum equations of motions in the Schrödinger representation, with both initial and boundary conditions in space-time.

A new theorem was proven which states that the categoryMathworldPlanetmath of quantum automata and automata–homomorphismsMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath has both limits and colimitsMathworldPlanetmath. Therefore, both categories of quantum automata and classical automata (sequential machines) are bicomplete. A second new theorem established that the standard automata category is a subcategoryMathworldPlanetmath of the quantum automata category.

1.4 Quantum Automata Applications to Modeling Complex Systems

The quantum automata category has a faithful representationMathworldPlanetmath in the category of Generalized (M,R) -systems which are open, dynamic bio-networks ([3]) with defined biological relations that represent physiological functions of primordial(s), single cells and the simpler organisms. A new category of quantum computers is also defined in terms of reversible quantum automata with quantum state spaces represented by topological groupoidsPlanetmathPlanetmathPlanetmathPlanetmath that admit a local characterizationMathworldPlanetmath through unique ‘quantum’ Lie algebroids. On the other hand, the category of n-Łukasiewicz algebrasMathworldPlanetmathPlanetmathPlanetmath has a subcategory of centered n- Łukasiewicz algebras [16] (which can be employed to design and construct subcategories of quantum automata based on n-Łukasiewicz diagrams of existing VLSI. Furthermore, as shown in ref.([16] the category of centered n-Łukasiewicz algebras and the category of Boolean algebrasMathworldPlanetmath are naturally equivalent.

VariableMathworldPlanetmath machines with a varying transition function were previously discussed informally by Norbert Wiener as a possible model for complex biological systems although how this might be achieved in Biocybernetics has not been specifcally, or mathematically presented by Wiener.

A ‘no-go’ conjecture was also proposed which states that Generalized (M,R)–Systems complexity prevents their completePlanetmathPlanetmathPlanetmathPlanetmath computability by either standard or quantum automata. The conceptsMathworldPlanetmath of quantum automata and quantum computation were initially studied and are also currently further investigated in the contexts of quantum genetics, genetic networks with nonlinear dynamics, and bioinformatics. In a previous publication (ICB71a)– after introducing the formal concept of quantum automaton–the possible implicationsMathworldPlanetmath of this concept for correctly modeling genetic and metabolic activities in living cells and organisms were also considered. This was followed by a formal report on quantum and abstract, symbolic computationMathworldPlanetmathPlanetmath based on the theory of categories, functorsMathworldPlanetmath and natural transformations [2]. The notions of topological semigroup, quantum automaton,or quantum computer, were then suggested with a view to their potential applications to the analogous simulation of biological systems, and especially genetic activities and nonlinear dynamics in genetic networks. Further, detailed studies of nonlinear dynamics in genetic networks were carried out in categories of n-valued, Łukasiewicz Logic AlgebrasPlanetmathPlanetmath that showed significant dissimilarities [ICB77] from the widespread Bolean models of human neural networks that may have begun with the early publication of [18]. Molecular models in terms of categories, functors and natural transformations were then formulated for uni-molecular chemical transformations, multi-molecular chemical and biochemical transformations [ICB2k4a]. Previous applications of computer modeling, classical automata theory, and relational biology to molecular biology, oncogenesis and medicine were extensively reviewed and several important conclusionsMathworldPlanetmath were reached regarding both the potential and limitations of the computation-assisted modeling of biological systems, and especially complex organisms such as Homo sapiens sapiens [3]. Novel approaches to solving the realization problems of Relational Biology models in Complex System Biology are introduced in terms of natural transformations between functors of such molecular categories. Several applications of such natural transformations of functors were then presented to protein biosynthesis, embryogenesis and nuclear transplant experiments. Other possible realizations in Molecular Biology and Relational Biology of Organisms were then suggested in terms of quantum automata models of Quantum Genetics and Interactomics. Future developments of this novel approach are likely to also include: Fuzzy Relations in Biology and Epigenomics, Relational Biology modeling of Complex Immunological and Hormonal regulatory systems, n-categories and generalized LM–Topoi of Łukasiewicz Logic Algebras and intuitionistic logicMathworldPlanetmath (Heyting) algebras for modeling nonlinear dynamics and cognitive processes in complex neural networks that are present in the human brain, as well as stochastic modeling of genetic networks in Łukasiewicz Logic Algebras (LLA).

1.4.1 Quantum Automata,Computation and Dynamics Represented by Categories and Functors

Molecular models were previously defined in terms of categories, functors and natural transformations were formulated for unimolecular chemical transformations, multi-molecular chemical and biochemical transformations [13]. Dynamic similarities or analogies between categories of classical, quantum or complex systemsMathworldPlanetmath and their transformations were then naturally represented in terms of adjoint functorsMathworldPlanetmathPlanetmathPlanetmath and the corresponding natural equivalences.

Remark. Previous applications of computer modeling, classical automata theory, and relational biology to molecular biology, neural networks, oncogenesis and medicine were extensively reviewed in a previous monograph and several important conclusions were reached regarding both the potential and the severe limitations of the algorithmMathworldPlanetmath driven, recursive computation-assisted modeling of complex biological systems [3].


  • 1 Baianu, I.C.: 1971a, Categories, Functors and Quantum Algebraic Computations, in P. Suppes (ed.), Proceed. Fourth Intl. Congress Logic-Mathematics-Philosophy of Science, September 1–4, 1971, the University of Bucharest.
  • 2 Baianu, I.C.: 1971b, Organismic SupercategoriesPlanetmathPlanetmathPlanetmathPlanetmath and Qualitative DynamicsPlanetmathPlanetmath of Systems. Bulletin of Mathematical Biophysics, 33 (3): 339–354.
  • 3 Baianu, I.C. 1987. Computer Models and Automata Theory in Biology and Medicine. (A Review). In: “Mathematical Models in Medicine.”,vol.7., M. Witten, Ed., Pergamon Press: New York, pp.1513-1577.
  • 4 I.C. Baianu.: Łukasiewicz-Topos Models of Neural Networks, Cell Genome and Interactome Nonlinear Dynamics). CERN Preprint EXT-2004-059. Health Physics and Radiation Effects (June 29, 2004).
  • 5 I. C. Baianu, J. F. Glazebrook, R. Brown and G. Georgescu.: Complex Nonlinear Biodynamics in Categories, Higher dimensional AlgebraPlanetmathPlanetmath and Łukasiewicz-Moisil Topos: Transformation of Neural, Genetic and Neoplastic Networks, Axiomathes, 16: 65–122(2006).
  • 6 Baianu, I.C.: 1970, Organismic Supercategories: II. On Multistable Systems. Bulletin of Mathematical Biophysics, 32: 539-561.
  • 7 Baianu, I.C. and D. Scripcariu: 1973, On Adjoint Dynamical Systems. The Bulletin of Mathematical Biophysics, 35(4), 475–486.
  • 8 Baianu, I.C.: 1973, Some Algebraic Properties of (M,R) – Systems. Bulletin of Mathematical Biophysics 35, 213-217.
  • 9 Baianu, I.C. and M. Marinescu: 1974, A Functorial Construction of (M,R)– Systems. Revue Roumaine de Mathematiques Pures et Appliquees 19: 388-391.
  • 10 Baianu, I.C.: 1977, A Logical Model of Genetic Activities in Łukasiewicz Algebras: The Non-linear Theory. Bulletin of Mathematical Biophysics, 39: 249-258.
  • 11 Baianu, I.C.: 1980, Natural Transformations of Organismic Structures. Bulletin of Mathematical Biophysics 42: 431-446
  • 12 Baianu, I. C.: 1987a, Computer Models and Automata Theory in Biology and Medicine., in M. Witten (ed.), Mathematical Models in Medicine, vol. 7., Pergamon Press, New York, 1513–1577; http://doe.cern.ch//archive/electronic/other/ext/ext-2004-072.pdfCERN Preprint No. EXT-2004-072 .
  • 13 Baianu, I.C.: 2004, Quantum Nano–Automata (QNA): Microphysical Measurements with Microphysical QNA Instruments, http://documents.cern.ch/cgi-bin/setlink?base=preprint&categ=ext&id=ext-2004-125CERN Preprint EXT–2004–125.
  • 14 Baianu, I. C., Glazebrook, J. F. and G. Georgescu: 2004, Categories of Quantum Automata and N-Valued Łukasiewicz Algebras in Relation to Dynamic Bionetworks, (M,R)–Systems and Their Higher Dimensional Algebra, http://www.ag.uiuc.edu/fs401/QAuto.pdfAbstract and Preprint of Report
  • 15 Baianu I. C., Brown R., Georgescu G. and J. F. Glazebrook: 2006, Complex Nonlinear Biodynamics in Categories, Higher Dimensional Algebra and Łukasiewicz–Moisil Topos: Transformations of Neuronal, Genetic and Neoplastic networks, Axiomathes 16 Nos. 1–2, 65–122.
  • 16 Georgescu, G. and C. Vraciu 1970. On the Characterization of Łukasiewicz Algebras., J Algebra, 16 (4), 486-495.
  • 17 BMB1: http://www.kli.ac.at/theorylab/Keyword/R/RelationalBio.htmlMathematical Biology reports
  • 18 McCullough, E. and M. Pitts.1945. Bull. Math. Biophys. 7, 112-145.
  • 19 MBR2: Eprint at cogprints.org/3674/ http://cogprints.org/3674/Mathematical Biology reports2.
Title quantum automata and computation
Canonical name QuantumAutomataAndComputation
Date of creation 2013-03-22 18:10:17
Last modified on 2013-03-22 18:10:17
Owner bci1 (20947)
Last modified by bci1 (20947)
Numerical id 172
Author bci1 (20947)
Entry type Topic
Classification msc 37B10
Classification msc 55U35
Classification msc 03D15
Classification msc 03D05
Synonym nano-automata
Related topic Automata
Related topic QuantumNanoAutomata
Related topic QuantumGroupoids2
Related topic GroupoidCDynamicalSystem
Related topic CategoryOfAutomata
Related topic CategoryOfQuantumAutomata
Related topic TopicEntryOnFoundationsOfMathematics
Related topic QuantumSpaceTimes
Related topic ETAS
Related topic QuantumCategory
Related topic TopicEntryOnAppliedMathematics
Related topic RichardFeynman
Related topic Exam
Defines quantum automaton
Defines quantum computers