Shravan Shravan

The classical simulation of noisy-intermediate scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise. For example, it has been shown that the output distributions of random quantum circuits and arbitrary IQP circuits undergoing depolarizing noise can be simulated in polynomial time with low error. However, it is currently unknown if such results can be extended to circuits undergoing non-unital noise. In this work, we answer this question partially by providing a classical algorithm to simulate the output distributions of arbitrary IQP circuits of depth d = Ω(log(n)) undergoing amplitude damping noise with a runtime O(dpoly(n/ϵ)).

The problems on which quantum computers will demonstrably outperform classical computers remains surprisingly unclear. Quantum simulation is one area where an exponential advantage is expected, yet establishing this advantage is not straightforward. Here, we propose a scheme for verifying quantum simulations of nonequilibrium dynamics at scale, based on a special class of quantum many-body scars known as stabilizer scars. Our approach leverages the structure of these states to guarantee efficient fidelity estimation, and our analysis connects the fidelity of classically simulable scar-subspace states to that of typical, non-simulable states.