Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

We study the quantum complexity class QNC⁰_f of quantum operations implement able exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC⁰_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⁰ ⊊ AC⁰ ⊊ TC⁰, our result with Hoyer and Spalek´s one implies the collapse of the hierarchy of the corresponding quantum ones: QNC⁰_f = QAC⁰_f = QTC⁰_f. Then, we show that there exists a constant-depth sub quadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC⁰_f and QTC⁰_f circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC⁰_f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC⁰_f oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC⁰_f circuit with gates for the quantum Fourier transform.