Ariel Shlosberg

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/ϵ)).

In this work, we study the sample complexity of two variants of product testing when restricted to single-copy measurements. In particular, we consider both bipartite product testing (i.e., does there exist at least one non-trivial cut across which the state is product) and multipartite product testing (i.e., is the state fully product across every cut). For the first variant, we prove an exponential lower bound on the sample complexity of any algorithm for this task which utilizes only single-copy measurements. When comparing this with known efficient algorithms that utilize multi-copy measurements, this establishes an exponential separation for this and several related entanglement learning tasks. For the second variant, we prove another sample lower bound that establishes a separation between single- and multi-copy strategies. To obtain our results, we prove a crucial technical lemma that gives a lower bound on the overlap between tensor products of permutation operators acting on subsystems of states that themselves carry a tensor structure. Finally, we provide an algorithm for multipartite product testing using only single-copy, local measurements, and we highlight several interesting open questions arising from this work.