Abuzer Yakaryılmaz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Abuzer Yakaryılmaz has a total of 64 co-authors. Here are the top co-authors by number of shared publications:
- Ahmet Celal Cem Say
Boğaziçi University
18 shared publications A. C. Cem Say
Department of Computer Engineering, Bogazici University, Bebek 34342 Istanbul, Turkey
13 shared publications- Mika Hirvensalo
Department of Mathematics and Statistics, University of Turku, Turku, Finland
8 shared publications - Kamil Khadiev
Institute of Computational Mathematics and IT Kazan Federal University Kazan, Russia Zavoisky Physical-Technical Institute FRC Kazan Scientific Center of RAS Kazan,Russia
7 shared publications - Aida Gainutdinova
Kazan Federal University
6 shared publications - Etienne Moutot
I2M CNRS Aix-Marseille Université Marseille France
6 shared publications
Latest Publications
- 16 September 2026
- Published by Springer Nature in Natural Computing
- Vol. 25 (2) , 31
Two-way affine automata can verify every language
- 16 September 2026
- Published by Springer Nature in Natural Computing
- Vol. 25 (2) , 31
Two-way affine automata can verify every language
- Open Access
Benchmarking the Lights Out Problem on Real Quantum Hardware
We implement the Lights Out problem on a 2D grid and on Mobius ladder graphs and evaluate the performance of Grover's search on real quantum hardware. We use two instances using 9 and 16 qubits, and implement them on publicly available quantum hardware by IBM and IQM. Our experiments show improvements in IBM hardware between the Heron r1 and Heron r2 generations, highlighting progress in IBM hardware during the 2023-2024 period. The Lights Out circuits produced output distributions close to uniform on IQM devices. To diagnose device limitations, we additionally ran a small Grover SAT baseline, finding that IQM Garnet performs more reliably than other tested IQM devices. We also observed that QPUs of the same manufacturing revision can differ significantly in performance (a newer device is not guaranteed to be better), and that calibration has a significant impact on the performance of quantum devices, so the choice of device strongly depends on calibration quality.
Open AccessBenchmarking the Lights Out Problem on Real Quantum Hardware
We implement the Lights Out problem on a 2D grid and on Mobius ladder graphs and evaluate the performance of Grover's search on real quantum hardware. We use two instances using 9 and 16 qubits, and implement them on publicly available quantum hardware by IBM and IQM. Our experiments show improvements in IBM hardware between the Heron r1 and Heron r2 generations, highlighting progress in IBM hardware during the 2023-2024 period. The Lights Out circuits produced output distributions close to uniform on IQM devices. To diagnose device limitations, we additionally ran a small Grover SAT baseline, finding that IQM Garnet performs more reliably than other tested IQM devices. We also observed that QPUs of the same manufacturing revision can differ significantly in performance (a newer device is not guaranteed to be better), and that calibration has a significant impact on the performance of quantum devices, so the choice of device strongly depends on calibration quality.
- 5 December 2025
- Published by Springer Nature in Quantum Information Processing
- Vol. 24 (12) , 394
Classical and quantum Merlin–Arthur automata
- 5 December 2025
- Published by Springer Nature in Quantum Information Processing
- Vol. 24 (12) , 394
Classical and quantum Merlin–Arthur automata
- Open AccessQIP $ \subseteq $ AM(2QCFA)The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness).Open AccessQIP $ \subseteq $ AM(2QCFA)The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness).
- Open Access
Two-way affine automata can verify every language
When used as verifiers in Arthur-Merlin systems, two-way quantum finite automata can verify membership in all languages with bounded error with double-exponential expected running time, which cannot be achieved by their classical counterparts. We obtain the same result for affine automata with single-exponential expected time. We show that every binary (and r-ary) language is verified by some two-way affine finite automata verifiers by presenting two protocols: A weak verification protocol uses a single affine register and the input is read once; and, a strong verification protocol uses two affine registers. These results reflects the remarkable verification capabilities of affine finite automata.
Open AccessTwo-way affine automata can verify every language
When used as verifiers in Arthur-Merlin systems, two-way quantum finite automata can verify membership in all languages with bounded error with double-exponential expected running time, which cannot be achieved by their classical counterparts. We obtain the same result for affine automata with single-exponential expected time. We show that every binary (and r-ary) language is verified by some two-way affine finite automata verifiers by presenting two protocols: A weak verification protocol uses a single affine register and the input is read once; and, a strong verification protocol uses two affine registers. These results reflects the remarkable verification capabilities of affine finite automata.
- 18 June 2024
- Published by Springer Nature
- p. 163-177
A Representative Framework for Implementing Quantum Finite Automata on Real Devices
- 18 June 2024
- Published by Springer Nature
- p. 163-177
A Representative Framework for Implementing Quantum Finite Automata on Real Devices
- Open Access
- 3 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 386, 269-280
GAPs for Shallow Implementation of Quantum Finite Automata
Quantum fingerprinting is a technique that maps classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is quantum automata algorithms for MOD p = {a i•p | i ≥ 0} languages, where p is a prime number. However, implementing such an automaton on the current quantum hardware is not efficient. Quantum fingerprinting maps a word x ∈ {0, 1} n of length n to a state |ψ(x) of O(log n) qubits, and uses O(n) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to a large number of quantum operations. To make quantum fingerprinting practical, we should optimize the circuit for depth instead of width in contrast to the previous works. We propose explicit methods of quantum fingerprinting based on tools from additive combinatorics, such as generalized arithmetic progressions (GAPs), and prove that these methods provide circuit depth comparable to a probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods.
- 3 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 386, 269-280
Open AccessGAPs for Shallow Implementation of Quantum Finite Automata
Quantum fingerprinting is a technique that maps classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is quantum automata algorithms for MOD p = {a i•p | i ≥ 0} languages, where p is a prime number. However, implementing such an automaton on the current quantum hardware is not efficient. Quantum fingerprinting maps a word x ∈ {0, 1} n of length n to a state |ψ(x) of O(log n) qubits, and uses O(n) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to a large number of quantum operations. To make quantum fingerprinting practical, we should optimize the circuit for depth instead of width in contrast to the previous works. We propose explicit methods of quantum fingerprinting based on tools from additive combinatorics, such as generalized arithmetic progressions (GAPs), and prove that these methods provide circuit depth comparable to a probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods.
- Open Access
Framework for understanding quantum computing use cases from a multidisciplinary perspective and future research directions
Recently, there has been increasing awareness of the tremendous opportunities inherent in quantum computing (QC). Specifically, the speed and efficiency of QC will significantly impact the Internet of Things, cryptography, finance, and marketing. Accordingly, there has been increased QC research funding from national and regional governments and private firms. However, critical concerns regarding legal, political, and business-related policies germane to QC adoption exist. Since this is an emerging and highly technical domain, most of the existing studies focus heavily on the technical aspects of QC, but our study highlights its practical and social uses cases, which are needed for the increased interest of governments. Thus, this study offers a multidisciplinary review of QC, drawing on the expertise of scholars from a wide range of disciplines whose insights coalesce into a framework that simplifies the understanding of QC, identifies possible areas of market disruption and offer empirically based recommendations that are critical for forecasting, planning, and strategically positioning QCs for accelerated diffusion.
Open AccessFramework for understanding quantum computing use cases from a multidisciplinary perspective and future research directions
Recently, there has been increasing awareness of the tremendous opportunities inherent in quantum computing (QC). Specifically, the speed and efficiency of QC will significantly impact the Internet of Things, cryptography, finance, and marketing. Accordingly, there has been increased QC research funding from national and regional governments and private firms. However, critical concerns regarding legal, political, and business-related policies germane to QC adoption exist. Since this is an emerging and highly technical domain, most of the existing studies focus heavily on the technical aspects of QC, but our study highlights its practical and social uses cases, which are needed for the increased interest of governments. Thus, this study offers a multidisciplinary review of QC, drawing on the expertise of scholars from a wide range of disciplines whose insights coalesce into a framework that simplifies the understanding of QC, identifies possible areas of market disruption and offer empirically based recommendations that are critical for forecasting, planning, and strategically positioning QCs for accelerated diffusion.
- Open Access
Classical and quantum Merlin-Arthur automata
We introduce Merlin-Arthur (MA) automata as Merlin provides a single certificate and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We obtain several results using different certificate lengths. We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages but can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs recognize the same nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language.
Open AccessClassical and quantum Merlin-Arthur automata
We introduce Merlin-Arthur (MA) automata as Merlin provides a single certificate and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We obtain several results using different certificate lengths. We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages but can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs recognize the same nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language.
- Open Access
Real-valued affine automata compute beyond Turing machines
We show that bounded-error affine finite automata recognize uncountably many (and so some non-Turing recognizable) languages when using real-valued transitions.
Open AccessReal-valued affine automata compute beyond Turing machines
We show that bounded-error affine finite automata recognize uncountably many (and so some non-Turing recognizable) languages when using real-valued transitions.