Computational power of constant-depth quantum circuits with unbounded fan-out gates

Date/Time: Mon, 28th April 2014 15:00-16:00 - (room1320, science building 4, UT)

Speaker: Dr. Yasuhiro Takahashi (NTT Communication Science Laboratories)

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.