Skip to main content
SpringerLink
Log in

Comparative complexity of quantum and classical OBDDs for total and partial functions

  • Published:
Russian Mathematics Aims and scope Submit manuscript

Abstract

We consider a model of computation for discrete functions—Ordered Binary Decision Diagrams (OBDD).We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k.

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. Manin, Yu. I. Computable and Uncomputable (Sovetskoye Radio,Moscow, 1980) [in Russian].

    Google Scholar 

  2. Feynman, R. “Simulating Physics with Computers,” Intern. J. Theor.Phys. 21, No. 6, 7, 467–488 (1982).

    Article  MathSciNet  Google Scholar 

  3. Nielsen, M. A. and Chuang, I. L. Quantum Computation and Quantum Information (Cambridge University Press, 2000; Mir, Moscow, 2006).

    MATH  Google Scholar 

  4. Shor, P. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput. 26, No. 5, 1484–1509 (1997).

    Article  MathSciNet  MATH  Google Scholar 

  5. Grover, L. “A Fast Quantum Mechanical Algorithm for Database Search,” in Proceedings of 28th STOC (P. Philadelphia PA USA, 1996), Vol. 2996, pp. 212–219.

    MathSciNet  Google Scholar 

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

    Book  MATH  Google Scholar 

  7. Ablayev, F., Gainutdinova, A., Karpinski, M. “On Computational Power of Quantum Branching Programs,” in Proceedings of the 13th International Symposium ‘Fundamentals of Computation Theory’, FCT 2001, Riga, Latvia (Lecture Notes in Computer Science, 2001), Vol. 2138, pp. 59–70.

    MathSciNet  Google Scholar 

  8. Barrington, D. A. “Bounded-Width Polynomial Branching Programs Recognize Exactly Those Languages in NC 1,” J. Comput. and System Sciences 38, No. 1, 150–164 (1989).

    Article  MathSciNet  MATH  Google Scholar 

  9. Nakanishi, M., Hamaguchi, K., Kashiwabara, T. “OrderedQuantum Branching Programs are More Powerful than Ordered Probabilistic Branching Programs Under a Bounded-Width Restriction,” in Proceedings of the 6th Annual International Conference on Computing and Combinatorics COCOON’2000 (Lecture Notes in Computer Science, Springer-Verlag, 2000), Vol. 1858, pp. 467–476.

    MathSciNet  Google Scholar 

  10. Sauerhoff, M., Sieling, D. “Quantum Branching Programs and Space-Bounded Nonuniform Quantum Complexity,” Theoret. Comput. Sci. 334, Nos. 1–3, 177–225 (2005) (quant-ph/0403164).

    Article  MathSciNet  MATH  Google Scholar 

  11. Gainutdinova, A. F. “On Relative Complexity of Quantum and Classical Branching Programs,” Discrete Math. Appl. 12, No. 5, 515–526 (2002).

    MathSciNet  MATH  Google Scholar 

  12. Ablayev, F., Gainutdinova, A., Karpinski, M., Moore, C., Pollette, C. “On the Computational Power of Probabilistic and Quantum Branching Program,” Inform. and Comput. 203, No. 2, 145–162 (2005).

    Article  MathSciNet  MATH  Google Scholar 

  13. Sholomov, L. A. Fundamentals of Theory and Discrete Logical Computer Devices (Nauka, Moscow, 1980) [in Russian].

    Google Scholar 

  14. Ambainis, A. and Yakaryilmaz, A. “Superiority of Exact Quantum Automata for Promise Problems,” Inform. Process. Lett. 112, No. 7, 289–291 (2012).

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Kazan (Volga Region) Federal University, ul. Kremlyovskaya 18, Kazan, 420008, Russia

    A. F. Gainutdinova

Authors
  1. A. F. Gainutdinova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. F. Gainutdinova.

Additional information

Original Russian Text © A.F. Gainutdinova, 2015, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2015, No. 11, pp. 32–45.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gainutdinova, A.F. Comparative complexity of quantum and classical OBDDs for total and partial functions. Russ Math. 59, 26–35 (2015). https://doi.org/10.3103/S1066369X15110031

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.3103/S1066369X15110031

Keywords

Search

Navigation