Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations
187
0
0.0
(
0
)
Added by
Juan Jose Garcia-Ripoll
Publication date
2019
fields
Physics
and research's language is
English
Authors
Juan Jose Garcia-Ripoll
Ask ChatGPT about the research
No Arabic 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 dont, some of these algorithms can be translated back to a quantum computer to implement a similar task.
rate research
Read More
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity $mathrm{poly}(1/epsilon)$, where $epsilon$ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be $mathrm{poly}(d, log(1/epsilon))$, where $d$ is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
A hybrid algorithm based on machine learning and quantum ensemble learning is proposed that is capable of finding a solution to a partial differential equation with good precision and favorable scaling in the required number of qubits. The classical part is composed by training several regressors (weak-learners), capable of solving a partial differential equation using machine learning. The quantum part consists of adapting the QBoost algorithm to solve regression problems. We have successfully applied our framework to solve the 1D Burgers equation with viscosity, showing that the quantum ensemble method really improves the solutions produced by weak-learners. We also implemented the algorithm on the D-Wave Systems, confirming the best performance of the quantum solution compared to the simulated annealing and exact solver methods, given the memory limitations of our classical computer used in the comparison.
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $Ax = b$, we show that there is a classical algorithm that outputs a data structure for $x$ allowing sampling and querying to the entries, where $x$ is such that $|x - A^{-1}b|leq epsilon |A^{-1}b|$. This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $widetilde{O}(kappa_F^6 kappa^2/epsilon^2 )$, where $kappa_F = |A|_F|A^{-1}|$ and $kappa = |A||A^{-1}|$. This improves the previous best algorithm [Gily{e}n, Song and Tang, arXiv:2009.07268] of complexity $widetilde{O}(kappa_F^6 kappa^6/epsilon^4)$. Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when $A$ is row sparse, this method already returns an approximate solution $x$ in time $widetilde{O}(kappa_F^2)$, while the best quantum algorithm known returns $ket{x}$ in time $widetilde{O}(kappa_F)$ when $A$ is stored in the QRAM data structure. As a result, assuming access to QRAM and if $A$ is row sparse, the speedup based on current quantum algorithms is quadratic.
Quantum computers are known to provide an exponential advantage over classical computers for the solution of linear differential equations in high-dimensional spaces. Here, we present a quantum algorithm for the solution of nonlinear differential equations. The quantum algorithm provides an exponential advantage over classical algorithms for solving nonlinear differential equations. Potential applications include the Navier-Stokes equation, plasma hydrodynamics, epidemiology, and more.
Fractional variational approach has gained much attention in recent years. There are famous fractional derivatives such as Caputo derivative, Riesz derivative and Riemann-Liouville derivative. Sever
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
