94 citations · 376 across the 55 of their papers we have counts for
10 papers · 1 filter
Proving the power of postselection
Abuzer Yakaryilmaz, A. C. Cem Say
It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time…
Tight bounds for the space complexity of nonregular language recognition by real-time machines
Abuzer Yakaryilmaz, A. C. Cem Say
We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternatin…
Quantum counter automata
A. C. Cem Say, Abuzer Yakaryilmaz
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirma…
Probabilistic and quantum finite automata with postselection
Abuzer Yakaryilmaz, A. C. Cem Say
We prove that endowing a real-time probabilistic or quantum computer with the ability of postselection increases its computational power. For this purpose, we provide a new model o…
Classical and quantum computation with small space bounds (PhD thesis)
Abuzer Yakaryilmaz
In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, a…
Superiority of one-way and realtime quantum machines and new directions
Abuzer Yakaryilmaz
In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QF…
Finite state verifiers with constant randomness
Cem Say, Abuzer Yakaryilmaz
We give a new characterization of as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state m…
Computation with narrow CTCs
A. C. Cem Say, Abuzer Yakaryilmaz
We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capac…
NP has log-space verifiers with fixed-size public quantum registers
Abuzer Yakaryilmaz, A. C. Cem Say
In classical Arthur-Merlin games, the class of languages whose membership proofs can be verified by Arthur using logarithmic space (AM(log-space)) coincides with the class P \cite{…
Superiority of exact quantum automata for promise problems
Andris Ambainis, Abuzer Yakaryilmaz
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in…