Quantum vs. classical algorithms for solving the heat equation
- URL: http://arxiv.org/abs/2004.06516v2
- Date: Thu, 18 Jun 2020 10:39:45 GMT
- Title: Quantum vs. classical algorithms for solving the heat equation
- Authors: Noah Linden, Ashley Montanaro and Changpeng Shao
- Abstract summary: Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially.
Here we consider a prototypical PDE - the heat equation in a rectangular region - and compare in detail the complexities of ten classical and quantum algorithms for solving it.
- Score: 0.04297070083645048
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computers are predicted to outperform classical ones for solving
partial differential equations, perhaps exponentially. Here we consider a
prototypical PDE - the heat equation in a rectangular region - and compare in
detail the complexities of ten classical and quantum algorithms for solving it,
in the sense of approximately computing the amount of heat in a given region.
We find that, for spatial dimension $d \ge 2$, there is an at most quadratic
quantum speedup using an approach based on applying amplitude estimation to an
accelerated classical random walk. However, an alternative approach based on a
quantum algorithm for linear equations is never faster than the best classical
algorithms.
Related papers
- Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt.
We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
arXiv Detail & Related papers (2024-07-10T14:08:58Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - Nonlinear dynamics as a ground-state solution on quantum computers [39.58317527488534]
We present variational quantum algorithms (VQAs) that encode both space and time in qubit registers.
The spacetime encoding enables us to obtain the entire time evolution from a single ground-state computation.
arXiv Detail & Related papers (2024-03-25T14:06:18Z) - A quantum advantage over classical for local max cut [48.02822142773719]
Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs.
Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
arXiv Detail & Related papers (2023-04-17T16:42:05Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation.
We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
arXiv Detail & Related papers (2021-08-18T09:26:17Z) - Quantum-accelerated multilevel Monte Carlo methods for stochastic
differential equations in mathematical finance [1.128265591164748]
We study quantum algorithms for differential equations (SDEs)
We provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting.
We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance.
arXiv Detail & Related papers (2020-12-11T12:34:55Z) - Simpler (classical) and faster (quantum) algorithms for Gibbs partition
functions [4.2698418800007865]
We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature.
We modify the classical algorithm of vStefankovivc, Vempala and Vigoda to improve its sample complexity.
We quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei.
arXiv Detail & Related papers (2020-09-23T17:27:28Z) - Quantum Assisted Eigensolver [0.0]
We propose a hybrid quantum-classical algorithm for approxing the ground state and ground state energy of a Hamiltonian.
The output from the quantum part of the algorithm is utilized as input for the classical computer.
arXiv Detail & Related papers (2020-09-23T08:33:18Z) - High-precision quantum algorithms for partial differential equations [1.4050836886292872]
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm.
We develop quantum algorithms based on adaptive-order finite difference methods and spectral methods.
Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound.
arXiv Detail & Related papers (2020-02-18T20:32:45Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.