Quantum Relaxation for Linear Systems in Finite Element Analysis
- URL: http://arxiv.org/abs/2308.01377v4
- Date: Wed, 18 Oct 2023 20:16:01 GMT
- Title: Quantum Relaxation for Linear Systems in Finite Element Analysis
- Authors: Osama Muhammad Raisuddin, Suvranu De
- Abstract summary: We present Quantum Relaxation for Linear System (qRLS) as an iterative approach for gate-based quantum computers.
The well-conditioned system enables a practical iterative solution of finite element problems using the state-of-the-art Quantum Signal Processing (QSP) variant of QLSAs.
This represents an exponential efficiency gain, offering a new approach for iterative finite element problem-solving on quantum hardware.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Quantum linear system algorithms (QLSAs) for gate-based quantum computing can
provide exponential speedups for solving linear systems but face challenges
when applied to finite element problems due to the growth of the condition
number with problem size. Furthermore, QLSAs cannot use an approximate solution
or initial guess to output an improved solution. Here, we present Quantum
Relaxation for Linear System (qRLS), as an iterative approach for gate-based
quantum computers by embedding linear stationary iterations into a larger block
linear system. The condition number of the block linear system scales linearly
with the number of iterations independent of the size and condition number of
the original system. The well-conditioned system enables a practical iterative
solution of finite element problems using the state-of-the-art Quantum Signal
Processing (QSP) variant of QLSAs, for which we provide numerical results using
a quantum computer simulator. The iteration complexity demonstrates favorable
scaling relative to classical architectures, as the solution time is
independent of system size and requires O(log(N)) qubits. This represents an
exponential efficiency gain, offering a new approach for iterative finite
element problem-solving on quantum hardware.
Related papers
- Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
We present an original algorithmic procedure to solve the Quantum Linear System Problem (QLSP) on a digital quantum device.
The result is a quantum algorithm avoiding the need for large controlled unitaries, requiring a number of qubits that is logarithmic in the system size.
We apply this to a physical problem of practical relevance, by leveraging decomposition theorems from linear algebra to solve the discretized Laplace Equation in a 2D grid.
arXiv Detail & Related papers (2024-09-13T15:46:32Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - 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) - Quantum Multigrid Algorithm for Finite Element Problems [0.0]
Quantum linear system algorithms (QLSAs) can provide exponential speedups for the solution of linear systems.
We present a Quantum Multigrid Algorithm (qMG) for the iterative solution of linear systems.
arXiv Detail & Related papers (2024-04-11T04:08:24Z) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA.
We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension.
arXiv Detail & Related papers (2024-03-28T20:37:32Z) - Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems.
By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$.
We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
arXiv Detail & Related papers (2023-09-20T16:27:16Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL)
This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
arXiv Detail & Related papers (2022-10-23T11:58:05Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates.
We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions.
The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z) - 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)
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.