## Parallel quantum computing: from theory to practice

##### Abstract

The term quantum parallelism is commonly used to refer to a property of quantum
computations where an algorithm can act simultaneously on a superposition of states.
However, this is not the only aspect of parallelism in quantum computing. Analogously
to the classical computing model, every algorithm consists of elementary quantum
operations and the application of them could be parallelised itself. This kind of
parallelism is explored in this thesis in the one way quantum computing (1WQC) and
the quantum circuit model.
In the quantum circuit model we explore arithmetic circuits and circuit complexity
theory. Two new arithmetic circuits for quantum computers are introduced in this
work: an adder and a multiply-adder. The latter is especially interesting because its
depth (i.e. the number of parallel steps required to finish the computation) is smaller
than for any known classical circuit when applied sequentially. From the complexity
theoretical perspective we concentrate on the classes QAC0 and QAC0[2], the quantum
counterparts of AC0 and AC0[2]. The class AC0 comprises of constant depth circuits with
unbounded fan-in AND and OR gates and AC0[2] is obtained when unbounded fan-in
parity gates are added to AC0 circuits. We prove that QAC0 circuits with two layers
of multi-qubit gates cannot compute parity exactly. This is a step towards proving
QAC0 6= QAC0[2], a relation known to hold for AC0 and AC0[2].
In 1WQC, computation is done through measurements on an entangled state called
the resource state. Two well known parallelisation methods exist in this model:
signal shifting and finding the maximally delayed general flow. The first one uses
the measurement calculus formalism to rewrite the dependencies of an existing
computation, whereas the second technique exploits the geometry of the resource state
to find the optimal ordering of measurements. We prove that the aforementioned
methods result in same depth computations when the input and output sizes are equal.
Through showing this equivalence we reveal new properties of 1WQC computations
and design a new algorithm for the above mentioned parallelisations.