Papers › How to simulate quantum measurement without computing marginals
How to simulate quantum measurement without computing marginals
Sergey Bravyi, David Gosset, Yinchen Liu
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 |⟨x|ψ⟩|². 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 |ψ⟩=U|0ⁿ⟩ 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,…,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 ψ.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections