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) a fast-forwarding algorithm that builds on construction of Apers and Sarlette [Quantum Inf. Comput. 19, 181 (2019)] and (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.
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) a fast-forwarding algorithm that builds on construction of Apers and Sarlette [Quantum Inf. Comput. 19, 181 (2019)] and (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.
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩, where ∣x⟩ is a prepared eigenstate and M is an observable. For an n×ns-sparse Hermitian matrix H, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3) time. In contrast, our algorithm runs in time O~(ns2log2n/Δmin), where Δmin denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin−1=O(n), the most favorable scaling for n distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix M is s-sparse, the complexity is O(sρ2κ2/ε2) for diagonalizable matrices that only have real eigenvalues, and O(sρ∥M∥max/ε2) for normal matrices. Here ρ is an upper bound of the eigenvalues, κ is the conditioning of the eigenvalue problem, and ε is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.
Computing eigenvalues of matrices is ubiquitous in numerical linear algebra problems. Currently, fast quantum algorithms for estimating eigenvalues of Hermitian and unitary matrices are known. However, the general case is far from fully understood in the quantum case. Based on a quantum algorithm for solving linear ordinary differential equations, we show how to estimate the eigenvalues of diagonalizable matrices that only have real eigenvalues. The output is a superposition of the eigenpairs, and the overall complexity is polylog in the dimension for sparse matrices. Under an assumption, we extend the algorithm to diagonalizable matrices with complex eigenvalues.
Linear matrix systems represent a fundamental class of problems in mathematics, physics, and engineering, and their efficient solution is crucial for various applications. Traditional methods often rely on computationally intensive algorithms, limiting scalability. This paper explores the potential of leveraging the inherent non-linear properties of linear matrices to design novel quantum algorithms for solving linear systems. We propose a quantum algorithm predicated on the principle that by mapping a linear system into a non-linear representation via a specific matrix transformation, we can achieve speedups that surpass classical approaches. The core mechanism involves constructing a quantum circuit that systematically explores this non-linear space, leveraging quantum phenomena like superposition and entanglement to enhance the search process. The paper details the design of a quantum algorithm for solving linear systems, emphasizing the benefits of this approach and its potential to unlock new possibilities in quantum computation.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log2n) parallel time with a total cost of O(nω+1) Boolean operations. This Boolean complexity matches the best known rigorous O(log2n) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod(2π)) is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in O(log2n) parallel time and O(nω) Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.