Parallelization of Quantum Circuits with Ancillae

摘要

In this paper, parallelization methods for quantum circuits are studied, where parallelization of quantum circuits means to reconstruct a given quantum circuit to one which realizes the same quantum computation with a smaller depth, and it is based on using additional bits, called ancillae, each of which is initialized to be in a certain state. We propose parallelization methods in terms of the number of available ancillae, for three types of quantum circuits. The proposed parallelization methods are more general than previous one in the sense that the methods are applicable when the number of available ancillae is fixed arbitrarily. As consequences, for the three types of n-bit quantum circuits, we show new upper bounds of the number of ancillae for parallelizing to logarithmic depth, which are 1/log n of previous upper bounds.