2022/04/22 by Kamil Khadiev, Khadiev, Kamil, Aliya Khadieva +3 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Machine Learning and Algorithms #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2204.10671
In this paper, we study quantum Ordered Binary Decision Diagrams(OBDD) model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a new technique ("reordering") for proving lower bounds and upper bounds for OBDD with an arbitrary order of input variables if we have similar bounds for the natural order. Using this transformation, we construct a total function REQ such that the deterministic OBDD complexity of it is at least 2Ω(n / log n), and the quantum OBDD complexity of it is at most O(n2/log n). It is the biggest known gap for explicit functions not representable by OBDDs of a linear width. Another function(shifted equality function) allows us to obtain a gap 2Ω(n) vs O(n2). Moreover, we prove the bounded error quantum and probabilistic OBDD width hierarchies for complexity classes of Boolean functions. Additionally, using "reordering" method we extend a hierarchy for read-k-times Ordered Binary Decision Diagrams (k-OBDD) of polynomial width, for k = o(n / log3 n). We prove a similar hierarchy for bounded error probabilistic k-OBDDs of polynomial, superpolynomial and subexponential width. The extended abstract of this work was presented on International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8 -- 12, 2017