Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Авторлар: Ablayev F.1, Gainutdinova A.1, Khadiev K.1, Yakaryılmaz A.2
-
Мекемелер:
- Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
- Hurriyet Mah. 1755. Sok. 8/5, Yenisehir
- Шығарылым: Том 37, № 6 (2016)
- Беттер: 670-682
- Бөлім: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198367
- DOI: https://doi.org/10.1134/S199508021606007X
- ID: 198367
Дәйексөз келтіру
Аннотация
In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels.
• We present results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2k+1.
• We consider quantum and classical nondeterminism. We show that quantum nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width.
• We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.
Негізгі сөздер
Авторлар туралы
F. Ablayev
Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
Хат алмасуға жауапты Автор.
Email: fablayev@gmail.com
Ресей, Kremlevskaya ul. 18, Kazan, Tatrstan, 420008
A. Gainutdinova
Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
Email: fablayev@gmail.com
Ресей, Kremlevskaya ul. 18, Kazan, Tatrstan, 420008
K. Khadiev
Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
Email: fablayev@gmail.com
Ресей, Kremlevskaya ul. 18, Kazan, Tatrstan, 420008
A. Yakaryılmaz
Hurriyet Mah. 1755. Sok. 8/5, Yenisehir
Email: fablayev@gmail.com
Түркия, Mersin, 33120