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

DOI10.3103/S1066369X15110031zbMath1347.68137WikidataQ62039550 ScholiaQ62039550MaRDI QIDQ906414

A. F. Gainutdinova

Publication date: 21 January 2016

Published in: Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexityordered binary decision diagramspartial functionsquantum computationnondeterminismprobabilistic OBDDs

Mathematics Subject Classification ID

Quantum computation (81P68) Data structures (68P05) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (max. 100)

Unary probabilistic and quantum automata on promise problems ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Quantum versus classical online streaming algorithms with logarithmic size of 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

Cites Work

• Superiority of exact quantum automata for promise problems
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Quantum branching programs and space-bounded nonuniform quantum complexity
• On the computational power of probabilistic and quantum branching program
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Branching Programs and Binary Decision Diagrams
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Comparative complexity of quantum and classical OBDDs for total and partial functions