On the Minimization of the Depth of Certain Quantum Circuits

摘要

A logic circuit model of computation is a basis for every kind of computation, and also takes an important role in quantum computation. Thus it is important to study how to evaluate logical functions on quantum circuits, and how to minimize or simplify those circuits. In this paper, we show how to automatically generate a certain kind of shallowest quantum logic circuit without ancilla, a so-called f-C-NOT gate, which computes an arbitrary logic function, f. We will, moreover, show that this circuit generation problem is strongly related to the minimization problem for a logical expression, called ESOP. Furthermore, in order to generate the desired f-C-NOT gates as quickly as possible, we reduce this minimization problem to an NP-complete problem, the so-called Maximum Clique. Having applied this reduction, we can use a well-known, efficient program to solve the Maximum Clique problem to generate a desired f-C-NOT gate with the minimum depth.