Matrix Inversion by Quantum Walk

• URL: http://arxiv.org/abs/2508.06611v1
• Date: Fri, 08 Aug 2025 18:00:05 GMT
• Title: Matrix Inversion by Quantum Walk
• Authors: Alastair Kay, Christino Tamon,
• Abstract summary: The HHL algorithm for matrix inversion is a landmark algorithm in quantum computation.<n>We substantially simplify the algorithm by replacing the phase estimations with a continuous time quantum walk.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The HHL algorithm for matrix inversion is a landmark algorithm in quantum computation. Its ability to produce a state $|x\rangle$ that is the solution of $Ax=b$, given the input state $|b\rangle$, is envisaged to have diverse applications. In this paper, we substantially simplify the algorithm, originally formed of a complex sequence of phase estimations, amplitude amplifications and Hamiltonian simulations, by replacing the phase estimations with a continuous time quantum walk. The key technique is the use of weak couplings to access the matrix inversion embedded in perturbation theory.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Quantum matrix arithmetics with Hamiltonian evolution [4.408403263084943]
  efficient implementation of matrix arithmetic operations underpins speedups of quantum algorithms.<n>We develop a suite of methods to perform matrix arithmetics using Hamiltonian evolutions of input operators.<n>We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count.
  arXiv  Detail & Related papers  (2025-10-07T18:00:01Z)
• Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications [18.700744251450313]
  We present an improved algorithm achieving the instance-optimal regret bound of $O(sqrtTcdot S(X||d-1I_d))$.<n>We show that it outperforms the state of the art for learning quantum states corrupted by depolarization noise, random quantum states, and Gibbs states.
  arXiv  Detail & Related papers  (2025-09-10T18:15:41Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  We propose the variational quantum singular value decomposition based on encoding the elements of the considered $Ntimes N$ matrix into the state of a quantum system of appropriate dimension.<n> Controlled measurement is involved to avoid small success in ancilla measurement.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
  This paper presents a novel quantum algorithm, XZ24, for efficiently computing the eigen-energy spectra of arbitrary quantum systems. XZ24 has three key advantages: It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap. It enables simultaneous computation of multiple eigen-energies, depending on the reference state.
  arXiv  Detail & Related papers  (2024-06-01T04:31:43Z)
• Quantum conjugate gradient method using the positive-side quantum eigenvalue transformation [0.35794129023851595]
  We introduce the quantum conjugate gradient (QCG) method using the quantum eigenvalue transformation (QET) Based on the numerical results, our algorithm significantly improves circuit depth, outperforming another QET-based algorithm by three to four orders of magnitude.
  arXiv  Detail & Related papers  (2024-04-03T13:13:55Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>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 Algorithm for Solving the Advection Equation using Hamiltonian Simulation [0.0]
  One-dimensional advection can be simulated directly since the central finite difference operator for first-order derivatives is anti-Hermitian. A single copy of the initial quantum state is required and the circuit depth grows linearly with the required number of time steps.
  arXiv  Detail & Related papers  (2023-12-15T13:39:27Z)
• Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
  We apply modern machine learning techniques to studying the unitarity constraint. We find a new phase-ambiguous solution which pushes the known limit on such solutions significantly beyond the previous bound.
  arXiv  Detail & Related papers  (2023-08-18T10:29:26Z)
• 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)
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices [3.1952399274829775]
  We develop a tool called quantum eigenvalue transformation of unitary matrices with reals (QET-U) This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model.
  arXiv  Detail & Related papers  (2022-04-12T17:11:40Z)
• Efficient multi-qubit subspace rotations via topological quantum walks [1.0486921990935787]
  The rotation of subspaces by a chosen angle is a fundamental quantum computing operation. We propose a fast, high-fidelity way to implement such operations via topological quantum walks. This procedure can be implemented in superconducting qubits, ion-traps and Rydberg atoms with star-type connectivity.
  arXiv  Detail & Related papers  (2021-11-12T02:10:56Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• 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.