Laboratory of Mathematical Logic at PDMI

Пятница, 26 октября, ауд. 106. Начало в 14:00.

Докладчик: Mika Hirvensalo (University of Turku).

Тема: Decidable and undecidable problems related to Measure-Once Quantum Automata with rational and irrational coefficients.

Abstract

Measure-Once Quantum Automata, also known as Moore-Crutchfield QFA, are the most straightforward quantum variants of probabilistic finite automata: They are obtained by replacing the stochastic matrices by unitary ones, and L1-norm by L2-norm. It turns out that the expressive power of MO-QFA is weaker than that of PFA, but sometimes the MO-QFA may be exponentially more compact than their classical counterparts.

It may appear surprising that determining the emptiness of a strict cut-point languages for MO-QFA is decidable, whereas the same question for PFA is undecidable. On the other hand, removing the attribute "strict" yields an undecidable problem for MO-QFA again. In this talk, I will demonstrate that the ambiguity problem of the acceptance probability for MO-QFA is undecidable, if some radical irrational amplitudes are allowed. It turns out that, conditional to Bombieri-Lang conjecture (or to a speculation by Don Zagier), the problem remains undecidable even if only rational amplitudes are allowed.