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

arXiv:2111.08914

Quantum Algorithm for Matrix Logarithm by Integral Formula

Songling Zhang, Hua Xiang

Published Nov 17, 2021• 0 citations
arXivHTMLPDF

Abstract

The matrix logarithm is one of the important matrix functions. Recently, a quantum algorithm that computes the state $|f\rangle$ corresponding to matrix-vector product $f(A)b$ is proposed in [Takahira, et al. Quantum algorithm for matrix functions by Cauchy's integral formula, QIC, Vol.20, No.1\&2, pp.14-36, 2020]. However, it can not be applied to matrix logarithm. In this paper, we propose a quantum algorithm, which uses LCU method and block-encoding technique as subroutines, to compute the state $|f\rangle = \log(A)|b\rangle / \|\log(A)|b\rangle\|$ corresponding to $\log(A)b$ via the integral representation of $\log(A)$ and the Gauss-Legendre quadrature rule.

DOI
10.48550/arxiv.2111.08914

Related papers

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•10 citations

Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

Yanqiao Wang, Jin-Peng Liu

We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix $M$ is chosen so that the target operator is a block of $\text{sign}(M)$ or is recovered from blocks of $(I-\text{sign}(M))/2$. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.

quant-pharXiv:2604.25333•Apr 29, 2026•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•8 citations

Preparation of digital-encoded and analog-encoded quantum states corresponding to matrix operations

Kaitian Gao, Youlong Yang, Zhenye Du

Abstract Efficient implementation of fundamental matrix operations on quantum computers, such as matrix products and Hadamard operations, holds significant potential for accelerating machine learning algorithms. A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states. We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations, including the matrix product, matrix sum, matrix Hadamard product and division. Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O (poly log( mn / ε )) and the matrix product with a time complexity of O (poly log( mnl / ε )), achieving an exponential speedup in contrast to the classical methods of O ( mn ) and O ( mnl ). Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O ( k 1 m n ⋅ poly log ( m n / ε ) ) and the matrix product with a time complexity of O ( k 2 l ⋅ poly log ( m n l / ε ) ) , where k 1 and k 2 are coefficients correlated with the elements of the matrix, achieving a square speedup in contrast to the classical counterparts. As applications, we construct an oracle that can access the trace of a matrix within logarithmic time, and propose several algorithms to respectively estimate the trace of a matrix, the trace of the product of two matrices, and the trace inner product of two matrices within logarithmic time.

Chinese Physics B•Jun 12, 2025•0 citations

Contour-integral based quantum eigenvalue transformation: analysis and applications

Shan Jiang, Dong An

Eigenvalue transformations appear ubiquitously in scientific computation, ranging from matrix polynomials to differential equations, and are beyond the reach of the quantum singular value transformation framework. In this work, we study the efficiency of quantum algorithms based on contour integral representation for eigenvalue transformations from both theoretical and practical aspects. Theoretically, we establish a complete complexity analysis of the contour integral approach proposed in [Takahira, Ohashi, Sogabe, and Usuda. Quant. Inf. Comput., 22, 11\&12, 965--979 (2021)]. Moreover, we combine the contour integral approach and the sampling-based linear combination of unitaries to propose a quantum algorithm for estimating observables of eigenvalue transformations using only $3$ additional qubits. Practically, we design contour integral based quantum algorithms for linear ordinary differential equations, $\varphi$-functions, Fréchet derivatives of matrix functions, and matrix functions. In particular, we show that the contour integral algorithm can outperform all the existing quantum algorithms in the case of solving asymptotically stable differential equations.

quant-pharXiv:2601.11959•Jan 20, 2026•0 citations

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal +2 more

Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree$-d$ polynomial, using circuits with logarithmic depth in the number $n$ of qubits and only $\mathcal O(n)$ ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only $n$ terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state $|1\rangle$. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using $14$ qubits and more than $500$ primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.

quant-pharXiv:2603.16527•Mar 18, 2026•0 citations
The matrix logarithm is one of the important matrix functions. Recently, a quantum algorithm that computes the state ∣f⟩|f\rangle∣f⟩ corresponding to matrix-vector product f(A)bf(A)bf(A)b is proposed in [Takahira, et al. Quantum algorithm for matrix functions by Cauchy's integral formula, QIC, Vol.20, No.1&2, pp.14-36, 2020]. However, it can not be applied to matrix logarithm. In this paper, we propose a quantum algorithm, which uses LCU method and block-encoding technique as subroutines, to compute the state ∣f⟩=log⁡(A)∣b⟩/∥log⁡(A)∣b⟩∥|f\rangle = \log(A)|b\rangle / \|\log(A)|b\rangle\|∣f⟩=log(A)∣b⟩/∥log(A)∣b⟩∥ corresponding to log⁡(A)b\log(A)blog(A)b via the integral representation of log⁡(A)\log(A)log(A) and the Gauss-Legendre quadrature rule.
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.
We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix MMM is chosen so that the target operator is a block of sign(M)\text{sign}(M)sign(M) or is recovered from blocks of (I−sign(M))/2(I-\text{sign}(M))/2(I−sign(M))/2. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.
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.
Abstract Efficient implementation of fundamental matrix operations on quantum computers, such as matrix products and Hadamard operations, holds significant potential for accelerating machine learning algorithms. A critical prerequisite for quantum implementations is the effective encoding of classical data into quantum states. We propose two quantum computing frameworks for preparing the distinct encoded states corresponding to matrix operations, including the matrix product, matrix sum, matrix Hadamard product and division. Quantum algorithms based on the digital encoding computing framework are capable of implementing the matrix Hadamard operation with a time complexity of O (poly log( mn / ε )) and the matrix product with a time complexity of O (poly log( mnl / ε )), achieving an exponential speedup in contrast to the classical methods of O ( mn ) and O ( mnl ). Quantum algorithms based on the analog-encoding framework are capable of implementing the matrix Hadamard operation with a time complexity of O ( k 1 m n ⋅ poly log ( m n / ε ) ) and the matrix product with a time complexity of O ( k 2 l ⋅ poly log ( m n l / ε ) ) , where k 1 and k 2 are coefficients correlated with the elements of the matrix, achieving a square speedup in contrast to the classical counterparts. As applications, we construct an oracle that can access the trace of a matrix within logarithmic time, and propose several algorithms to respectively estimate the trace of a matrix, the trace of the product of two matrices, and the trace inner product of two matrices within logarithmic time.
Eigenvalue transformations appear ubiquitously in scientific computation, ranging from matrix polynomials to differential equations, and are beyond the reach of the quantum singular value transformation framework. In this work, we study the efficiency of quantum algorithms based on contour integral representation for eigenvalue transformations from both theoretical and practical aspects. Theoretically, we establish a complete complexity analysis of the contour integral approach proposed in [Takahira, Ohashi, Sogabe, and Usuda. Quant. Inf. Comput., 22, 11\&12, 965--979 (2021)]. Moreover, we combine the contour integral approach and the sampling-based linear combination of unitaries to propose a quantum algorithm for estimating observables of eigenvalue transformations using only 333 additional qubits. Practically, we design contour integral based quantum algorithms for linear ordinary differential equations, φ\varphiφ-functions, Fréchet derivatives of matrix functions, and matrix functions. In particular, we show that the contour integral algorithm can outperform all the existing quantum algorithms in the case of solving asymptotically stable differential equations.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only nnn terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩|1\rangle∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 141414 qubits and more than 500500500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.