Seminars

On the complexity of minimizing probabilistic and quantum automata PDF
Paulo Mateus, Departamento de Matemática, Instituto Superior Técnico

2/28/2014, 1:30pm, GHC 8102

Abstract

Several types of automata, such as probabilistic and quantum automata, require to work with real and complex numbers. For such automata the acceptance of an input is quantified with a probability. There are plenty of results in the literature addressing the complexity of checking the equivalence of these automata, that is, checking whether two automata accept all inputs with the same probability. On the other hand, the critical problem of finding the minimal automata equivalent to a given one has been left open (C. Moore, J.P. Crutchfield, Theoretical Computer Science 237 (2000) 275-306, p. 304, Problem 5). In this work, we reduce the minimization problem of probabilistic and quantum automata to finding a solution of a system of algebraic polynomial (in)equations. An EXPSPACE upper bound on the complexity of the minimization problem is derived by applying Renegar's algorithm. More specifically, we show that the state minimization of probabilistic automata, measure-once quantum automata, measure-many quantum automata, measure-once generalized quantum automata, and measure-many generalized quantum automata is decidable and in EXPSPACE. Finally, we also solve an open problem concerning minimal covering of stochastic sequential machines (A. Paz, Introduction to Probabilistic Automata, Academic Press, 1971, Page 43). Joint work with D. Qiu and L. Li published in Information and Computation.

Biography

Born in 1975 in Lisbon, studied at IST where he got his PhD in 2001 with a thesis on the interconnection of probabilistic systems. In the Fall semester of 2001-02, he was a postdoc at the Logic and Computation Group, Department of Mathematics, University of Pennsylvania. In 2006, he obtained his agregação (habilitation) in Mathematics from the Technical University of Lisbon. His habilitation thesis was awarded the Portuguese IBM Scientific Prize 2005. Currently, he is an Associate Professor at the Department of Mathematics of IST and coordinates the Security and Quantum Information Group at Instituto de Telecomunicações.

http://sqig.math.ist.utl.pt/paulo.mateus