Publications
Preprint · arXiv · March 21, 2017
Exact Affine OBDDs.
Rishat Ibrahimov, Kamil Ravilevich Khadiev, Abuzer Yakaryılmaz
Abstract
We introduce affine OBDD model and we show that exact affine OBDDs can be exponentially narrower than bounded-error quantum and classical OBDDs on some certain problems. Moreover, we consider Las-Vegas quantum and classical automata models and improve the previous gap between deterministic and probabilistic models by a factor of 2 and then follow the same gap for the known most restricted quantum model. Lastly, we follow an exponential gap between exact affine finite automata and Las-Vegas classical and quantum models.
Quantum Computing Algorithms and Architecturesemigroups and automata theoryComplexity and Algorithms in Graphsordered binary decision diagramsexact computationquantum automata
More by Kamil Khadiev
- Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering PatharXiv · 2026
- Quantum k-means based on Quantum Local Sensitive Hashing with Application to Irrigation Machine Sensors Data ClusteringIEEE International Conference on Smart Computing Workshops and Other Affiliated Events · 2026
- Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity GrapharXiv · 2026
- Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs Based on 1-Cover PathInternational Conference on Quantum Communications, Networking, and Computing · 2026 · Citations: 1