Quantum Approximate $k$-Minimum Finding
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912621516554240 |
|---|---|
| author | Gao, Minbo Ji, Zhengfeng Wang, Qisheng |
| author_facet | Gao, Minbo Ji, Zhengfeng Wang, Qisheng |
| contents | Quantum $k$-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum $k$-minimum finding algorithm that works with approximate values for all $k \geq 1$, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for $k=1$. As practical applications of this algorithm, we present efficient quantum algorithms for identifying the $k$ smallest expectation values among multiple observables and for determining the $k$ lowest ground state energies of a Hamiltonian with a known eigenbasis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16586 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Approximate $k$-Minimum Finding Gao, Minbo Ji, Zhengfeng Wang, Qisheng Quantum Physics Quantum $k$-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum $k$-minimum finding algorithm that works with approximate values for all $k \geq 1$, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for $k=1$. As practical applications of this algorithm, we present efficient quantum algorithms for identifying the $k$ smallest expectation values among multiple observables and for determining the $k$ lowest ground state energies of a Hamiltonian with a known eigenbasis. |
| title | Quantum Approximate $k$-Minimum Finding |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2412.16586 |