Efficient Lattice Hamiltonian Encoding for the Shortest Vector Problem

Abstract: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.

arXiv:2307.12047 [quant-ph]

(or arXiv:2307.12047v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2307.12047 Focus to learn more arXiv-issued DOI via DataCite

https://doi.org/10.1103/zv7d-3vbv Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.