Width Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams with Repeated Test

2017/03/23 by Kamil Khadiev, Khadiev, Kamil, Rishat Ibrahimov +1
Computer Science · #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1703.07891

openalex publication_date 2017/03/23 · openalex created_date 2017/04/14 · openalex updated_date 2026/07/28

Abstract

We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-k-times Branching Programs or Ordered Binary Decision Diagrams with repeated test (k-QOBDD, k-NOBDD and k-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of k-OBDD.

Related

• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
• Quantum Ordered Binary Decision Diagrams with Repeated Tests
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
• Quantum Branching Programs and Space-Bounded Nonuniform Quantum Complexity