Finding dense sublattices as low energy states of a Hamiltonian
Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2024-12-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.6.043279 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850116824542216192 |
|---|---|
| author | Júlia Barberà-Rodríguez Nicolas Gama Anand Kumar Narayanan David Joseph |
| author_facet | Júlia Barberà-Rodríguez Nicolas Gama Anand Kumar Narayanan David Joseph |
| author_sort | Júlia Barberà-Rodríguez |
| collection | DOAJ |
| description | Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K-Densest Sublattice Problem (K-DSP): to find the densest K-dimensional sublattice of a given lattice. We formulate K-DSP as finding the first excited state of a Z-basis Hamiltonian, making K-DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O(KN^{2}) qubits suffice for solving K-DSP for N-dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K-DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K-DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K-DSP. We devise a quantum algorithm that solves K-DSP with runtime exponent (5KNlog_{2}N)/2. Therefore, for fixed K, K-DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K-DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question. |
| format | Article |
| id | doaj-art-a9f8bfa97f81499ab1cd256f632d0fd4 |
| institution | OA Journals |
| issn | 2643-1564 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj-art-a9f8bfa97f81499ab1cd256f632d0fd42025-08-20T02:36:14ZengAmerican Physical SocietyPhysical Review Research2643-15642024-12-016404327910.1103/PhysRevResearch.6.043279Finding dense sublattices as low energy states of a HamiltonianJúlia Barberà-RodríguezNicolas GamaAnand Kumar NarayananDavid JosephLattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K-Densest Sublattice Problem (K-DSP): to find the densest K-dimensional sublattice of a given lattice. We formulate K-DSP as finding the first excited state of a Z-basis Hamiltonian, making K-DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O(KN^{2}) qubits suffice for solving K-DSP for N-dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K-DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K-DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K-DSP. We devise a quantum algorithm that solves K-DSP with runtime exponent (5KNlog_{2}N)/2. Therefore, for fixed K, K-DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K-DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question.http://doi.org/10.1103/PhysRevResearch.6.043279 |
| spellingShingle | Júlia Barberà-Rodríguez Nicolas Gama Anand Kumar Narayanan David Joseph Finding dense sublattices as low energy states of a Hamiltonian Physical Review Research |
| title | Finding dense sublattices as low energy states of a Hamiltonian |
| title_full | Finding dense sublattices as low energy states of a Hamiltonian |
| title_fullStr | Finding dense sublattices as low energy states of a Hamiltonian |
| title_full_unstemmed | Finding dense sublattices as low energy states of a Hamiltonian |
| title_short | Finding dense sublattices as low energy states of a Hamiltonian |
| title_sort | finding dense sublattices as low energy states of a hamiltonian |
| url | http://doi.org/10.1103/PhysRevResearch.6.043279 |
| work_keys_str_mv | AT juliabarberarodriguez findingdensesublatticesaslowenergystatesofahamiltonian AT nicolasgama findingdensesublatticesaslowenergystatesofahamiltonian AT anandkumarnarayanan findingdensesublatticesaslowenergystatesofahamiltonian AT davidjoseph findingdensesublatticesaslowenergystatesofahamiltonian |