Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2307.12047 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909986869739520 |
|---|---|
| author | Schirman, Eden Ling, Cong Mintert, Florian |
| author_facet | Schirman, Eden Ling, Cong Mintert, Florian |
| contents | The advent of quantum computing necessitates the transition of worldwide cryptosystems to post-quantum cryptography (PQC), which is founded upon the problem of finding short vectors in high-dimensional structured lattices. It is assumed that the structure of these lattices cannot be exploited by quantum or classical algorithms attempting to find short vectors. In this work, we focus on the structure of the lattices used in PQC protocols - nega-cyclic (and cyclic)lattices - and provide a quantum algorithmic framework that efficiently encodes the structured lattices into Hamiltonians by exploiting their underlying symmetries. The efficient encoding substantially reduces the dimension of the corresponding Hilbert space by limiting it to a relevant subspace where short vectors are likely to be found - leading to significant savings in quantum resources (e.g. qubit count and circuit depth) required to implement a quantum algorithm for finding short vectors. We analytically prove the efficient encoding procedure and benchmark the proposed framework using the variational quantum eigensolver, demonstrating improved results with reduced quantum resources. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_12047 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient Lattice Hamiltonian Encoding for the Shortest Vector Problem Schirman, Eden Ling, Cong Mintert, Florian Quantum Physics The advent of quantum computing necessitates the transition of worldwide cryptosystems to post-quantum cryptography (PQC), which is founded upon the problem of finding short vectors in high-dimensional structured lattices. It is assumed that the structure of these lattices cannot be exploited by quantum or classical algorithms attempting to find short vectors. In this work, we focus on the structure of the lattices used in PQC protocols - nega-cyclic (and cyclic)lattices - and provide a quantum algorithmic framework that efficiently encodes the structured lattices into Hamiltonians by exploiting their underlying symmetries. The efficient encoding substantially reduces the dimension of the corresponding Hilbert space by limiting it to a relevant subspace where short vectors are likely to be found - leading to significant savings in quantum resources (e.g. qubit count and circuit depth) required to implement a quantum algorithm for finding short vectors. We analytically prove the efficient encoding procedure and benchmark the proposed framework using the variational quantum eigensolver, demonstrating improved results with reduced quantum resources. |
| title | Efficient Lattice Hamiltonian Encoding for the Shortest Vector Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2307.12047 |