Youngseok Kim, Andrew Eddins, et al.
APS March Meeting 2023
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.
Youngseok Kim, Andrew Eddins, et al.
APS March Meeting 2023
David Gosset, Jenish C. Mehta, et al.
Quantum
Dmitri Maslov, Jin-Sung Kim, et al.
APS March Meeting 2021
Sergey Bravyi, Guillaume Duclos-Cianci, et al.
Quantum Information and Computation