Пятница 26.10. Mika Hirvensalo (University of Turku): "Decidable and undecidable problems related to Measure-Once Quantum Automata with rational and irrational coefficients"
PDMI seminars
Тема: Decidable and undecidable problems related to Measure-Once Quantum Automata with rational and irrational coefficients
Место: ауд. 106
Время: 26.10.2018, 14:00
Докладчик: Mika Hirvensalo (University of Turku)
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.