94 citations · 176 across the 26 of their papers we have counts for
4 papers · 1 filter
Magic coins are useful for small-space quantum machines
A. C. Cem Say, Abuzer Yakaryilmaz
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to…
Alternating, private alternating, and quantum alternating realtime automata
Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt +2
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-count…
Quantum finite automata: A modern introduction
A. C. Cem Say, Abuzer Yakaryilmaz
We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum comp…
Debates with small transparent quantum verifiers
Abuzer Yakaryilmaz, A. C. Cem Say, H. Gökalp Demirci
We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We…