Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations

Abstract

In this work we study the encoding of smooth, differentiable multivariate functions in quantum registers, using quantum computers or tensor-network representations. We show that a large family of distributions can be encoded as low-entanglement states of the quantum register. These states can be efficiently created in a quantum computer, but they are also efficiently stored, manipulated and probed using Matrix-Product States techniques. Inspired by this idea, we present eight quantum-inspired numerical analysis algorithms, that include Fourier sampling, interpolation, differentiation and integration of partial derivative equations. These algorithms combine classical ideas -- finite-differences, spectral methods -- with the efficient encoding of quantum registers, and well known algorithms, such as the Quantum Fourier Transform. {When these heuristic methods work}, they provide an exponential speed-up over other classical algorithms, such as Monte Carlo integration, finite-difference and fast Fourier transforms (FFT). But even when they don't, some of these algorithms can be translated back to a quantum computer to implement a similar task.

arXiv commentRevised version (v4), accepted for publication

References in corpus (29)

• The density-matrix renormalization group
• Efficient classical simulation of slightly entangled quantum computations
• 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
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Quantum computing for finance: overview and prospects
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Entropy scaling and simulability by Matrix Product States
• Efficient Simulation of Quantum Systems by Quantum Computers
• Sequential generation of entangled multi-qubit states
• Quantum speedup of Monte Carlo methods
• Variational quantum algorithms for nonlinear problems
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Quantum Risk Analysis
• Dynamical Correlation Functions using the Density Matrix Renormalization Group
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Creating superpositions that correspond to efficiently integrable probability distributions
• Image compression and entanglement
• Option Pricing using Quantum Computers
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum Algorithm for Simulating the Wave Equation
• Time evolution algorithms for Matrix Product States and DMRG
• Sequential Generation of Matrix-Product States in Cavity QED
• Quantum algorithm for non-homogeneous linear partial differential equations
• Multigrid Renormalization
• General-Purpose Parallel Simulator for Quantum Computing
• Matrix Product States Algorithms and Continuous Systems
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• TensorNetwork on TensorFlow: A Spin Chain Application Using Tree Tensor Networks

Cited by in corpus (41)

• Solving nonlinear differential equations with differentiable quantum circuits
• Filtering variational quantum algorithms for combinatorial optimization
• A Quantum Inspired Approach to Exploit Turbulence Structures
• Quantum Fourier Transform Has Small Entanglement
• Quantics Tensor Cross Interpolation for High-Resolution, Parsimonious Representations of Multivariate Functions in Physics and Beyond
• Quantum unary approach to option pricing
• Practical Quantum Computing: solving the wave equation using a quantum approach
• Efficient quantum amplitude encoding of polynomial functions
• Quantum algorithms for approximate function loading
• Complete quantum-inspired framework for computational fluid dynamics
• Quantum State Preparation of Normal Distributions using Matrix Product States
• A quantum-inspired method for solving the Vlasov-Poisson equations
• Gauging tensor networks with belief propagation
• Quantum integration of elementary particle processes
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Correlation length in random MPS and PEPS
• Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Quantum-Inspired Fluid Simulation of 2D Turbulence with GPU Acceleration
• Quantized tensor networks for solving the Vlasov-Maxwell equations
• Variational determination of multi-qubit geometrical entanglement in NISQ computers
• Efficient MPS representations and quantum circuits from the Fourier modes of classical image data
• Option pricing under stochastic volatility on a quantum computer
• Quantum state preparation for multivariate functions
• Efficient quantum interpolation of natural data
• Protocols for Trainable and Differentiable Quantum Generative Modelling
• Tensorized orbitals for computational chemistry
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
• Fully numerical Hartree-Fock calculations for atoms and small molecules with quantics tensor trains
• Survey on Computational Applications of Tensor Network Simulations
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Quantum Data Loading
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• Simulating Quantum Turbulence with Matrix Product States
• Pseudospectral method for solving PDEs using Matrix Product States
• The Software Landscape for the Density Matrix Renormalization Group
• Tensorization of neural networks for improved privacy and interpretability
• Time series generation for option pricing on quantum computers using tensor network
• The product structure of MPS-under-permutations
• Process Tensor Approaches to Non-Markovian Quantum Dynamics
• Quantum Encoding of Structured Data with Matrix Product States