Reordering method and hierarchies for quantum and classical ordered binary decision diagrams

DOI10.1007/978-3-319-58747-9_16zbMath1489.68061arXiv1703.00242OpenAlexW2594321785MaRDI QIDQ2399372

Aliya Khadieva, Kamil Khadiev

Publication date: 22 August 2017

Full work available at URL: https://arxiv.org/abs/1703.00242

zbMATH Keywords

computational complexityquantum computinghierarchybranching programsquantum modelsquantum vs classicalprobabilistic OBDDquantum OBDD

Mathematics Subject Classification ID

Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (10)

Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ New size hierarchies for two way automata ⋮ Application of dynamic evidential networks in reliability analysis of complex systems with epistemic uncertainty and multiple life distributions

Cites Work

• Unnamed Item
• Unnamed Item
• Extension of the hierarchy for \(k\)-OBDDs of small width
• Width hierarchy for \(k\)-OBDD of small width
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• Comparative complexity of quantum and classical OBDDs for total and partial functions
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• The power of nondeterminism and randomness for oblivious branching programs
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• On the computational power of probabilistic and quantum branching program
• Branching Programs and Binary Decision Diagrams
• Developments in Language Theory
• Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs

This page was built for publication: Reordering method and hierarchies for quantum and classical ordered binary decision diagrams