We study the quantum complexity class QNC^0_f of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates (called QNC^0_f circuits). Our main result is that the quantum OR operation is in QNC^0_f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC^0 \subsetneq AC^0 \subsetneq TC^0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC^0_f = QAC^0_f = QTC^0_f. Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This implies the size difference between the QNC^0_f and QTC^0_f circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC^0_f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC^0_f oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC^0_f circuit with gates for the quantum Fourier transform.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok