How to simulate quantum measurement without computing marginals

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 $|⟨x|\psi ⟩{|}^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 ⟩=U|0^n⟩$ 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,\dots ,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$.

In v2 we have redone the tensor network circuit simulations using the "dynamic slicing" setting in CoTenGra as suggested to us by Johnnie Gray

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Hyper-optimized tensor network contraction
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Classical Simulation of Quantum Supremacy Circuits
• On measurement-based quantum computation with the toric code states
• On the simulation of quantum circuits
• Improved upper bounds on the stabilizer rank of magic states
• Simulating the Sycamore quantum supremacy circuits

Cited by in corpus (17)

• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Unbiasing Fermionic Auxiliary-Field Quantum Monte Carlo with Matrix Product State Trial Wavefunctions
• Improved simulation of quantum circuits dominated by free fermionic operations
• Zero and Finite Temperature Quantum Simulations Powered by Quantum Magic
• Experimental virtual distillation of entanglement and coherence
• Efficient distributed inner product estimation via Pauli sampling
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Approximately-symmetric neural networks for quantum spin liquids
• Classification of measurement-based quantum wire in stabilizer PEPS
• A rapidly mixing Markov chain from any gapped quantum many-body system
• BGLS: A Python Package for the Gate-by-Gate Sampling Algorithm to Simulate Quantum Circuits
• Optimal sampling of tensor networks targeting wave function's fast decaying tails
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques