Dr. Miklos Bartha

Department of Computer Science

Memorial University of Newfoundland* ** Quantum Turing Automata*

Department of Computer Science

Thursday, February 16, 2012, 1:00 p.m., Room EN-2022

Abstract

A quantum Turing machine is commonly perceived as the straightforward probabilistic generalization of the classical concept. The transition function assigns "probabilities with complex amplitudes" to each possible transition of the machine, so that the sum of squared norms of these amplitudes equals 1. The operation of the machine is then explained in terms of configurations in a step-by-step manner, exactly in the way this is done for classical Turing machines.

In this talk we take a structural approach to the analysis of Turing computations, and define a denotational style semantics for quantum Turing machines as hardware devices. By this we mean that the changing of the tape contents caused by the entire computation process is captured directly as a complex linear (unitary) operator, rather than just one step of this process. At the same time the rigid topological structure of Turing machines as a linear array of tape cells is replaced by a flexible graph structure, giving rise to the concept of Turing automata and Turing graph machines.

Formally, a directed Turing automaton is a monoidal automaton (also known as circuit) over the strongly compact closed category of finite dimensional Hilbert spaces. By the help of the Moore-Penrose generalized inverse we introduce a new additive trace operation on the restriction of this category to isometries, which trace is then carried over to the monoidal category of directed quantum Turing automata. Using the Joyal-Street-Verity Int construction, the resulting traced monoidal category is further transformed into the indexed monoidal algebra of undirected quantum Turing automata