()


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.

This talk is based on the following paper:
Y. Takahashi and S. Tani, Collapse of the hierarchy of constant-depth exact quantum circuits, Proc. of the 28th IEEE Conference on Computational Complexity, pp. 168-178, 2013, arXiv:quant-ph/1112.6063.