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. 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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:mi>K</a:mi></a:math>-Densest Sublattice Problem (<b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mi>K</b:mi></b:math>-DSP): to find the densest <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"><c:mi>K</c:mi></c:math>-dimensional sublattice of a given lattice. We formulate <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"><d:mi>K</d:mi></d:math>-DSP as finding the first excited state of a <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"><e:mrow><e:mi>Z</e:mi></e:mrow></e:math>-basis Hamiltonian, making <f:math xmlns:f="http://www.w3.org/1998/Math/MathML"><f:mi>K</f:mi></f:math>-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 <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"><g:mrow><g:mi>O</g:mi><g:mo>(</g:mo><g:mi>K</g:mi><g:msup><g:mi>N</g:mi><g:mn>2</g:mn></g:msup><g:mo>)</g:mo></g:mrow></g:math> qubits suffice for solving <h:math xmlns:h="http://www.w3.org/1998/Math/MathML"><h:mi>K</h:mi></h:math>-DSP for <i:math xmlns:i="http://www.w3.org/1998/Math/MathML"><i:mi>N</i:mi></i:math>-dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm <j:math xmlns:j="http://www.w3.org/1998/Math/MathML"><j:mi>K</j:mi></j:math>-DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of <k:math xmlns:k="http://www.w3.org/1998/Math/MathML"><k:mi>K</k:mi></k:math>-DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on <l:math xmlns:l="http://www.w3.org/1998/Math/MathML"><l:mi>K</l:mi></l:math>-DSP. We devise a quantum algorithm that solves <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"><m:mi>K</m:mi></m:math>-DSP with runtime exponent <n:math xmlns:n="http://www.w3.org/1998/Math/MathML"><n:mrow><n:mo>(</n:mo><n:mn>5</n:mn><n:mi>K</n:mi><n:mi>N</n:mi><n:msub><n:mo form="prefix">log</n:mo><n:mn>2</n:mn></n:msub><n:mi>N</n:mi><n:mo>)</n:mo><n:mo>/</n:mo><n:mn>2</n:mn></n:mrow></n:math>. Therefore, for fixed <p:math xmlns:p="http://www.w3.org/1998/Math/MathML"><p:mi>K</p:mi><p:mo>,</p:mo><p:mo> </p:mo><p:mi>K</p:mi></p:math>-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 <q:math xmlns:q="http://www.w3.org/1998/Math/MathML"><q:mi>K</q:mi></q:math>-DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on <r:math xmlns:r="http://www.w3.org/1998/Math/MathML"><r:mi>K</r:mi></r:math> can be lowered remains an open question. Published by the American Physical Society 2024