See k-PBP for the definition of a classical branching program.
A quantum branching program is the natural quantum generalization: we have a quantum state in a Hilbert space of dimension k. Each step t consists of applying a unitary matrix U(t)(xi): that is, U(t) depends on a single bit xi of the input. (So these are the quantum analogues of so-called oblivious branching programs.) In the end we measure to decide whether to accept; there must be zero probability of error.
Defined in [AMP02], where it was also shown that NC1 is contained in 2-EQBP.
k-BQBP can be defined similarly.
See NC for definition.
[KV94] give a family of functions that is computable in NC1, but not efficiently learnable unless there exists an efficient algorithm for factoring Blum integers.
Was shown to equal 5-PBP [Bar89]. On the other hand, width 5 is necessary unless NC1 = ACC0 [BT88].
As an application of this result, NC1 can be simulated on a quantum computer with three qubits, one initialized to a pure state and the remaining two in the maximally mixed state [ASV00]. Surprisingly, [AMP02] showed that only a single qubit is needed to simulate NC1 - i.e. that NC1 is contained in 2-EQBP. (Complex amplitudes are needed for this result.)
Contains TC0.
NC1 contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].
UE*-uniform NC1 is equal to ALOGTIME [RUZ81].
A branching program is a directed acyclic graph with a designated start vertex. Each (non-sink) vertex is labeled by the name of an input bit, and has two outgoing edges, one of which is followed if that input bit is 0, the other if the bit is 1. A sink vertex can be either an 'accept' or a 'reject' vertex.
The size of the branching program is the number of vertices. The branching program has width k if the vertices can be sorted into levels, each with at most k vertices, such that each edge goes from a level to the one immediately after it.
Then k-PBP is the class of decision problems solvable by a family of polynomial-size, width-k branching programs. (A uniformity condition may also be imposed.)
k-PBP equals (nonuniform) NC1 for constant k at least 5 [Bar89]. On the other hand, 4-PBP is in ACC0 [BT88].
Contained in k-EQBP, as well as PBP.
See also BPd(P).