### Špalek, Robert

Faculty of Mathematics and Physics, Charles University

Prague, Czech Republic, 2002

## Space Complexity of Quantum Computation

### Abstract

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.

### Table of Contents

**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