Efficient lattice Hamiltonian encoding for the shortest vector problem
File(s)
Published version
Author(s)
Schirman, Eden
Ling, Cong
Mintert, Florian
Type
Journal Article
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.
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.
Date Issued
2026-10-01
Date Acceptance
2026-09-11
Citation
Physical Review Research, 2026, 8 (4)
ISSN
2643-1564
Publisher
American Physical Society
Journal / Book Title
Physical Review Research
Volume
8
Issue
4
Copyright Statement
© 2026 The Author(s). Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
License URL
Identifier
10.1103/zv7d-3vbv
Publication Status
Published
Article Number
043002
Date Publish Online
2026-10-02