论文标题
量子和经典有序二进制决策图，重新排序方法和层次结构之间的指数分离
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
论文作者
论文摘要
在本文中，我们研究了量子订购的二进制决策图（$ obdd $）模型；对于“宽度”的复杂性，这是读取量子量子分支程序的受限制版本。众所周知，确定性和量子复杂性之间的最大差距是指数的。但是很少有这样的函数示例。如果我们在自然顺序上具有相似的界限，则我们提出了一种新技术（“重新排序”），用于用任意输入变量的OBDD证明下限和上限。使用此转换，我们构建了一个总函数$ req $，以便确定性$ obdd $的复杂性至少为$ 2^{ω（n / \ log n）} $，而量子$ obdd $的复杂性最多是$ o（n^2 / \ log n）$。它是线性宽度的$ obdd $ s代表的显式功能最大的差距。另一个函数（移动的平等函数）使我们能够获得差距$ 2^{ω（n）} $ vs $ o（n^2）$。 此外，我们证明了布尔功能复杂性类别的有限误差量子和概率$ obdd $宽度层次结构。此外，使用“重新排序”方法，我们扩展了一个多项式宽度的读取的层次结构，以读取-$ k $ -times订购的二进制决策图（$ k $ - $ obdd $），以$ k = o（n / \ log^3 n）$。我们证明了有界错误概率$ k $ -obdd $ obdd $ s多项式，超级单位和亚指定宽度的类似层次结构。 这项工作的扩展摘要是在国际上提出的 俄罗斯的计算机科学研讨会，2017年CSR，俄罗斯喀山，6月 8-12，2017
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(n^2/\log n)$. It is the biggest known gap for explicit functions not representable by $OBDD$s of a linear width. Another function(shifted equality function) allows us to obtain a gap $2^{Ω(n)}$ vs $O(n^2)$. 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 / \log^3 n)$. We prove a similar hierarchy for bounded error probabilistic $k$-$OBDD$s 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
