Report
A square-root speedup for finding the smallest eigenvalue
| العنوان: | A square-root speedup for finding the smallest eigenvalue |
|---|---|
| المؤلفون: | Kerzner, Alex, Gheorghiu, Vlad, Mosca, Michele, Guilbaud, Thomas, Carminati, Federico, Fracas, Fabio, Dellantonio, Luca |
| سنة النشر: | 2023 |
| المجموعة: | Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics |
| الوصف: | 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. Comment: 17 pages, 6 figures, all comments are welcome, additional references added |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2311.04379 |
| رقم الانضمام: | edsarx.2311.04379 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |