6533b82bfe1ef96bd128e289

RESEARCH PRODUCT

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

Kamil KhadievRishat Ibrahimov

subject

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsFOS: Physical sciencesComputational Complexity (cs.CC)Quantum Physics (quant-ph)

description

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.

yearjournalcountryeditionlanguage
2017-03-22
https://dx.doi.org/10.48550/arxiv.1703.07891