Quantum Advantage with Noisy Shallow Circuits in 3D

Sergey Bravyi, David Gosset, Robert Koenig, Marco Tomamichel

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

3 Zitate (Scopus)

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. 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.

OriginalspracheEnglisch
TitelProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
Herausgeber (Verlag)IEEE Computer Society
Seiten995-999
Seitenumfang5
ISBN (elektronisch)9781728149523
DOIs
PublikationsstatusVeröffentlicht - Nov. 2019
Extern publiziertJa
Veranstaltung60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, USA/Vereinigte Staaten
Dauer: 9 Nov. 201912 Nov. 2019

Publikationsreihe

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Band2019-November
ISSN (Print)0272-5428

Konferenz

Konferenz60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Land/GebietUSA/Vereinigte Staaten
OrtBaltimore
Zeitraum9/11/1912/11/19

Fingerprint

Untersuchen Sie die Forschungsthemen von „Quantum Advantage with Noisy Shallow Circuits in 3D“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren