How to simulate quantum measurement without computing marginals

We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state ψ in the standard basis, that is, sampling a bit string x from the probability distribution |langle x|ψrangle|². Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. First we consider the case where |ψrangle=U|0^nrangle is the output state of an m-gate quantum circuit U. We propose an exact sampling algorithm which involves computing O(m) amplitudes of n-qubit states generated by subcircuits of U spanned by the first t=1,2,ldots,m gates. We show that our algorithm can significantly accelerate quantum circuit simulations based on tensor network contraction methods or low-rank stabilizer decompositions. As another striking consequence we obtain an efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph, generalizing a previous algorithm which was known to be efficient only under restrictive topological constraints on the ordering of single-qubit measurements. Second, we consider the case in which ψ is the unique ground state of a local Hamiltonian with a spectral gap that is lower bounded by an inverse polynomial function of n. We prove that a simple Metropolis-Hastings Markov Chain mixes rapidly to the desired probability distribution provided that ψ obeys a certain technical condition, which we show is satisfied for all sign-problem free Hamiltonians. This gives a sampling algorithm which involves computing poly(n) amplitudes of ψ.