Quantum algorithm for matrix logarithm by integral formula

Yatian Wang, Hua Xiang, Songling ZhangQuantum Inf. Process 2023 · DOI

TL;DR

This paper introduces a novel quantum algorithm to compute the matrix logarithm, a fundamental operation in many scientific fields. By leveraging the integral representation of the matrix logarithm and the Gauss-Legendre quadrature rule, the authors develop a quantum approach that overcomes limitations of previous methods, particularly for functions with singularities at the origin.

What Problem Does This Paper Address?

The matrix logarithm, denoted as $\log(A)$, is a crucial function in various applications, including quantum state preparation and solving linear systems. While quantum algorithms like HHL and its LCU-based improvements have shown promise for general matrix functions, they struggle with functions that have singularities at the origin, such as the matrix logarithm. Existing quantum algorithms for matrix functions often rely on contour integrals around the origin, making them unsuitable for $\log(A)$. This paper aims to bridge this gap by proposing a quantum algorithm that can efficiently compute $\log(A)b$ for a given vector $b$, even when the matrix $A$ might have eigenvalues on the negative real axis.

Methods

The core of this work lies in approximating the matrix logarithm using its integral representation and the Gauss-Legendre quadrature rule. The integral formula for the principal matrix logarithm is given by:

$\log(A) = (A - I) \int_0^1 h(t) dt$, where $h(t) = [t(A - I) + I]^{-1}$.

The authors then discretize this integral using the M-point Gauss-Legendre quadrature, which is shown to be equivalent to the (M, M) Padé approximation of the matrix logarithm. This approximation, denoted as $f_M(A)$, allows for the computation of $\log(A)b$ by first computing the state $|h_M\rangle$ corresponding to $h_M(A)b$ and then transforming it to the desired state $|f_M\rangle$ representing $f_M(A)b$.

The quantum algorithm utilizes two key subroutines:

  1. LCU method (Linear Combination of Unitaries): This is employed to solve linear systems of the form $Ax=b$, which is a prerequisite for constructing the intermediate states.
  2. Block-encoding technique: This is used to create a quantum representation of the matrix $A-I$, enabling the efficient implementation of the required matrix operations.

The algorithm proceeds in several steps: solving a linear system, adding an ancilla qubit and performing controlled rotations, applying Hadamard gates, and finally measuring the registers to obtain the desired state.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Integral Representation as a Bridge: The paper ingeniously uses the integral representation of the matrix logarithm, which avoids direct computation around the origin, to circumvent the limitations of existing quantum algorithms for matrix functions.
  • Gauss-Legendre Quadrature as Padé Approximation: A crucial insight is that the M-point Gauss-Legendre quadrature rule for the matrix logarithm is equivalent to the (M, M) Padé approximation. This connection is vital for bounding the approximation error.
  • Decomposition of Matrix Logarithm Computation: The problem of computing $\log(A)b$ is broken down into computing intermediate states related to $h_M(A)b$ and then transforming them to the final state. This decomposition allows for the application of established quantum techniques like LCU and block-encoding.
  • Error Analysis through Padé Approximations: The paper provides rigorous error bounds by relating the approximation error of the Gauss-Legendre quadrature to the error of Padé approximations, leveraging existing theoretical results.

Key Results

The paper presents a quantum algorithm for computing the state $|f\rangle = \log(A)|b\rangle / ||\log(A)|b||$. The key results include:

  • Approximation of Matrix Logarithm: The matrix logarithm is approximated by $f_M(A) = \sum_{j=1}^M \omega_j [ \tau_j (A - I) + I ]^{-1}$, where $\tau_j$ and $\omega_j$ are nodes and weights of the M-point Gauss-Legendre quadrature.
  • Error Bounds: The paper provides bounds on the approximation error, showing that $||f_M(A) - \log(A)|| \leq \epsilon_{M,A}$, where $\epsilon_{M,A}$ depends on the Padé approximation error.
  • Quantum Algorithm Framework: A step-by-step quantum algorithm is outlined, utilizing LCU and block-encoding techniques.
  • Complexity Analysis: The paper analyzes the query and gate complexity of the algorithm, providing expressions in terms of matrix sparsity ($d$), condition number ($\kappa'$), and the number of quadrature points ($M$). The complexity for queries to the oracle $P_A$ is $O(d\kappa'^2 \log^2(d'))$, and the gate complexity is $O(d\kappa'^2 \log^2(d') [\log(MN) + \log(d')] + L)$, where $L$ is the complexity of implementing the block-encoding.
  • Success Probability: A lower bound for the success probability of the algorithm is derived, which can be improved using amplitude amplification.

Limitations and Future Work

  • Assumption of No Eigenvalues on R¯: The definition of the principal logarithm and the integral representation used in the paper assume that the matrix $A$ has no eigenvalues on the negative real axis. This is a standard assumption for the principal logarithm but might limit its applicability in certain scenarios.
  • Approximation Error: While error bounds are provided, the actual achievable accuracy depends on the choice of $M$ and the precision of the quantum subroutines.
  • Complexity Dependence: The complexity is dependent on the condition number of the matrix $A$, which can be large for ill-conditioned matrices.
  • Future Work: The paper suggests that the technique of amplitude amplification can be used to repeat the algorithm steps to achieve a constant success probability. Further research could explore the application of this method to other matrix functions with singularities.

Summary updated

BibTeX
@article{wang2023quantum,
  author = {Yatian Wang and Hua Xiang and Songling Zhang},
  title = {{Quantum algorithm for matrix logarithm by integral formula}},
  journal = {Quantum Inf. Process.},
  year = {2023},
  doi = {10.1007/s11128-022-03824-y},
}
Figure