On the computational power of constant-depth quantum circuits with gates for addition

We investigate a class QNC⁰ (ADD) that is QNC⁰ with gates for addition of two binary numbers, where QNC⁰ is a class consisting of quantum operations computed by constant-depth quantum circuits. We show that QNC⁰(ADD) = QNC⁰(PAR), where QNC⁰(PAR) is QNC⁰ with Toffoli gates of arbitrary fan-in and gates for parity. Moreover, we show that QNC⁰(ADD) = QAC⁰(MUL) = QAC⁰(DIV), where QAC⁰(MUL) and QAC⁰(DIV) are QNC⁰ 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⁰ ⊆ QNC⁰(ADD); that is, the use of gates for addition increases the computational power of constant-depth quantum circuits. To prove QNC⁰ ⊆ QNC⁰(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⁰ ⊆ QNC⁰(ADD).