Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916383323848704 |
|---|---|
| author | Mizuno, Kota Watabe, Shohei |
| author_facet | Mizuno, Kota Watabe, Shohei |
| contents | Quantum annealing has been recently studied to solve the shortest vector problem (SVP), where the norm of a lattice point vector is mapped to the problem Hamiltonian with the qudit encoding, Hamming-weight encoding, or binary encoding, and the problem to find the shortest vector is mapped to a problem to find a non-trivial first excited state. We here propose an alternative encoding and alternative quantum algorithm to solve the SVP: the one-hot encoding and the quantum imaginary-time algorithm with the folded spectrum (FS) method. We demonstrate that our approach is applicable to find the shortest vector with a variational quantum algorithm. The application of the FS method to the quantum annealing and simulated annealing is also discussed to solve the SVP. Our study shows wide potential applicability of the SVP in quantum computing frameworks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16062 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method Mizuno, Kota Watabe, Shohei Quantum Physics Quantum annealing has been recently studied to solve the shortest vector problem (SVP), where the norm of a lattice point vector is mapped to the problem Hamiltonian with the qudit encoding, Hamming-weight encoding, or binary encoding, and the problem to find the shortest vector is mapped to a problem to find a non-trivial first excited state. We here propose an alternative encoding and alternative quantum algorithm to solve the SVP: the one-hot encoding and the quantum imaginary-time algorithm with the folded spectrum (FS) method. We demonstrate that our approach is applicable to find the shortest vector with a variational quantum algorithm. The application of the FS method to the quantum annealing and simulated annealing is also discussed to solve the SVP. Our study shows wide potential applicability of the SVP in quantum computing frameworks. |
| title | Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.16062 |