Abstract

We show that constant-depth polynomial-size quantum circuits with unbounded fan-out gates, called QNC^0_f circuits, are powerful. More concretely, we first show that there exists a QNC^0_f circuit for the OR function. This is an affirmative answer to the question of Hoyer and Spalek. Then, using this result, we show 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.