Skip to main content
SpringerLink
Log in

Very narrow quantum OBDDs and width hierarchies for classical OBDDs

  • Published:
Lobachevskii Journal of Mathematics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

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

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  3. F. Ablayev, A. Gainutdinova, and M. Karpinski, “On computational power of quantum branching programs,” FCT, LNCS 2138, 59–70 (2001).

    MathSciNet  MATH  Google Scholar 

  4. F. M. Ablayev, A. Gainutdinova, and M. Karpinski, Cristopher Moore, and Chris Pollett, “On the computational power of probabilistic and quantum branching program,” Information Computation 203 (2), 145–162 (2005).

    Article  MathSciNet  MATH  Google Scholar 

  5. F. M. Ablayev and M. Karpinski, “On the power of randomized branching programs,” ICALP, LNCS 1099, 348–356 (1996).

    MathSciNet  MATH  Google Scholar 

  6. A. Ambainis and R. Freivalds, in Proceedings of 39th Annual Symposium on Foundations of Computer Science, 1998 (IEEE Computer Society, 1998), pp. 332–341.

    Google Scholar 

  7. A. Ambainis and A. Yakaryilmaz, “Superiority of exact quantum automata for promise problems,” Information Processing Letters 112 (7), 289–291 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  8. A. Ambainis and A. Yakaryilmaz, Automata and Quantum Computing, arXiv:1507.01988 (2015).

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  11. R. Freivalds, “Fast probabilistic algorithms,” Mathematical Foundations of Computer Science, LNCS 74, 57–69 (1979).

    MathSciNet  MATH  Google Scholar 

  12. V. Geffert and A. Yakaryilmaz, “Classical automata on promise problems,” Discrete Mathematics & Theoretical Computer Science 17 (2), 126–137 (2015).

    MathSciNet  MATH  Google Scholar 

  13. J. Hromkovic and M. Sauerhoff, “Tradeoffs between nondeterminism and complexity for communication protocols and branching programs,” STACS, LNCS 1770, 145–156 (2000).

    MathSciNet  MATH  Google Scholar 

  14. J. Hromkovic and M. Sauerhoff, “The power of nondeterminism and randomness for oblivious branching programs,” Theory of Computing Systems 36 (2), 159–182 (2003).

    Article  MathSciNet  MATH  Google Scholar 

  15. K. Ireland and M. Rosen, A Classical Introduction toModern Number Theory, 2nd ed. Vol. 84 (Graduate Texts inMathematics, 1990).

    Google Scholar 

  16. J.G. Kemeny and J. L. Snell, FiniteMarkov Chains (Van Nostrand Company, INC, 1960).

    MATH  Google Scholar 

  17. K. Khadiev, “Width hierarchy for k-OBDD of small width,” Lobachevskii Journal of Mathematics 36 (2), 178–183 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  18. A. Kondacs and J. Watrous, “On the power of quantum finite state automata,” FOCS’97 Proceedings of the 38th Annual Symposium on Foundations of Computer Science (IEEE Computer Society, Washington, 1997), pp. 66–75.

    Chapter  Google Scholar 

  19. M. Nakanishi, K. Hamaguchi, and T. Kashiwabara, “Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction,” COCOON, LNCS 1858, 467–476 (2000).

    MathSciNet  MATH  Google Scholar 

  20. A. Paz, Introduction to Probabilistic Automata (Academic Press, New York, 1971).

    MATH  Google Scholar 

  21. J. Rashid and A. Yakaryilmaz, “Implications of quantum automata for contextuality,” Implementation and Application of Automata, LNCS 8587, 318–331 (2014).

    MathSciNet  MATH  Google Scholar 

  22. M. Sauerhoff and D. Sieling, “Quantum branching programs and space-bounded nonuniform quantum complexity,” Theoretical Computer Science 334 (1–3), 177–225 (2005).

    Article  MathSciNet  MATH  Google Scholar 

  23. J. Watrous, “On the complexity of simulating space-bounded quantum computations,” Computational Complexity 12 (1–2), 48–84 (2003).

    Article  MathSciNet  MATH  Google Scholar 

  24. J. Watrous, “Quantum computational complexity,” in Encyclopedia of Complexity and Systems Science, arXiv:0804.3401, 7174–7201 (2009).

    Chapter  Google Scholar 

  25. I. Wegener, Branching Programs and Binary Decision Diagrams (SIAM, 2000).

    Book  MATH  Google Scholar 

  26. A. Yakaryilmaz and A. C. Cem Say, “Languages recognized by nondeterministic quantum finite automata,” Quantum Information and Computation 10 (9–10), 747–770 (2010).

    MathSciNet  MATH  Google Scholar 

  27. A. Yakaryilmaz and A. C. Cem Say, “Unbounded-error quantum computation with small space bounds,” Information and Computation 279 (6), 873–892 (2011).

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    F. Ablayev, A. Gainutdinova & K. Khadiev

  2. Hurriyet Mah. 1755. Sok. 8/5, Yenisehir, Mersin, 33120, Turkey

    A. Yakaryılmaz

Authors
  1. F. Ablayev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Gainutdinova
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. K. Khadiev
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. A. Yakaryılmaz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to F. Ablayev.

Additional information

Submitted by M. M. Arslanov

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ablayev, F., Gainutdinova, A., Khadiev, K. et al. Very narrow quantum OBDDs and width hierarchies for classical OBDDs. Lobachevskii J Math 37, 670–682 (2016). https://doi.org/10.1134/S199508021606007X

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S199508021606007X

Keywords and phrases

Search

Navigation