Error-free affine, unitary, and probabilistic OBDDs

DOI10.1007/978-3-319-94631-3_15zbMATH Open1435.68072arXiv1703.07184OpenAlexW2878465808MaRDI QIDQ778003FDOQ778003

Authors: Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz 

Publication date: 30 June 2020

Abstract: We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.

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

Recommendations

• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Nondeterministic unitary OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• scientific article; zbMATH DE number 2123421
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs

zbMATH Keywords

quantum computationsuccinctnessaffine modelsprobabilistic computationLas Vegas computationOBDDszero-error

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (11)

• Quantum online streaming algorithms with logarithmic memory
• Exact affine counter automata
• Exact Affine Counter Automata
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Nondeterministic unitary OBDDs
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Computational limitations of affine automata and generalized affine automata
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Quantum online algorithms with respect to space and advice complexity
• Improved constructions for succinct affine automata
• Affine automata verifiers

This page was built for publication: Error-free affine, unitary, and probabilistic OBDDs

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