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.

http://arxiv.org/abs/1704.00690http://arxiv.org/pdf/1704.00690.pdf

A provable separation between analogous quantum and classical circuit classes!

I would like to publicly thank the authors for using the term "advantage" instead of the tainted word "supremacy" that makes me cringe every time I hear it.

Also, great result!

Edited Apr 04 2017 13:16 UTC by Steve Flammia

Is it okay to be a quantum supremacist? I thought I was, but maybe if it's "tainted" I should reconsider.

On a more serious note... a question for somebody who has read (or written) the paper. If the computation is performed on Poly(n) qubits, and all of them are relevant, and you are only allowed bounded fan-in... how do you read out the answer without using classical postprocessing of depth log(n) to concentrate the relevant information into one place?

(I'm totally happy for this to be a naive question; educate me?)

You are completely correct that in order to check whether a give output is "correct" for the input, we would require an additional log-depth classical circuit, but this is not how the problem is defined. In particular, for each input there is a set of "accepting" outputs, and we only need to guarantee that our circuit outputs an answer from this "accepting" set. With a constant depth quantum circuit, we can guarantee that the output is from this set, while any $o(\log n)$ depth classical circuit can only output from this set with probability 7/8.

Thanks Zak, that's exactly right-- for each instance there is a set of possible solutions. Like in the Bernstein-Vazirani problem, a solution is a bit string. It can't just be a single bit since then we would have the problem you describe, Robin.

Zak, David: thanks! So (I think) this is a relation problem, not a decision problem (or even a partial function). Which is fine -- I'm happier with relation problems than with sampling problems, and the quantum part of Shor's algorithm is solving a relation problem, which is a pretty good pedigree. And this is clearly a very very cool result.

I do wish I had a better intuition for the practical implications -- by which I mean "How plausibly could this be leveraged to prove polynomial separations for decision problems?" Solving the relation problem at the heart of Shor immediately gives you an extension to the function/decision problem of factoring by tacking on the GCD algorithm. But situations where the circuit depth is dwarfed by the resources required to perform serial I/O on the input and/or output give me a headache!

Anyway, thanks very much for the clear explanations.