Convergence rate of algorithms for solving linear equations by quantum annealing

• URL: http://arxiv.org/abs/2310.15441v1
• Date: Tue, 24 Oct 2023 01:23:00 GMT
• Title: Convergence rate of algorithms for solving linear equations by quantum annealing
• Authors: V. Shalgin, S. Tikhomirov
• Abstract summary: We consider various iterative algorithms for solving the linear equation $ax=b$ using a quantum computer. The application of this approach to algorithms using both an infinite number of qubits and a small number of qubits is discussed.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider various iterative algorithms for solving the linear equation $ax=b$ using a quantum computer operating on the principle of quantum annealing. Assuming that the computer's output is described by the Boltzmann distribution, it is shown under which conditions the equation-solving algorithms converge, and an estimate of their convergence rate is provided. The application of this approach to algorithms using both an infinite number of qubits and a small number of qubits is discussed.

Related papers

• A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
  We propose a quantum algorithm for solving the linear advection-diffusion equation by employing a new approximate probabilistic imaginary-time evolution (PITE) operator. We construct the explicit quantum circuit for realizing the imaginary-time evolution of the Hamiltonian coming from the advection-diffusion equation. Our algorithm gives comparable result to the Harrow-Hassidim-Lloyd (HHL) algorithm with similar gate complexity, while we need much less ancillary qubits.
  arXiv  Detail & Related papers  (2024-09-27T08:56:21Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Depth analysis of variational quantum algorithms for heat equation [0.0]
  We consider three approaches to solve the heat equation on a quantum computer. An exponential number of Pauli products in the Hamiltonian decomposition does not allow for the quantum speed up to be achieved. The ansatz tree approach exploits an explicit form of the matrix what makes it possible to achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2022-12-23T14:46:33Z)
• Quantum Algorithm For Estimating Eigenvalue [0.0]
  We provide a quantum algorithm for estimating the largest eigenvalue in magnitude of a given Hermitian matrix. Our quantum procedure can also yield exponential speedup compared to classical algorithms that solve the same problem.
  arXiv  Detail & Related papers  (2022-11-11T13:02:07Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Variational Quantum Evolution Equation Solver [0.0]
  Variational quantum algorithms offer a promising new paradigm for solving partial differential equations on near-term quantum computers. We propose a variational quantum algorithm for solving a general evolution equation through implicit time-stepping of the Laplacian operator. We present a semi-implicit scheme for solving systems of evolution equations with non-linear terms, such as the reaction-diffusion and the incompressible Navier-Stokes equations.
  arXiv  Detail & Related papers  (2022-04-06T16:02:11Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods [1.802439717192088]
  We explore utilizing quantum computers for the purpose of solving differential equations. We devise and simulate corresponding digital quantum circuits, and implement and run a 6$mathrmth$ order Gauss-Legendre collocation method. As promising future scenario, the digital arithmetic method could be employed as an "oracle" within quantum search algorithms for inverse problems.
  arXiv  Detail & Related papers  (2020-12-17T09:49:35Z)

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.