Quantum algorithms and the finite element method
arXiv:1512.05903 · doi:10.1103/PhysRevA.93.032324
Abstract
The finite element method is used to approximately solve boundary value problems for differential equations. The method discretises the parameter space and finds an approximate solution by solving a large system of linear equations. Here we investigate the extent to which the finite element method can be accelerated using an efficient quantum algorithm for solving linear equations. We consider the representative general question of approximately computing a linear functional of the solution to a boundary value problem, and compare the quantum algorithm's theoretical performance with that of a standard classical algorithm -- the conjugate gradient method. Prior work had claimed that the quantum algorithm could be exponentially faster, but did not determine the overall classical and quantum runtimes required to achieve a predetermined solution accuracy. Taking this into account, we find that the quantum algorithm can achieve a polynomial speedup, the extent of which grows with the dimension of the partial differential equation. In addition, we give evidence that no improvement of the quantum algorithm could lead to a super-polynomial speedup when the dimension is fixed and the solution satisfies certain smoothness properties.
16 pages, 2 figures
References in corpus (6)
- Quantum algorithm for solving linear systems of equations
- Creating superpositions that correspond to efficiently integrable probability distributions
- Quantum algorithm and circuit design solving the Poisson equation
- A quantum algorithm to solve nonlinear differential equations
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
- Quantum Networks for Generating Arbitrary Quantum States
Cited by in corpus (85)
- Quantum Computing in the NISQ era and beyond
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Variational quantum algorithms for nonlinear problems
- Quantum computing for finance
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Solving nonlinear differential equations with differentiable quantum circuits
- High-precision quantum algorithms for partial differential equations
- Quantum Algorithm for Simulating the Wave Equation
- On the impact of quantum computing technology on future developments in high-performance scientific computing
- Variational Quantum algorithm for Poisson equation
- Solving Systems of Linear Equations with a Superconducting Quantum Processor
- Biology and medicine in the landscape of quantum advantages
- Quantum algorithm for non-homogeneous linear partial differential equations
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
- Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
- Asymptotic Quantum Algorithm for the Toeplitz Systems
- On applications of quantum computing to plasma simulations
- Quantum Computing: Towards Industry Reference Problems
- Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
- Quantum unary approach to option pricing
- Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
- Quantum simulation of partial differential equations via Schrodingerisation
- Hybrid quantum algorithms for flow problems
- Quantum phase estimation for a class of generalized eigenvalue problems
- Quantum Variational Solving of Nonlinear and Multi-Dimensional Partial Differential Equations
- Application of a variational hybrid quantum-classical algorithm to heat conduction equation
- Quantum Computing for Fusion Energy Science Applications
- A novel design update framework for topology optimization with quantum annealing: Application to truss and continuum structures
- Two quantum algorithms for solving the one-dimensional advection-diffusion equation
- Box algorithm for the solution of differential equations on a quantum annealer
- Nonlinear dynamics as a ground-state solution on quantum computers
- Quantum Circulant Preconditioner for Linear System of Equations
- A Performance Study of Variational Quantum Algorithms for Solving the Poisson Equation on a Quantum Computer
- Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
- Quantum algorithm for time-dependent differential equations using Dyson series
- Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
- Quantum Computing and Preconditioners for Hydrological Linear Systems
- Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
- Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
- Depth analysis of variational quantum algorithms for heat equation
- Efficient Hamiltonian Simulation for Solving Option Price Dynamics
- Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
- On efficient quantum block encoding of pseudo-differential operators
- A hybrid classical-quantum approach to solve the heat equation using quantum annealers
- Quantum algorithms for scientific computing
- Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
- Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
- A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
- A quantum active learning algorithm for sampling against adversarial attacks
- A quantum annealing-sequential quadratic programming assisted finite element simulation for non-linear and history-dependent mechanical problems
- Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
- Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
- Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
- Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
- Quantum vs. classical algorithms for solving the heat equation
- Representation of the Fermionic Boundary Operator
- Tight Bound for Estimating Expectation Values from a System of Linear Equations
- Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
- Quantum Algorithms for Geologic Fracture Networks
- Variational Quantum Algorithms for Differential Equations on a Noisy Quantum Computer
- Coherence dynamics in quantum algorithm for linear systems of equations
- Explicit block encodings of boundary value problems for many-body elliptic operators
- Quantum Machine Learning and its Supremacy in High Energy Physics
- Quantum Newton's method for solving system of nonlinear algebraic equations
- An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
- Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
- Pricing multi-asset derivatives by finite difference method on a quantum computer
- Alternatives to a nonhomogeneous partial differential equation quantum algorithm
- Calculating response functions of coupled oscillators using quantum phase estimation
- Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
- Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
- Quantum circuits for partial differential equations in Fourier space
- On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
- Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
- Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
- Quantum Realization of the Finite Element Method
- Quantum oracles for the finite element method
- Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
- Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
- Fully Quantum Algorithm for the 1-dimensional linear Lattice Boltzmann Method
- Quantum Simulation-Based Optimization for Cooling System Design
- QAFE: Quantum accelerated multiscale finite element analysis
- Vortex Detection from Quantum Data
- Fully Quantum Lattice Gas Automata Building Blocks for Computational Basis State Encodings