Rawad
Mezher
One of the main goals in the field of quantum computing is demonstrating a quantum-over-classical advantage (or simply quantum advantage). A main obstacle in the way of achieving this goal is noise, which can destroy whatever quantum advantage a quantum device offers. In this work, we present a new example of a sampling problem, defined by local measurements on efficiently preparable 2D graph states, which cannot be performed efficiently (in polynomial time) on a classical computer unless certain complexity-theoretic conjectures, which are widely believed to be true, turn out to be false, dubbed quantum speedup. Crucially, this sampling problem is robust against general types of noise, by virtue of quantum error correction, and also possesses desirable properties for experimental implementation such as low overhead, nearest neighbor interactions, regular structure, and fixed angle, non-adaptive Pauli measurements. Furthermore, our sampling problem can be viewed in the circuit model picture as a constant depth circuit acting on a polynomial number of ancilla qubits. From this perspective we present a quantum circuit with constant depth giving rise to a sampling problem which demonstrates a quantum speed-up, and which is robust to noise.
