A new quantum model of computation --- a sequence of Quantum Branching Programs --- is proposed and its consistence is verified. Its power, properties, special forms and relations to existing computational models are investigated. Both nonuniform and uniform variants are considered. It is shown that QBP's are equivalent to Quantum Turing Machines and that they are at least as powerful as their deterministic and probabilistic variant. Every QBP can be converted to its most regular form (layered, oblivious, 2-bounded degree, with connected graph) at low cost. Almost all these simulations preserve the space complexity and enlarge the time complexity at most polynomially, moreover we prove that the target sequence obtained by converting a uniform source sequence is also uniform --- we describe an explicit construction machine for each conversion. It is demonstrated that width-2 oblivious QBP's recognise $NC_1$ languages in polynomial time.
1. Preliminaries 1.1. Syllabus 1.2. Contribution of the thesis 1.3. Notation 2. Branching Programs 2.1. Deterministic Branching Programs 2.2. Nonuniform and uniform sequences of BP's 2.3. Probabilistic Branching Programs 2.4. Complexity classes 2.5. Reversible computation 3. Quantum Computation 3.1. Intrinsics of Quantum Computation 3.1.1. State space 3.1.2. Evolution 3.1.3. Measurement 3.2. Quantum Circuits 3.3. Quantum Turing Machines 3.3.1. Definition 3.3.2. Transition function 3.3.3. Quantum behaviour and language acceptance 3.3.4. Complexity measures and complexity classes 3.3.5. Nonuniform version 3.3.6. Special forms of QTM's 4. Quantum Networks 4.1. Raw Quantum Networks 4.1.1. Definition 4.1.2. Consistency of the model 4.1.3. Uniform sequences of QN's 4.1.4. Language acceptance and complexity measures 4.2. Special forms of QN's 4.2.1. Layered QN's 4.2.2. Oblivious QN's 4.2.3. Bounded degree QN's 5. Equivalence of QN's and QTM's 5.1. Converting a QTM to a sequence of QN's 5.2. Converting a sequence of QN's to a QTM 6. Converting QN's to special forms 6.1. Layered layout 6.2. Oblivious layout 6.3. Bounded degree layout 6.4. Connected graphs 6.5. Conclusion 7. Achieving reversibility 7.1. The back-tracking method 7.2. The infinite iteration method 7.3. The Pebble game method 7.4. Tradeoffs between the methods 8. Space bounded Quantum Computation 8.1. Recognising $NC_1$ languages by 5-PBP's 8.2. $NC_1$ is contained in 2-EqQBP
