3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits

Abstract

Although quantum computers are believed to be more powerful than classical ones, a convincing experimental demonstration of this fact remains elusive. Proposed schemes either rely on unproven complexity-theoretic hardness assumptions, and/or require universal, fault-tolerant scalable quantum computers to implement. This has motivated the study of restricted models of computation. Constant-depth quantum circuits are known to be more powerful than unbounded fan-in classical (AC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{AC}}}^{0}$$\end{document}-)circuits. Here we ask if this advantage persists in the presence of noise and under locality constraints. We present a computational problem for which every instance can be solved with near-certainty, despite noise, by a constant-depth quantum circuit with local operations in 3D. In contrast, every AC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{AC}}}^{0}$$\end{document}-circuit of size smaller than a certain (sub)exponential fails with near-certainty on a uniformly random instance. This constitutes a proposal with built-in fault-tolerance to experimentally observe the strongest known complexity-theoretic separation between classical and quantum computation. Finding cases in which imperfect quantum information processing can surpass classical protocols would allow to make use of NISQ-era devices without having to wait for full fault-tolerance. Here, the authors describe a search problem that can be solved efficiently by 3D-local constant-depth noisy quantum circuits but not by constant-depth unbounded fan-in classical circuits.