Amsterdam, The Netherlands, 2002

We propose a new circuit class **QNCf0** -- constant-depth quantum circuits
with unbounded fan-out. It differs from **QNC0** by including the quantum
fan-out gate, and from **QACC0** by excluding the Toffoli (AND) gate. Hence
* QNC0 \subseteq QNCf0 \subseteq QACC0*.

We describe an efficient method for performing commuting gates in parallel.
Using this method, the Quantum Fourier Transform, and a shallow circuit for the
increment operator, we construct approximate circuits for the Counting and
linear Threshold gate. Let us assume the weights of the source qubits in the
linear combination are bounded by a polynomial *p(n)*. Then both circuits
have depth *O(log log n + log log (1/epsilon))* and size *O(log n (n +
log (1/epsilon)))* with error bounded by *epsilon*.

Furthermore, we construct exact and shallower circuits for these gates at the
cost of bigger space complexity. They all have depth *O(log* n)* in the
model **QNCf**. We first define a linear Rank gate (testing a linear
equation on source qubits) and construct an exact circuit of size *O(n log
n)* for it. Using this gate, we construct circuits for the Counting and
linear Threshold gate of size *O(n^2 p(n) log n)*.

Finally, we state several interesting related results, e.g. the efficiency of
performing arithmetical operations in **QNCf**, or Shor's factoring algorithm.

1. Preliminaries1.1. Contents of the thesis 1.2. Contribution of the thesis 1.3. Notation2. Quantum Computation2.1. Intrinsics of Quantum Computation 2.1.1. State space 2.1.2. Evolution 2.1.3. Measurement 2.2. Models of Quantum Computation 2.2.1. Quantum Circuits 2.2.2. Quantum Turing Machines 2.2.3. Quantum Branching Programs 2.3. Approximations3. Quantum Circuits with fan-out3.1. Survey of existing circuit classes 3.2. Motivation 3.3. Quantum fan-out operation 3.4. Quantum parity operation 3.5. Generalised quantum operations4. Parallelisation method4.1. Parallelising commuting operations 4.2. Application to one qubit operators5. Quantum Fourier Transform5.1. Definition and decomposition 5.2. Basic narrow circuit 5.3. Decomposition of QFT 5.4. Parallelising QFS 5.5. Implementing QFP 5.6. Precision of the approximate QFT6. Increment operation6.1. Classical circuit 6.2. Quantum circuit7. Interesting shallow circuits7.1. Approximative Counting and Threshold gate 7.2. Approximative Rank and Toffoli gate 7.3. Exact Rank and Toffoli gate 7.4. Exact Threshold and Counting gate 7.5. Arithmetics8. Lower and upper bounds8.1. Arithmetics using threshold circuits 8.2. Factoring problem 8.3. Relations of the quantum circuit classes 8.4. Open problems