  Classical branching programs are studied to understand the space complexity
of computational problems. Prior to this work, Nakanishi and Ablayev had
separately defined two different quantum versions of branching programs that we
refer to as NQBP and AQBP. However, none of them, to our satisfaction, captures
the intuitive idea of being able to query different variables in superposition
in one step of a branching program traversal. Here we propose a quantum
branching program model, referred to as GQBP, with that ability. To motivate
our definition, we explicitly give examples of GQBP for n-bit Deutsch-Jozsa,
n-bit Parity, and 3-bit Majority with optimal lengths. We the show several
equivalences, namely, between GQBP and AQBP, GQBP and NQBP, and GQBP and query
complexities (using either oracle gates and a QRAM to query input bits). In way
this unifies the different results that we have for the two earlier branching
programs, and also connects them to query complexity. We hope that GQBP can be
used to prove space and space-time lower bounds for quantum solutions to
combinatorial problems.
