A team of researchers, including Alex Kerzner and Luca Dellantonio from softwareQ Inc., the Institute for Quantum Computing, and Transmutex SA, have developed a quantum algorithm that can find the smallest eigenvalue of a Hermitian matrix faster than classical algorithms. The algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. This development could have applications in quantum chemistry and materials science.
Quantum Algorithm for Finding the Smallest Eigenvalue
A quantum algorithm has been developed for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup with respect to the best classical algorithm in terms of matrix dimensionality. This means that the algorithm can perform the task with fewer queries to an oracle encoding the matrix, where N is the matrix dimension and ε is the desired precision. In contrast, the best classical algorithm for the same task requires more queries.
The algorithm also allows the user to select any constant success probability. A similar algorithm with the same runtime has been developed that allows us to prepare a quantum state lying mostly in the matrix’s low-energy subspace. Simulations of both algorithms have been implemented and their application to problems in quantum chemistry and materials science has been demonstrated.
Importance of Finding the Smallest Eigenvalue
Finding the smallest eigenvalue of a Hermitian operator is a common task in quantum computing, computer science, and the natural sciences more generally. The special case of k-local Hamiltonians, which correspond to several quantum systems arising in nature, has been extensively studied in the quantum computing literature. Local Hamiltonians can also encode optimization problems in the sense that the ground state and ground state energy correspond to the minimizer and minimum value of a cost function of interest.
A Hermitian matrix, named after the French mathematician Charles Hermite, is a complex square matrix that is equal to its own conjugate transpose
The power of ground state energy estimation for local Hamiltonians is reflected in the fact that a decision version of this problem is QMA-complete. Although this means that quantum computers are unlikely to provide an exponential speedup for this task, we may hope for polynomial speedups, which can be crucial in practice. Moreover, we might ask whether such speedups can be retained when considering nonlocal Hamiltonians.
Quantum Phase Estimation (QPE) Algorithm
One well-known quantum algorithm for solving this problem is the quantum phase estimation (QPE) algorithm. This algorithm, given an eigenstate of a unitary operator, estimates its eigenvalue. However, in general, it is not clear whether the ground state can be efficiently prepared. One approach is to first prepare the ground state of a known Hamiltonian, then perform an adiabatic evolution to slowly evolve the initial state into the ground state of the target Hamiltonian.
However, the time required for this adiabatic evolution is inversely proportional to the gap between the smallest eigenvalues of the Hamiltonian, and in general, this gap may vanish. Moreover, for general Hamiltonians, this gap is usually unknown a priori, making it impossible to assess the validity of the obtained result.
Variational Algorithms
Other quantum approaches include variational algorithms. These prepare a circuit where there is a set of parameters with which the circuit varies continuously. The smallest eigenvalue of an n-qubit Hamiltonian H is (hopefully) the minimum value of a certain function, and so by computing this value and repeatedly varying the parameters according to a classical minimization strategy, we might hope to find the global minimum.
However, variational algorithms have few performance guarantees, as their cost landscapes may suffer from barren plateaus and local minima.
Advantages of the New Quantum Algorithm
The new quantum algorithm described in the paper has a guaranteed speedup over the best possible classical algorithm with respect to the dimension of the considered matrix and a success probability that the user can select. This algorithm makes use only of two basic subroutines: QPE and quantum amplitude estimation (QAE) and requires fewer black-box queries to the matrix, where N is the matrix dimension and ε the desired precision. For fixed ε, this is an improvement over classical algorithms, which require more queries.
“In this paper, we describe a quantum algorithm that has (1) a guaranteed speedup over the best possible classical algorithm with respect to the dimension of the considered matrix; and (2) a success probability that the user can select. This algorithm makes use only of two basic subroutines: QPE and quantum amplitude estimation (QAE) [18] and requires Oe(√N /ε) black-box queries to the matrix, where N is the matrix dimension and ε the desired precision. For fixed ε, this is an improvement over classical algorithms, which require Ω(N)polylog(1/ε) queries.”
Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carminati, Fabio Fracas, and Luca Dellantonio
Quick Summary
Scientists have developed a quantum algorithm that can find the smallest eigenvalue of a Hermitian matrix, achieving a quadratic speedup compared to the best classical algorithm. This advancement could have applications in quantum chemistry and materials science.
- A team of researchers, including Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico Carminati, Fabio Fracas, and Luca Dellantonio, have developed a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix.
- The algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup compared to the best classical algorithm in terms of matrix dimensionality.
- The quantum algorithm requires significantly fewer queries to the matrix than classical algorithms, offering an improvement in efficiency.
- The algorithm also allows the user to select any constant success probability.
- The team has implemented simulations of both algorithms and demonstrated their application to problems in quantum chemistry and materials science.
- The researchers are affiliated with various institutions, including softwareQ Inc., the Institute for Quantum Computing at the University of Waterloo, the Perimeter Institute for Theoretical Physics, the Laboratory for Reactor Physics and Systems Behaviour at EPFL, Transmutex SA, the University of Padua, and the Department of Physics and Astronomy at the University of Exeter.