Very narrow quantum OBDDs and width hierarchies for classical OBDDs
Preprint
Abstract
We present several results on comparative complexity for different variants of OBDD models. - We present some results on comparative complexity of classical and quantum OBDDs. We consider a partial function depending on 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 nondeterminism can be more efficient than classical one. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width but any classical nondeterministic OBDD for this function needs non-constant width. - We also present new hierarchies on widths of deterministic and non-deterministic OBDDs. We focus both on small and large widths.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Implications of Quantum Automata for ContextualityLecture Notes in Computer Science, 2014
- Unbounded-error quantum computation with small space boundsInformation and Computation, 2011
- On the computational power of probabilistic and quantum branching programInformation and Computation, 2005
- On the complexity of simulating space-bounded quantum computationscomputational complexity, 2003
- The Power of Nondeterminism and Randomness for Oblivious Branching ProgramsTheory of Computing Systems, 2003
- On Computational Power of Quantum Branching Programs2001
- Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a Bounded-Width Restriction2000
- Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching ProgramsLecture Notes in Computer Science, 2000
- On the power of randomized branching programs1996
- Introduction to Probabilistic Automata1971