Publications
Preprint · arXiv · March 21, 2017
Zero-Error Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Ravilevich Khadiev, Krišjānis Prūsis, Jevgēnijs Vihrovs, Abuzer Yakaryılmaz
Abstract
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.
semigroups and automata theoryComplexity and Algorithms in GraphsFormal Methods in Verificationordered binary decision diagramsLas Vegas algorithmsautomata
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