Geodesic
Quantum and classical nondeterministic OBDDs
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 166 (2024) no. 4, pp. 470-484

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

A model of nondeterministic ordered binary decision diagrams (NOBDDs) was analyzed. A method for proving a lower bound on the complexity of quantum NOBDDs was developed. Two functions were introduced: one function has linear complexity in the quantum NOBDD but constant complexity in the classical NOBDD, while the other function demonstrates the same complexity in both quantum and classical NOBDD models. The relationships among the complexity classes specific to the OBDD model were described.
Keywords: branching program, ordered binary decision diagram, OBDD, complexity, quantum algorithm, nondeterminism, hierarchy of complexity classes. 
@article{UZKU_2024_166_4_a1,
     author = {A. F. Gainutdinova},
     title = {Quantum and classical nondeterministic {OBDDs}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {470--484},
     publisher = {mathdoc},
     volume = {166},
     number = {4},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2024_166_4_a1/}
}
TY  - JOUR
AU  - A. F. Gainutdinova
TI  - Quantum and classical nondeterministic OBDDs
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2024
SP  - 470
EP  - 484
VL  - 166
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2024_166_4_a1/
LA  - ru
ID  - UZKU_2024_166_4_a1
ER  - 
%0 Journal Article
%A A. F. Gainutdinova
%T Quantum and classical nondeterministic OBDDs
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2024
%P 470-484
%V 166
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2024_166_4_a1/
%G ru
%F UZKU_2024_166_4_a1
A. F. Gainutdinova. Quantum and classical nondeterministic OBDDs. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 166 (2024) no. 4, pp. 470-484. http://geodesic.mathdoc.fr/item/UZKU_2024_166_4_a1/