__
Revision #1 to TR08-085 | 25th January 2010 13:05
__
#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

**Abstract:**
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.

**Changes to previous version:**
1. Generalized Equality section removed;

2. Permutation Matrix Test section added to the paper;

3. HSP section extended with extra details;

4. Minor typos corrected.

__
TR08-085 | 19th June 2008 00:00
__

#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

**Abstract:**
We consider Generalized Equality, the Hidden Subgroup,

and 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.