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

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
  arXiv  Detail & Related papers  (2024-09-06T03:32:02Z)
• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator. Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel. Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
  arXiv  Detail & Related papers  (2024-09-05T17:56:51Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• 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)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix. The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  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)
• 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)
• 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)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• 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.