IQI Weekly Seminar

Abstract: We give a probabilistic time classical algorithm to weakly simulate noisy quantum circuits. We assume l1 sampling of the columns of the quantum channels in the circuit w.r.t. some basis. The algorithm is efficient whenever the circuits consist overwhelmingly of quantum channels whose columns lie in a l1 norm ball of small radius, one of the signatures of sparsity. Moreover, we extend this algorithm to simulate continuous-time quantum channels with sparse generators. This algorithm immediately induces a quantity similar to the negativity that can be used to upper bound the classical complexity of simulating a given noisy quantum circuit. Inspired by that, we give a randomized benchmarking protocol to estimate this quantity under some assumptions on the structure of the noise affecting the circuit. Finally, as an easy application of these methods, we show bounds on how much local noise certain quantum circuits can withstand before becoming classically simulable and show that circuits consisting of simulations of constant sparsity Hamiltonians for times logarithmic in the number of qubits can be simulated classically in quasi-polynomial time. This immediately implies that some quantum algorithms can be dequantized for certain parameter ranges.