Parallelizing Quantum Circuit
Anne Broadbent
Université de Montréal, Canada
Abstract: Given a quantum circuit, an interesting question both from the theoretical and practical viewpoints is to ask whether is can be parallelized. On the theory side, this could lead to new complexity results, while on the practical side, it is highly desirable to have parallel implementations of quantum algorithms because of decoherence.
We present an algorithm for the parallelization of quantum circuits. That is, we give a method that given a circuit C_1 in the standard quantum circuit model, outputs another circuit C_2 that performs the same unitary as C_1, but of potentially smaller depth. Our method uses the tools of the measurement calculus for measurement-based quantum computing (MBQC): we translate the circuit C_1 to it's equivalent pattern, perform standardization and signal shifting and then revert to the final quantum circuit, C_2.
For any circuit, we show how to quantify how much decrease in depth our algorithm achieves and give the tradeoff in terms of auxiliary qubits. We also define the depth of a measurement pattern and give a depth characterization of patterns that relies on the notion of information flow. Finally, we show a separation between the quantum circuit model and the measurement-based model in terms of quantum depth complexity via the example of the parity problem: by exploiting the advantage of the classical control, the parity function can be computed in constant quantum depth in the MBQC, while it requires logarithmic quantum depth in the circuit model. Our results therefore confirm the advantages of MBQC over the circuit model.