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