The quantum eigenvalue problem arises in the study of the geometric measure of the quantum entanglement. In this paper, we convert the quantum eigenvalue problem to the Z-eigenvalue problem of a real symmetric tensor. In this way, the theory and algorithms for Z-eigenvalues can be applied to the quantum eigenvalue problem. In particular, this gives an upper bound for the number of quantum eigenvalues. We show that the quantum eigenvalues appear in pairs, i.e., if a real number $λ$ is a quantum eigenvalue of a square symmetric tensor $Ψ$ , then $-λ$ is also a quantum eigenvalue of $Ψ$ . When $Ψ$ is real, we show that the entanglement eigenvalue of $Ψ$ is always greater than or equal to the Z-spectral radius of $Ψ$ , and that in several cases the equality holds. We also show that the ratio between the entanglement eigenvalue and the Z-spectral radius of a real symmetric tensor is bounded above in a real symmetric tensor space of fixed order and dimension.The quantum eigenvalue problem arises in the study of the geometric measure of the quantum entanglement. In this paper, we convert the quantum eigenvalue problem to the Z-eigenvalue problem of a real symmetric tensor. In this way, the theory and algorithms for Z-eigenvalues can be applied to the quantum eigenvalue problem. In particular, this gives an upper bound for the number of quantum eigenvalues. We show that the quantum eigenvalues appear in pairs, i.e., if a real number $λ$ is a quantum eigenvalue of a square symmetric tensor $Ψ$, then $-λ$ is also a quantum eigenvalue of $Ψ$. When $Ψ$ is real, we show that the entanglement eigenvalue of $Ψ$ is always greater than or equal to the Z-spectral radius of $Ψ$, and that in several cases the equality holds. We also show that the ratio between the entanglement eigenvalue and the Z-spectral radius of a real symmetric tensor is bounded above in a real symmetric tensor space of fixed order and dimension.

arXiv:1205.1342May 7, 20123 citations

Quantum algorithms for the polynomial eigenvalue problems.

Changpeng Shao, Jin-Peng Liu

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $\Omega(\sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $\Omega(\sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

Oct 28, 20200 citations

The Eigenvalue Problem

Alexander Komech

Springer eBooksOct 23, 20120 citations

Solving generalized eigenvalue problems by ordinary differential equations on a quantum computer

Changpeng Shao, Jin-Peng Liu

Many eigenvalue problems arising in practice are often of the generalized form A x = λ B x . One particularly important case is symmetric, namely A , B are Hermitian and B is positive definite. The standard algorithm for solving this class of eigenvalue problems is to reduce them to Hermitian eigenvalue problems. For a quantum computer, quantum phase estimation is a useful technique to solve Hermitian eigenvalue problems. In this work, we propose a new quantum algorithm for symmetric generalized eigenvalue problems using ordinary differential equations. The algorithm has lower complexity than the standard one based on quantum phase estimation. Moreover, it works for a wider case than symmetric: B is invertible, B − 1 A is diagonalizable and all the eigenvalues are real.Many eigenvalue problems arising in practice are often of the generalized form A x = λ B x . One particularly important case is symmetric, namely A , B are Hermitian and B is positive definite. The standard algorithm for solving this class of eigenvalue problems is to reduce them to Hermitian eigenvalue problems. For a quantum computer, quantum phase estimation is a useful technique to solve Hermitian eigenvalue problems. In this work, we propose a new quantum algorithm for symmetric generalized eigenvalue problems using ordinary differential equations. The algorithm has lower complexity than the standard one based on quantum phase estimation. Moreover, it works for a wider case than symmetric: B is invertible, B − 1 A is diagonalizable and all the eigenvalues are real.

arXiv:2010.15027Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesJun 1, 20225 citations

λ

is a quantum eigenvalue of a square symmetric tensor

Ψ

, then

-λ

is also a quantum eigenvalue of

Ψ

. When

Ψ

is real, we show that the entanglement eigenvalue of

Ψ

is always greater than or equal to the Z-spectral radius of

Ψ

, and that in several cases the equality holds. We also show that the ratio between the entanglement eigenvalue and the Z-spectral radius of a real symmetric tensor is bounded above in a real symmetric tensor space of fixed order and dimension.

A,B

symmetric, and

B

positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when

B

is invertible,

B^{-1}A

is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when

B

is singular, any quantum algorithm uses at least

\Omega(\sqrt{n})

queries to compute the eigenvalues, where

n

is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.