This article is cited in 1 paper

Quantum and classical nondeterministic OBDDs

A. F. Gainutdinova

Kazan Federal University, Kazan, 420008 Russia

Abstract: 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.

UDC: 519.71

Received: 05.07.2024
Accepted: 10.10.2024

DOI: 10.26907/2541-7746.2024.4.470-484