Quantum algorithms for powering stable Hermitian matrices
arXiv:2103.08329 · doi:10.1103/PhysRevA.103.062420
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.
References in corpus (24)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum algorithm for solving linear systems of equations
- Quantum Simulation
- Quantum computational advantage using photons
- Quantum random access memory
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Quantum speedup of Monte Carlo methods
- High-order quantum algorithm for solving linear differential equations
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- A Limit on the Speed of Quantum Computation in Determining Parity
- Quantum Simulation of Generic Many-Body Open System Dynamics Using Classical Noise
- A dissipative quantum Church-Turing theorem
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations
- Algorithms for quantum simulation at finite energies
- Quantum Power Method by a Superposition of Time-Evolved States
- Adiabatic quantum algorithms as quantum phase transitions: first versus second order
- Black-box Hamiltonian simulation and unitary implementation
- Quantum Simulation of Dissipative Processes without Reservoir Engineering
- Efficient Quantum Algorithms for Simulating Lindblad Evolution
- Quantum Computational Method of Finding the Ground State Energy and Expectation Values
- Implementing smooth functions of a Hermitian matrix on a quantum computer