Quantum Realization of the Finite Element Method
- URL: http://arxiv.org/abs/2403.19512v1
- Date: Thu, 28 Mar 2024 15:44:20 GMT
- Title: Quantum Realization of the Finite Element Method
- Authors: Matthias Deiml, Daniel Peterseim,
- Abstract summary: This paper presents a quantum algorithm for the solution of second-order linear elliptic partial differential equations discretized by $d$-linear finite elements.
A BPX preconditioner transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation.
We detail the design and implementation of a quantum circuit capable of executing our algorithm, and present simulator results that support the quantum feasibility of the finite element method.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by $d$-linear finite elements on Cartesian grids of a bounded $d$-dimensional domain. An essential step in the construction is a BPX preconditioner, which transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation. We provide a constructive proof demonstrating that our quantum algorithm can compute suitable functionals of the solution to a given tolerance $\texttt{tol}$ with a complexity linear in $\texttt{tol}^{-1}$ for a fixed dimension $d$, neglecting logarithmic terms. This complexity is proportional to that of its one-dimensional counterpart and improves previous quantum algorithms by a factor of order $\texttt{tol}^{-2}$. We also detail the design and implementation of a quantum circuit capable of executing our algorithm, and present simulator results that support the quantum feasibility of the finite element method in the near future, paving the way for quantum computing approaches to a wide range of PDE-related challenges.
Related papers
- A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA)
Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver.
By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
arXiv Detail & Related papers (2024-06-19T23:15:35Z) - Dense outputs from quantum simulations [5.295277584890625]
The quantum dense output problem is the process of evaluating time-accumulated observables from time-dependent quantum dynamics.
This problem arises frequently in applications such as quantum control and spectroscopic computation.
We present a range of algorithms designed to operate on both early and fully fault-tolerant quantum platforms.
arXiv Detail & Related papers (2023-07-26T18:16:51Z) - Fast quantum algorithm for differential equations [0.5895819801677125]
We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs.
Our algorithm generates a quantum state that enables extracting features of the solution.
arXiv Detail & Related papers (2023-06-20T18:01:07Z) - Double-bracket quantum algorithms for diagonalization [0.0]
This work proposes double-bracket iterations as a framework for obtaining diagonalizing quantum circuits.
Their implementation on a quantum computer consists of interlacing evolutions generated by the input Hamiltonian with diagonal evolutions which can be chosen variationally.
arXiv Detail & Related papers (2022-06-23T15:13:46Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$.
These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
arXiv Detail & Related papers (2022-05-11T14:29:39Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself.
We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
arXiv Detail & Related papers (2021-06-23T16:33:33Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - 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.