Quantum Multigrid Algorithm for Finite Element Problems
- URL: http://arxiv.org/abs/2404.07466v1
- Date: Thu, 11 Apr 2024 04:08:24 GMT
- Title: Quantum Multigrid Algorithm for Finite Element Problems
- Authors: Osama Muhammad Raisuddin, Suvranu De,
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Quantum linear system algorithms (QLSAs) can provide exponential speedups for the solution of linear systems, but the growth of the condition number for finite element problems can eliminate the exponential speedup. QLSAs are also incapable of using an initial guess of a solution to improve upon it. To circumvent these issues, we present a Quantum Multigrid Algorithm (qMG) for the iterative solution of linear systems by applying the sequence of multigrid operations on a quantum state. Given an initial guess with error e_0, qMG can produce a vector encoding the entire sequence of multigrid iterates with the final iterate having a relative error e'=e/e_0, as a subspace of the final quantum state, with exponential advantage in O( poly log (N/e') ) time using O( poly log (N/e') ) qubits. Although extracting the final iterate from the sequence is efficient, extracting the sequence of iterates from the final quantum state can be inefficient. We provide an analysis of the complexity of the method along with numerical analysis.
Related papers
- 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) - Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Quantum Relaxation for Linear Systems in Finite Element Analysis [0.0]
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.
arXiv Detail & Related papers (2023-08-02T18:31:33Z) - Limitations for Quantum Algorithms to Solve Turbulent and Chaotic
Systems [0.5735035463793008]
We investigate the limitations of quantum computers for solving nonlinear dynamical systems.
We provide a significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector.
arXiv Detail & Related papers (2023-07-13T11:06:02Z) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
We show that some quantum SDO solvers provide speedups in the low-precision regime.
We exploit this fact to exponentially improve the dependence of their algorithm on precision.
A quantum implementation of our algorithm exhibits a worst case running time of $mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$.
arXiv Detail & Related papers (2023-01-10T23:12:05Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP)
We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
arXiv Detail & Related papers (2021-09-23T07:46:20Z) - 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) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.