Error-free affine, unitary, and probabilistic OBDDs

DOI10.1007/978-3-319-94631-3_15MaRDI QIDQ778003zbMATH OpenOpenAlexFDO

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

Publication date 30 June 2020

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

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)

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.

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

Cited in

(11)

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

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)