2011/12/31 by Yasuhiro Takahashi, Seiichiro Tani · 3 citations
Computer Science · Physics and Astronomy · #cs.CC #quant-ph
published as Computational Complexity, Vol. 25 Issue 4, pp.849-881, 2016; Proceedings of the 28th IEEE Conference on Computational Complexity (CCC 2013), pp.168-178, 2013 · 19 pages, 4 figures; v2: one theorem added, title changed, text substantially rewritten
arxiv created 2012/09/04 · arxiv updated 2016/11/07
We study the quantum complexity class QNC0f of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates (called QNC0f circuits). Our main result is that the quantum OR operation is in QNC0f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC0 \subsetneq AC0 \subsetneq TC0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC0f = QAC0f = QTC0f. 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 QNC0f and QTC0f circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC0f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC0f oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC0f circuit with gates for the quantum Fourier transform.