2017/04/03 by Sergey Bravyi, David Gosset, Robert Koenig · 2 voices · 3 citations
Computer Science · Physics and Astronomy · #cs.CC #quant-ph
paper · pdf · doi:10.1126/science.aar3106
published as Science Vol. 362, Issue 6412, pp. 308-311 (2018)
arxiv created 2017/04/03 · arxiv published 2017/04/03 · arxiv updated 2018/10/23
We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.