As larger and larger prototypes of quantum computers are being developed, one of the most exciting challenges in the theory of quantum computing is to find computational problems that can be solved by an intermediate-scale noisy quantum computer. QSI's latest contribution to this area is a joint work with researchers from IBM, the University of Waterloo and TU Munich.
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.
Reference: Sergey Bravyi, David Gosset, Robert Koenig, Marco Tomamichel, "Quantum advantage with noisy shallow circuits in 3D", available at https://arxiv.org/abs/1904.01502
