Optimal sampling of tensor networks targeting wave function's fast decaying tails

Abstract

We introduce an optimal strategy to sample quantum outcomes of local measurement strings for isometric tensor network states. Our method generates samples based on an exact cumulative bounding function, without prior knowledge, in the minimal amount of tensor network contractions. The algorithm avoids sample repetition and, thus, is efficient at sampling distribution with exponentially decaying tails. We illustrate the computational advantage provided by our optimal sampling method through various numerical examples, involving condensed matter, optimization problems, and quantum circuit scenarios. Theory predicts up to an exponential speedup reducing the scaling for sampling the space up to an accumulated unknown probability $\epsilon$ from $\mathcal{O}({\epsilon }^{-1})$ to $\mathcal{O}(\log ({\epsilon }^{-1}))$ for a decaying probability distribution. We confirm this in practice with over one order of magnitude speedup or multiple orders improvement in the error depending on the application. Our sampling strategy extends beyond local observables, e.g., to quantum magic.

17 pages, 11 figures. All figures are available on figshare at http://dx.doi.org/10.6084/m9.figshare.c.7023201. The code to reproduce the results is available on zenodo at http://dx.doi.org/10.5281/zenodo.10499025. The initial states to reproduce the results are available on zenodo at http://dx.doi.org/10.5281/zenodo.10511001. Updated version in Quantum's format for the publication

References in corpus (51)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• The density-matrix renormalization group
• Quantum computational advantage using photons
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Superconducting Qubits: Current State of Play
• Trapped-Ion Quantum Computing: Progress and Challenges
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Quantum information processing with superconducting circuits: a review
• Unifying time evolution and optimization with matrix product states
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Contextuality supplies the magic for quantum computation
• Classical simulation of quantum many-body systems with a tree tensor network
• From density-matrix renormalization group to matrix product states
• Rydberg atom quantum technologies
• Quantum simulation and computing with Rydberg-interacting qubits
• Algorithms for entanglement renormalization
• Minimally Entangled Typical Thermal State Algorithms
• Stabilizer Rényi entropy
• Simulation of two-dimensional quantum systems using a tree tensor network that exploits the entropic area law
• Unsupervised Generative Modeling Using Matrix Product States
• Simulating Strongly Correlated Quantum Systems with Tree Tensor Networks
• Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
• The iPEPS algorithm, improved: fast full update and gauge fixing
• A positive tensor network approach for simulating open quantum many-body systems
• Solving the sampling problem of the Sycamore quantum circuits
• Isometric Tensor Network States in Two Dimensions
• The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems
• Perfect Sampling with Unitary Tensor Networks
• Tensor Network Algorithms: a Route Map
• Multi-scale Entanglement Renormalization Ansatz in Two Dimensions: Quantum Ising Model
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Developments in the Tensor Network -- from Statistical Mechanics to Quantum Entanglement
• Unconstrained Tree Tensor Network: An adaptive gauge picture for enhanced performance
• A class of highly entangled many-body states that can be efficiently simulated
• One-dimensional many-body entangled open quantum systems with tensor network methods
• Simulation of time evolution with the MERA
• Quantum pixel representations and compression for $N$-dimensional images
• Quantum simulation with just-in-time compilation
• How to simulate quantum measurement without computing marginals
• A randomized measurement toolbox for an interacting Rydberg-atom quantum simulator
• Entanglement of formation of mixed many-body quantum states via Tree Tensor Operators
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Quantum Magic via Perfect Pauli Sampling of Matrix Product States
• Ab-initio tree-tensor-network digital twin for quantum computer benchmarking in 2D
• Tensor network to learn the wavefunction of data

Cited by in corpus (1)

• Quantum circuit compilation with quantum computers