Parallelization of Quantum Circuits with Ancillae

Hideaki ABE  Shao Chin SUNG  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.2   pp.255-262
Publication Date: 2003/02/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Quantum Computation
quantum computation,  quantum circuit,  parallelization,  ancillae,  

Full Text: PDF>>
Buy this Article

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.