Projects per year
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 superpolynomial speedup when the dimension is fixed and the solution satisfies certain smoothness properties.
Original language  English 

Article number  032324 
Number of pages  16 
Journal  Physical Review A 
Volume  93 
Early online date  17 Mar 2016 
DOIs  
Publication status  Published  Mar 2016 
Keywords
 quantum algorithms
Fingerprint
Dive into the research topics of 'Quantum algorithms and the finite element method'. Together they form a unique fingerprint.Projects
 2 Finished

New insights in quantum algorithms and complexity
Montanaro, A. M. R. (Principal Investigator)
31/07/14 → 30/07/19
Project: Research

New insights in quantum algorithms and complexity
Montanaro, A. M. R. (Principal Investigator)
31/07/14 → 30/06/20
Project: Research