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

DOI10.3103/S1066369X15110031MaRDI QIDQ906414zbMATH OpenWikidataFDO

Authors A. F. Gainutdinova

Publication date 21 January 2016

Published in Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexitynondeterminismquantum computationordered binary decision diagramspartial functionsprobabilistic OBDDs

Mathematics Subject Classification ID

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

Recommendations

• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
• Nondeterministic unitary OBDDs
• Developments in Language Theory

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1696662 (Why is no real title available?)
• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• scientific article; zbMATH DE number 3872639 (Why is no real title available?)
• scientific article; zbMATH DE number 3737613 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1839432 (Why is no real title available?)
• scientific article; zbMATH DE number 2095528 (Why is no real title available?)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Branching Programs and Binary Decision Diagrams
• On the computational power of probabilistic and quantum branching program
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Superiority of exact quantum automata for promise problems

Cited in

(9)

• Quantum online streaming algorithms with logarithmic memory
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Developments in Language Theory
• Quantum versus classical online streaming algorithms with logarithmic size of memory
• Quantum online algorithms with respect to space and advice complexity
• Two-way and one-way quantum and classical automata with advice for online minimization problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906414)