Related papers: How to simulate quantum measurement without computing marginals

How to simulate quantum measurement without computing marginals

URL: http://arxiv.org/abs/2112.08499v2
Date: Thu, 6 Jan 2022 21:34:39 GMT
Title: How to simulate quantum measurement without computing marginals
Authors: Sergey Bravyi, David Gosset, Yinchen Liu
Abstract summary: We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
Score: 3.222802562733787
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We describe and analyze algorithms for classically simulating measurement of an $n$-qubit quantum state $\psi$ in the standard basis, that is, sampling a bit string $x$ from the probability distribution $|\langle x|\psi\rangle|^2$. 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 $|\psi\rangle=U|0^n\rangle$ 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 $\psi$ 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 $\psi$ obeys a certain technical condition, which we show is satisfied for all sign-problem free Hamiltonians. This gives a sampling algorithm which involves computing $\mathrm{poly}(n)$ amplitudes of $\psi$.