Prior work has shown that there exists a relation problem which can be solved
with certainty by a constant-depth quantum circuit composed of geometrically
local gates in two dimensions, but cannot be solved with high probability by
any classical constant depth circuit composed of bounded fan-in gates. Here we
provide two extensions of this result. Firstly, we show that a separation in
computational power persists even when the constant-depth quantum circuit is
restricted to geometrically local gates in one dimension. The corresponding
quantum algorithm is the simplest we know of which achieves a quantum advantage
of this type. It may also be more practical for future implementations. Our
second, main result, is that a separation persists even if the shallow quantum
circuit is corrupted by noise. We construct a relation problem which can be
solved with near certainty using a noisy constant-depth quantum circuit
composed of geometrically local gates in three dimensions, provided the noise
rate is below a certain constant threshold value. On the other hand, the
problem cannot be solved with high probability by a noise-free classical
circuit of constant depth. A key component of the proof is a quantum
error-correcting code which admits constant-depth logical Clifford gates and
single-shot logical state preparation. We show that the surface code meets
these criteria. To this end, we provide a protocol for single-shot logical
state preparation in the surface code which may be of independent interest.
Description
Quantum advantage with noisy shallow circuits in 3D
%0 Generic
%1 bravyi2019quantum
%A Bravyi, Sergey
%A Gosset, David
%A Koenig, Robert
%A Tomamichel, Marco
%D 2019
%K quantum
%T Quantum advantage with noisy shallow circuits in 3D
%U http://arxiv.org/abs/1904.01502
%X Prior work has shown that there exists a relation problem which can be solved
with certainty by a constant-depth quantum circuit composed of geometrically
local gates in two dimensions, but cannot be solved with high probability by
any classical constant depth circuit composed of bounded fan-in gates. Here we
provide two extensions of this result. Firstly, we show that a separation in
computational power persists even when the constant-depth quantum circuit is
restricted to geometrically local gates in one dimension. The corresponding
quantum algorithm is the simplest we know of which achieves a quantum advantage
of this type. It may also be more practical for future implementations. Our
second, main result, is that a separation persists even if the shallow quantum
circuit is corrupted by noise. We construct a relation problem which can be
solved with near certainty using a noisy constant-depth quantum circuit
composed of geometrically local gates in three dimensions, provided the noise
rate is below a certain constant threshold value. On the other hand, the
problem cannot be solved with high probability by a noise-free classical
circuit of constant depth. A key component of the proof is a quantum
error-correcting code which admits constant-depth logical Clifford gates and
single-shot logical state preparation. We show that the surface code meets
these criteria. To this end, we provide a protocol for single-shot logical
state preparation in the surface code which may be of independent interest.
@preprint{bravyi2019quantum,
abstract = {Prior work has shown that there exists a relation problem which can be solved
with certainty by a constant-depth quantum circuit composed of geometrically
local gates in two dimensions, but cannot be solved with high probability by
any classical constant depth circuit composed of bounded fan-in gates. Here we
provide two extensions of this result. Firstly, we show that a separation in
computational power persists even when the constant-depth quantum circuit is
restricted to geometrically local gates in one dimension. The corresponding
quantum algorithm is the simplest we know of which achieves a quantum advantage
of this type. It may also be more practical for future implementations. Our
second, main result, is that a separation persists even if the shallow quantum
circuit is corrupted by noise. We construct a relation problem which can be
solved with near certainty using a noisy constant-depth quantum circuit
composed of geometrically local gates in three dimensions, provided the noise
rate is below a certain constant threshold value. On the other hand, the
problem cannot be solved with high probability by a noise-free classical
circuit of constant depth. A key component of the proof is a quantum
error-correcting code which admits constant-depth logical Clifford gates and
single-shot logical state preparation. We show that the surface code meets
these criteria. To this end, we provide a protocol for single-shot logical
state preparation in the surface code which may be of independent interest.},
added-at = {2019-04-03T18:49:17.000+0200},
author = {Bravyi, Sergey and Gosset, David and Koenig, Robert and Tomamichel, Marco},
biburl = {https://www.bibsonomy.org/bibtex/2c18687bf4c32acc66d2d25ef07f9df10/bobsutor},
description = {Quantum advantage with noisy shallow circuits in 3D},
interhash = {73229be46cd53146d1bfb66bf3d413af},
intrahash = {c18687bf4c32acc66d2d25ef07f9df10},
keywords = {quantum},
note = {cite arxiv:1904.01502},
timestamp = {2019-04-03T18:49:17.000+0200},
title = {Quantum advantage with noisy shallow circuits in 3D},
url = {http://arxiv.org/abs/1904.01502},
year = 2019
}