Quantum-classical transition in analog quantum supremacy subject to Markovian decoherence

Instantaneous Quantum Polynomial time circuits are a promising way to demonstrate quantum supremacy. We study the robustness of quantum supremacy in an analog Hamiltonian version of such circuits in the presence of a Markovian environment whose noise operators commute with the system Hamiltonian. We find a transition from a regime of quantum supremacy to classical simulability that occurs at a finite critical decoherence rate, that depends on the system size.