Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective

• URL: http://arxiv.org/abs/2309.05290v4
• Date: Sun, 29 Jun 2025 13:13:04 GMT
• Title: Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective
• Authors: Alejandro Mata Ali, Iñigo Perez Delgado, Marina Ristol Roura, Aitor Moreno Fdez. de Leceta, Sebastián V. Romero,
• Abstract summary: We present a new approach for solving systems of linear equations with tensor networks based on the quantum HHL algorithm.<n>We first develop a novel HHL in the qudits formalism, the generalization of qubits, and then transform its operations into an equivalent classical HHL.
• Score: 39.58317527488534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a new approach for solving systems of linear equations with tensor networks based on the quantum HHL algorithm. We first develop a novel HHL in the qudits formalism, the generalization of qubits, and then transform its operations into an equivalent classical HHL, taking advantage of the non-unitary operations that they can apply. The main novelty of this proposal is to perform a classical simulation as efficiently as possible of the HHL to benchmark the algorithm steps according to its input parameters and the input matrix. We apply this algorithm to three simulation problems, comparing it with an exact inversion algorithm, and we compare its performance against an implementation of the original HHL simulated in the Qiskit framework, providing both codes. Our results show that our approach can achieve a promising performance in computational efficiency to simulate HHL process without quantum noise, providing a lower bound.

Related papers

• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks [0.0]
  We present an efficient classical algorithm for simulating the Isotropic Wave Equation (IWE) in one, two, or three dimensions. Exact diagonalization of the unitary circuit in combination with Networks allows simulation of the wave equation with a resolution of $1013$ grid points on a laptop.
  arXiv  Detail & Related papers  (2025-04-15T13:36:08Z)
• Explicit near-optimal quantum algorithm for solving the advection-diffusion equation [0.0]
  An explicit quantum algorithm is proposed for modeling dissipative initial-value problems. We propose a quantum circuit based on a simple coordinate transformation that turns the dependence on the summation index into a trigonometric function. The proposed algorithm can be used for modeling a wide class of nonunitary initial-value problems.
  arXiv  Detail & Related papers  (2025-01-19T19:03:29Z)
• Quantum Discrete Adiabatic Linear Solver based on Block Encoding and Eigenvalue Separator [5.138262101775231]
  The rise of quantum computing has spurred interest in quantum linear system problems. The performance of the HHL algorithm is constrained by its dependence on the square of the condition number. This work proposes a quantum discrete adiabatic linear solver based on block encoding and eigenvalue separation techniques.
  arXiv  Detail & Related papers  (2024-12-09T04:50:48Z)
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems [0.0]
  We propose an explicit algorithm to simulate both the advection-diffusion equation and a nonunitary discretized version of the Koopman-von Neumann formulation of nonlinear dynamics. The proposed algorithm is universal and can be used for modeling a broad class of linear and nonlinear differential equations.
  arXiv  Detail & Related papers  (2024-10-04T23:58:12Z)
• Optimised Hybrid Classical-Quantum Algorithm for Accelerated Solution of Sparse Linear Systems [0.0]
  This paper introduces a hybrid classical-quantum algorithm that combines preconditioning techniques with the HHL algorithm to solve sparse linear systems more efficiently. We show that the proposed approach surpasses traditional methods in speed and scalability but also mitigates some of the inherent limitations of quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-03T11:36:14Z)
• 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)
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
  We adapt a well-known algorithm for linear systems of equations, originally proposed by Harrow, Hassidim and Lloyd (HHL), by adapting it into a predictor-corrector instead of a direct solver. This strategy enables the intelligent omission of computationally costly steps commonly found in many classical algorithms, while simultaneously mitigating the notorious readout problems associated with extracting a quantum state. The versatility of the approach is illustrated through applications in various fields such as smoothed particle hydrodynamics, plasma simulations, and reactive flow configurations.
  arXiv  Detail & Related papers  (2024-06-28T15:31:10Z)
• 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)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• 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)
• 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)
• Solving Linear Systems on Quantum Hardware with Hybrid HHL++ [1.9311784849535176]
  Harrow-Hassidim-Lloyd (HHL) is a critical quantum linear algebra primitive. We propose a novel algorithm for determining a scaling factor for the linear system matrix. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers.
  arXiv  Detail & Related papers  (2021-10-29T17:59:29Z)
• Optimization and Noise Analysis of the Quantum Algorithm for Solving One-Dimensional Poisson Equation [17.65730040410185]
  We propose an efficient quantum algorithm for solving one-dimensional Poisson equation. We further develop this algorithm to make it closer to the real application on the noisy intermediate-scale quantum (NISQ) devices. We analyze the effect of common noise existing in the real quantum devices on our algorithm using the IBM Qiskit toolkit.
  arXiv  Detail & Related papers  (2021-08-27T09:44:41Z)
• Hybrid algorithms to solve linear systems of equations with limited qubit resources [7.111403318486868]
  The complexity using classical methods increases linearly with the size of equations. The HHL algorithm proposed by Harrow et al. achieves exponential acceleration compared with the best classical algorithm. Three hybrid iterative phase estimation algorithms (HIPEA) are designed based on the iterative phase estimation algorithm in this paper.
  arXiv  Detail & Related papers  (2021-06-29T15:10:55Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  This letter investigates a channel assignment problem in uplink wireless communication systems. Our goal is to maximize the sum rate of all users subject to integer channel assignment constraints. Due to high computational complexity, machine learning approaches are employed to obtain computational efficient solutions.
  arXiv  Detail & Related papers  (2020-01-12T15:54:20Z)

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.