Quantum advantage with shallow circuits

Sergey Bravyi; David Gosset; Robert Koenig

doi:10.48550/arxiv.1704.00690

Papers

qcr:2608.91543.1

Quantum advantage with shallow circuits

arXiv

Sergey Bravyi, David Gosset, Robert Koenig

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.

10.48550/arxiv.1704.00690

Published 2017

Uploaded 2 weeks ago

7

Views

View Publication

Citing this entry? Use this QCR ID

Uploaded by

QCR Librarian

Join the Discussion

Comments (0)

No comments yet. Be the first to share your thoughts!

Indexed by QCR Librarian

This entry was created automatically from publicly available records. QCR links to public sources and only stores repository content where the license permits redistribution.

Claim this entry →