Very narrow quantum OBDDs and width hierarchies for classical OBDDs

被引：22

作者：

Ablayev F. ^{[1
]}

Gainutdinova A. ^{[1
]}

Khadiev K. ^{[1
]}

Yakaryılmaz A. ^{[2
]}

机构：

[1] Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies, Kazan (Volga Region) Federal University, Kremlevskaya ul. 18, Kazan, Tatrstan

[2] Hurriyet Mah. 1755. Sok. 8/5, Yenisehir, Mersin

来源：

Lobachevskii Journal of Mathematics | 2016年 / 37卷 / 6期

关键词：

nondeterminism; OBDD; partial functions; quantum computation; width hierarchy;

D O I：

10.1134/S199508021606007X

中图分类号：

学科分类号：

摘要：

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. © 2016, Pleiades Publishing, Ltd.

引用

页码：670 / 682

页数：12

共 27 条

[1]

Ablayev F., Randomization and nondeterminsm are incomparable for ordered read-once branching programs, Electronic Colloquium on Computational Complexity, 4, (1997)

[2]

Ablayev F., Gainutdinova A., Complexity of quantum uniform and nonuniform automata, Developments in Language Theory, LNCS, 3572, pp. 78-87, (2005)

[3]

Ablayev F., Gainutdinova A., Karpinski M., On computational power of quantum branching programs, FCT, LNCS, 2138, pp. 59-70, (2001)

[4]

Ablayev F.M., Gainutdinova A., Karpinski M., Moore C., Pollett C., On the computational power of probabilistic and quantum branching program, Information Computation, 203, 2, pp. 145-162, (2005)

[5]

Ablayev F.M., Karpinski M., On the power of randomized branching programs, ICALP, LNCS, 1099, pp. 348-356, (1996)

[6]

Ambainis A., Freivalds R., Proceedings of 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 332-341, (1998)

[7]

Ambainis A., Yakaryilmaz A., Superiority of exact quantum automata for promise problems, Information Processing Letters, 112, 7, pp. 289-291, (2012)

[8]

Ambainis A., Yakaryilmaz A., Automata and Quantum Computing, (2015)

[9]

Bertoni A., Carpentieri M., Analogies and differences between quantum and stochastic automata, Theoretical Computer Science, 262, 1-2, pp. 69-81, (2001)

[10]

Diamond H.G., Elementary methods in the study of the distribution of prime numbers, Bulletin of The AmericanMathematical Society, 7, pp. 553-589, (1982)

← 1 2 3 →