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.