On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions
Farid Mansurovich Ablayev, Airat Khasianov, Alexander Vasiliev · 2008
We consider the Hidden Subgroup, and Equality-related problems in the context of quantum Ordered Binary Decision Diagrams. For the decision versions of considered problems we show polynomial upper bounds in terms of quantum OBDD width. We apply a new modification of the fingerprinting technique and present the algorithms in circuit notation. Our algorithms require at most logarithmic number of qubits. 1