On the computational power of constant-depth quantum circuits with gates for addition
Yasuhiro Takahashi, Y. Kawano, Masahiro Kitagawa · 2003
We investigate a class QNC/sup 0/ (ADD) that is QNC/sup 0/ with gates for addition of two binary numbers, where QNC/sup 0/ is a class consisting of quantum operations computed by constant-depth quantum circuits. We show that QNC/sup 0/(ADD) = QNC/sup 0/(PAR), where QNC/sup 0/(PAR) is QNC/sup 0/ with Toffoli gates of arbitrary fan-in and gates for parity. Moreover, we show that QNC/sup 0/(ADD) = QAC/sup 0/(MUL) = QAC/sup 0/(DIV), where QAC/sup 0/(MUL) and QAC/sup 0/(DIV) are QNC/sup 0/ with Toffoli gates of arbitrary fan-in and gates for multiplication and division respectively. In the classical setting, similar relationships do not hold. These relationships suggest that QNC/sup 0/ /spl subne/ QNC/sup 0/(ADD); that is, the use of gates for addition increases the computational power of constant-depth quantum circuits. To prove QNC/sup 0/ /spl subne/ QNC/sup 0/(ADD), we present a characterization of this relationship by the one-wayness of a permutation that is constructed explicitly. We conjecture that the permutation is one-way, which implies QNC/sup 0/ /spl subne/ QNC/sup 0/(ADD).