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. Preliminaries 1.1. Contents of the thesis 1.2. Contribution of the thesis 1.3. Notation 2. Quantum Computation 2.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. Approximations 3. Quantum Circuits with fan-out 3.1. Survey of existing circuit classes 3.2. Motivation 3.3. Quantum fan-out operation 3.4. Quantum parity operation 3.5. Generalised quantum operations 4. Parallelisation method 4.1. Parallelising commuting operations 4.2. Application to one qubit operators 5. Quantum Fourier Transform 5.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 QFT 6. Increment operation 6.1. Classical circuit 6.2. Quantum circuit 7. Interesting shallow circuits 7.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. Arithmetics 8. Lower and upper bounds 8.1. Arithmetics using threshold circuits 8.2. Factoring problem 8.3. Relations of the quantum circuit classes 8.4. Open problems
