Quantum algorithms for powering stable Hermitian matrices
- URL: http://arxiv.org/abs/2103.08329v1
- Date: Mon, 15 Mar 2021 12:20:04 GMT
- Title: Quantum algorithms for powering stable Hermitian matrices
- Authors: Guillermo Gonz\'alez, Rahul Trivedi, J. Ignacio Cirac
- Abstract summary: Matrix powering is a fundamental computational primitive in linear algebra.
We present two quantum algorithms that can achieve speedup over the classical matrix powering algorithms.
- Score: 0.7734726150561088
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Matrix powering is a fundamental computational primitive in linear algebra.
It has widespread applications in scientific computing and engineering, and
underlies the solution of time-homogeneous linear ordinary differential
equations, simulation of discrete-time Markov chains, or discovering the
spectral properties of matrices with iterative methods. In this paper, we
investigate the possibility of speeding up matrix powering of sparse stable
Hermitian matrices on a quantum computer. We present two quantum algorithms
that can achieve speedup over the classical matrix powering algorithms -- (i)
an adaption of quantum-walk based fast forwarding algorithm (ii) an algorithm
based on Hamiltonian simulation. Furthermore, by mapping the N-bit parity
determination problem to a matrix powering problem, we provide no-go theorems
that limit the quantum speedups achievable in powering non-Hermitian matrices.
Related papers
- Tensor networks based quantum optimization algorithm [0.0]
In optimization, one of the well-known classical algorithms is power iterations.
We propose a quantum realiziation to circumvent this pitfall.
Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
arXiv Detail & Related papers (2024-04-23T13:49:11Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations.
We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix.
A quantum algorithm to simulate the dynamics of the density matrix is proposed.
arXiv Detail & Related papers (2023-06-14T23:08:51Z) - 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) - 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) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph.
Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework.
We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
arXiv Detail & Related papers (2022-03-28T02:24:08Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model.
These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization.
We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance.
The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
arXiv Detail & Related papers (2021-06-24T16:39:31Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - Quantum Algorithms for Estimating Physical Quantities using
Block-Encodings [0.30458514384586405]
We present quantum algorithms for the estimation of n-time correlation functions, the local and non-local density of states, and dynamical linear response functions.
All algorithms are based on block-encodings - a technique for the manipulation of arbitrary non-unitary combinations on a quantum computer.
arXiv Detail & Related papers (2020-04-14T23:15:39Z)
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.