Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum algorithm for matrix functions

宗一 高比良, Souichi Takahira

Published Mar 20, 2020• 0 citations
OpenAlex

Related papers

Quantum algorithm for linear systems

Yunah Choi, Jeihee Cho, Shiho Kim

Advances in computers•Nov 29, 2025•0 citations

Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals

Souichi Takahira, A. Ohashi, Tomohiro Sogabe +1 more

he matrix functions can be defined by Cauchy's integral formula and can be approximated by the linear combination of inverses of shifted matrices using a quadrature formula. In this paper, we propose a quantum algorithm for matrix functions based on a procedure to implement the linear combination of the inverses on quantum computers. Compared with the previous study [S. Takahira, A. Ohashi, T. Sogabe, and T.S. Usuda, Quant. Inf. Comput., \textbf{20}, 1\&2, 14--36, (Feb. 2020)] that proposed a quantum algorithm to compute a quantum state for the matrix function based on the circular contour centered at the origin, the quantum algorithm in the present paper can be applied to a more general contour. Moreover, the algorithm is described by the block-encoding framework. Similarly to the previous study, the algorithm can be applied even if the input matrix is not a Hermitian or normal matrix. This is an advantage compared with quantum singular value transformation.

arXiv:2106.08076•Quantum Information and Computation•Aug 1, 2022•25 citations

Algorithms of quantum computation

Shinil Cho

Institute of Physics eBooks•Jul 1, 2022•8 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

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.

•Jul 24, 2020•0 citations

Quantum algorithm for matrix functions by Cauchy's integral formula

Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe +1 more

For matrix A, vector b and function f, the computation of vector f(A)b arises in many scientific computing applications. We consider the problem of obtaining quantum state |f> corresponding to vector f(A)b. There is a quantum algorithm to compute state |f> using eigenvalue estimation that uses phase estimation and Hamiltonian simulation e^{\im A t}. However, the algorithm based on eigenvalue estimation needs \poly(1/\epsilon) runtime, where \epsilon is the desired accuracy of the output state. Moreover, if matrix A is not Hermitian, \e^{\im A t} is not unitary and we cannot run eigenvalue estimation. In this paper, we propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation. We show that the runtime of the algorithm is \poly(\log(1/\epsilon)) and the algorithm outputs state |f> even if A is not Hermitian.

arXiv:2106.08075•Quantum Information and Computation•Feb 1, 2020•23 citations

On quantum computational algorithms

이수준

•Jan 1, 2002•0 citations
he matrix functions can be defined by Cauchy's integral formula and can be approximated by the linear combination of inverses of shifted matrices using a quadrature formula. In this paper, we propose a quantum algorithm for matrix functions based on a procedure to implement the linear combination of the inverses on quantum computers. Compared with the previous study [S. Takahira, A. Ohashi, T. Sogabe, and T.S. Usuda, Quant. Inf. Comput., \textbf{20}, 1\&2, 14--36, (Feb. 2020)] that proposed a quantum algorithm to compute a quantum state for the matrix function based on the circular contour centered at the origin, the quantum algorithm in the present paper can be applied to a more general contour. Moreover, the algorithm is described by the block-encoding framework. Similarly to the previous study, the algorithm can be applied even if the input matrix is not a Hermitian or normal matrix. This is an advantage compared with quantum singular value transformation.
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.
For matrix A, vector b and function f, the computation of vector f(A)b arises in many scientific computing applications. We consider the problem of obtaining quantum state |f> corresponding to vector f(A)b. There is a quantum algorithm to compute state |f> using eigenvalue estimation that uses phase estimation and Hamiltonian simulation e^{\im A t}. However, the algorithm based on eigenvalue estimation needs \poly(1/\epsilon) runtime, where \epsilon is the desired accuracy of the output state. Moreover, if matrix A is not Hermitian, \e^{\im A t} is not unitary and we cannot run eigenvalue estimation. In this paper, we propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation. We show that the runtime of the algorithm is \poly(\log(1/\epsilon)) and the algorithm outputs state |f> even if A is not Hermitian.