A square-root speedup for finding the smallest eigenvalue
- URL: http://arxiv.org/abs/2311.04379v2
- Date: Wed, 15 Nov 2023 15:08:31 GMT
- Title: A square-root speedup for finding the smallest eigenvalue
- Authors: Alex Kerzner, Vlad Gheorghiu, Michele Mosca, Thomas Guilbaud, Federico
Carminati, Fabio Fracas, Luca Dellantonio
- Abstract summary: We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix.
This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup.
We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
- Score: 0.6597195879147555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We describe a quantum algorithm 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, i.e.,
$\widetilde{\mathcal{O}}(\sqrt{N}/\epsilon)$ black-box queries to an oracle
encoding the matrix, where $N$ is the matrix dimension and $\epsilon$ is the
desired precision. In contrast, the best classical algorithm for the same task
requires $\Omega(N)\text{polylog}(1/\epsilon)$ queries. In addition, this
algorithm allows the user to select any constant success probability. We also
provide a similar algorithm with the same runtime that allows us to prepare a
quantum state lying mostly in the matrix's low-energy subspace. We implement
simulations of both algorithms and demonstrate their application to problems in
quantum chemistry and materials science.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
Finding a good approximation of the top eigenvector of a given $dtimes d$ matrix $A$ is a basic and important computational problem.
We give two different quantum algorithms that output a classical description of a good approximation of the top eigenvector.
arXiv Detail & Related papers (2024-05-23T16:33:13Z) - Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.
This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
arXiv Detail & Related papers (2023-11-17T20:38:38Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions.
Our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures.
arXiv Detail & Related papers (2023-02-03T17:22:49Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph.
Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework.
We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
arXiv Detail & Related papers (2022-03-28T02:24:08Z) - Improved quantum lower and upper bounds for matrix scaling [0.0]
We investigate the possibilities for quantum speedups for classical second-order algorithms.
We show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime.
We give improved quantum algorithms in the low-precision regime.
arXiv Detail & Related papers (2021-09-30T17:29:23Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.