2023/09/15 by Bravyi, Sergey, Gosset, David, Liu, Yinchen · 6 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2309.08405
An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime n^O(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime n^O(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √(n).