# On finding dense sub-lattices as low energy states of a quantum Hamiltonian

Júlia Barberà Rodríguez  ICFO-Institut de Ciències Fotòniques, The Barcelona
Institute of Science and Technology,
Av. Carl Friedrich Gauss 3, 08860 Castelldefels (Barcelona), Spain  SandboxAQ,
Palo Alto, California, USA  Nicolas Gama  SandboxAQ, Palo Alto, California,
USA  Anand Kumar Narayanan  SandboxAQ, Palo Alto, California, USA  David
Joseph  SandboxAQ, Palo Alto, California, USA

###### Abstract

Lattice-based cryptography has emerged as one of the most prominent candidates
for post-quantum 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 non-zero 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 Sub-lattice Problem ($K$-DSP): to find the densest $K$-dimensional
sub-lattice 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 reason to build post-quantum cryptography on
$K$-DSP. We devise a quantum algorithm that solves $K$-DSP with run-time
exponent $(5KN\log{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.

††preprint: APS/123-QED

##  I Introduction

In 1994, Shor revolutionized quantum computing and cryptography by devising
quantum algorithms that solve prime factorization and discrete logarithm in
polynomial time [1] using a fault-tolerant quantum computer. These problems
are believed to be intractable on classical computers. Consequently, most
public-key cryptographic protocols were built on such hardness assumptions [2,
3].

The emergence of fault-tolerant quantum computers that can run Shor’s
algorithm poses an imminent threat to public-key cryptography based on
factoring or discrete logarithms. As a preventive measure, post-quantum
cryptography (PQC) is being developed with urgency, spurred on by initiatives
by the National Institute of Standards and Technology (NIST). Post-quantum
cryptography is built on problems believed to be hard even on fault-tolerant
quantum computers. Within PQC, lattice-based cryptography (LBC) [4] is
considered to be one of the most promising solutions to build quantum-safe
primitives [5]. This is also supported by complexity theoretic hardness
reductions [6], as well as the failure of the best-known quantum algorithmic
methods in breaking lattice-based problems.

Public-key encryption schemes based on lattices were pioneered by Ajtai [7],
and put on sound complexity theoretic footing by Regev [6]. The Shortest
Vector Problem (SVP) is to find the shortest non-zero vector of a given
lattice. Regev based his schemes on the Learning With Errors (LWE) problem,
the dual problem to the SVP. The security of these systems is supported by a
worst-case to average case reduction from SVP to LWE like problems. Thus, the
hardness of SVP like problems is the foundation of LBC. Since then, there has
been a long line of LBC research leading to soon-to-be-standardized schemes
such as Kyber, Dilithium, and Falcon [8, 9, 10].

The $K$-Densest Sub-lattice Problem ($K$-DSP) seeks the densest sub-lattice of
a prescribed dimension $K$ within a given lattice. It is a generalization of
the SVP, since SVP is merely $1$-DSP. Being a generalization, $K$-DSP is at
least as hard as the SVP, but has received much less attention. While the
primary focus of finding dense sub-lattices lies in cryptography [11], it also
holds relevance in communication and information theory [12], as well as in
crystallography [13].

The best-known classical algorithms for solving SVP start with classical
reduction algorithms such as the LLL algorithm [14] and perform enumeration or
sieving. Enumeration algorithms started with Pohst [15] and Kannan [16], and
have evolved to be the best-known algorithms for SVP (see [17] and the
references therein).

Despite considerable interest, it is not clear if these sophisticated
classical algorithms can be sped up meaningfully on a fault-tolerant quantum
computer. However, the current interest is in designing quantum algorithms in
the Noise Intermediate Scale Quantum (NISQ) era [18], with limited qubits that
are extremely sensitive to noise and very susceptible to decoherence effects.
In this context, there is a necessity to develop hardware and quantum
algorithms that are able to work properly even in the presence of noise [19].
Within this framework, Variational Quantum Algorithms (VQAs) emerge as one of
the most encouraging approaches [20]. These algorithms rely on running a
parametrized quantum circuit on a quantum computer, and perform classical
optimization afterwards to update the parameters of this circuit.

The best known classical algorithms for $K$-DSP is due to Dadush-Micciancio
and for $K=\Theta(N)$ has a significantly worse complexity $K^{O({KN})}$ than
SVP solvers [21]. There have been previous works on mapping the SVP into one
of finding low energy states of a Hamiltonian. Shorts vectors in the lattice
map to eigenstates of the Hamiltonian with eigenvalues corresponding to the
vector lengths. In [22], the Bose-Hubbard Hamiltonian is used to solve the SVP
via adiabatic quantum computation. Since their lowest energy state is the zero
vector, the first excited state is the target of the algorithm. The results
show that, outside the adiabatic regime and for up to 4-dimensional lattices,
the solution for the SVP can be found with the same probability as the ground
state or the second excited state. Two quantum algorithms are also proposed in
[23], where the authors consider the mapping of the SVP now into Ising
coefficients which result in Hamiltonians that are more reusable in the
context of gate model computers and certain annealer architectures. These
algorithms are limited to low-dimensional lattices. A different approach with
results for up to 28-dimensional lattices is presented in [24], employing the
Ising spin Hamiltonian mapping followed by a Variational Quantum Eigensolver
(VQE). See [25, 26, 27, 28] for additional quantum SVP-solving approaches.

####  I.0.1 Contribution

We construct a Hamiltonian from the input lattice whose eigenstates correspond
to sub-lattices (of dimension at most $K$) with eigenvalues proportional to
the covolumes of the sub-lattices. The ground energy eigenstates correspond to
sub-lattices of dimension less than $K$. The solution to the $K$-DSP are the
first excited states, corresponding to $K$-dimensional sub-lattices of the
lowest covolume. Through this Hamiltonian correspondence a variety of quantum
algorithms ranging from adiabatic quantum computing to QAOA may be invoked to
solve $K$-DSP. Such generality means that this Hamiltonian formulation can be
useful in NISQ scenarios where VQA and QAOA type approaches yield the best
results, as well as in adiabatic systems, which may represent the most
challenging engineering milestones in developing fault-tolerant quantum
computation. For quantum algorithms that demand that the solutions to $K$-DSP
be encoded as the lowest energy eigenstate, we present a way to penalize the
ground states (fewer than $K$-dimensional sub-lattices) of the original
Hamiltonian. To tune the penalization accurately, we resort to estimating the
spectral gap of the Hamiltonian.

The difficulty of lattice problems such as the SVP or $K$-DSP are not
intrinsic to the input lattice, but may depend on the basis through which the
input lattice is presented. We present a classical polynomial time algorithm
that takes the input basis and preprocesses it to be suitable for being solved
using quantum algorithms. In the simplest case, this preprocessing merely LLL-
reduces the input basis and feeds it to the quantum algorithm. The LLL-reduced
basis is a basis for the same input lattice, but is better shaped to aid in
the low energy eigenstate search. In general, the preprocessing is far more
intricate and may only call the quantum algorithm on a carefully chosen lower
dimensional instance of $K$-DSP. With the preprocessing, we prove that
$O(KN^{2})$ qubits suffice for constructing the $K$-DSP Hamiltonian for $N$
dimensional input lattices with the assurance that the solution is contained
in the span of the qubits (see Theorem 1). A key technical insight that leads
to the bound is the invariance of the densest sub-lattice under LLL-reduction.
In particular, there is always a solution that is part of an LLL-reduced
basis. With the number of qubits bounded, we may invoke quantum algorithms
such as Grover search [29], phase estimation followed by amplitude
amplification [30], and quantum Gibbs sampling [31] to find a low energy
state. These algorithms at the minimum come with a quadratic speedup over
exhaustive search, but we may hope for more. The prospect of using quantum
Gibbs sampling is particularly enticing, since there is recent work proving
that low energy states of sparse (local) Hamiltonians drawn from random
ensembles can be found efficiently [32]. We do not expect cryptographic
instances of lattice problems to fall within these ensembles, but further
investigation is warranted before speculation. In particular, are there
natural ensembles of lattice problems, perhaps arising in chemistry or digital
communication for which quantum Gibbs sampling finds densest sub-lattices
fast? The aforementioned quantum algorithms require fault-tolerant quantum
computers. When constrained to NISQ devises, we can look to VQAs such as QAOA
to find the low energy states. We empirically investigate the performance of
QAOA in small dimensions in Section IV.

We finally investigate the hardness of $K$-DSP as $K$ increases. Hardness
cannot decrease with $K$, since $K_{1}$-DSP can be embedded into $K_{2}$-DSP
for $K_{2}>K_{1}$ by appending short orthogonal basis vectors. But how much
harder is $K$-DSP for large $K$, in particular, when $K$ approaches half the
ambient dimension? If the best known $K$-DSP algorithms take significantly
longer than the SVP algorithms, then there is cause to base post-quantum
cryptosystems on $K$-DSP. A natural way to address this question is to try to
solve $K$-DSP given oracle access to an SVP solver. The best known SVP
solvers, classical or quantum, take exponential time in the lattice dimension.
With an SVP solver, we observe that the input to quantum algorithms can be
preprocessed to be an HKZ-basis, a stronger guarantee than an LLL-basis.
Exploiting this stronger structure, we devise a quantum algorithm that solves
$K$-DSP with run-time exponent $(5KN\log{N})/2$ (see Theorem 2). Therefore,
for fixed $K$, $K$-DSP is no more than polynomially harder than the SVP. Our
algorithm is close in spirit to the aforementioned best known classical
$K$-DSP algorithm by Dadush and Micciancio. In comparison, our run-time
exponent is worse by a small constant. But our algorithm is simpler in the
sense of not requiring recursive calls to the SVP oracle. Whether the
exponential dependence on $K$ can be reduced remains an important open
question.

In Section II, we introduce relevant theoretical concepts regarding lattices
and quantum algorithms. In Section III, we describe the mapping of the Densest
Sub-lattice Problem to one of finding low energy states of a Z spins
Hamiltonian. We also prove bounds on the quantum resources and then develop an
approach to penalize trivial solutions by computing an upper bound on the
spectral gap. In Section IV, we simulate a $2$-DSP quantum solver and present
the results obtained. Finally, Section V discusses the conclusions and
potential directions for future research.

##  II Preliminaries

###  II.1 Lattices

A lattice is simply a pattern of repeating points in $N$-dimensional space,
for example, a section of the integer lattice in 3 dimensions is visualized in
Fig. 1. More formally, we define a lattice as a discrete free
$\mathbb{Z}$-sub-module of the real space $\mathbb{R}^{N}$ for some finite
dimension $N$, endowed with the Euclidean metric. The dimension of the lattice
is its rank as a $\mathbb{Z}$-module, which is at most $N$. A lattice of
dimension $r\leq N$ can be described by an ordered basis
$B=(\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{r})\subset\mathbb{R}^{n}$
of $\mathbb{R}$-linearly independent vectors, presented in our algorithms as
the matrix $\mathbf{B}$ consisting of basis vectors as the rows. Throughout,
we represent vectors as row vectors. The lattice generated by $\mathbf{B}$ is
the integer linear combinations
$\mathcal{L}(\mathbf{B}):=\sum_{i=1}^{N}x_{i}\mathbf{b}_{i}=\\{\mathbf{x}\mathbf{B}\mid\mathbf{x}\in\mathbb{Z}^{N}\\}$
of the basis vectors.

The computational complexity of the problems we study is not intrinsic to the
input lattice but may depend on the choice of basis generating the input
lattice. One notion that helps solve these problems faster is that of a ‘good’
basis. Informally, a basis that contains only short and nearly orthogonal
vectors is said to be a good basis. On the contrary, a bad basis consists of
long vectors with large colinearities. A lattice has infinitely many bases,
including a small number of good ones and a very large number of bad ones.

The LLL algorithm [14] is a powerful polynomial time lattice reduction
technique that transforms a given basis of a lattice into a “better” basis for
the same lattice, consisting of shorter basis vectors. Nevertheless, the basis
returned is not good enough to solve the SVP. Such vectors that correspond to
the output that LLL-reduction provides satisfy Lovász condition. This involves
a bound on the Gram-Schmidt basis lengths $(\mathbf{b}_{i}^{*})$.

The fundamental parallelepiped of a basis $(\mathbf{B})$ is defined as
$P(\mathbf{B}):=\\{\mathbf{x}\mathbf{B}|\mathbf{x}\in\left[0,1)\right.^{N}\\}$.
The covolume
$\text{vol}\left(\mathcal{L}(\mathbf{B})\right):=\sqrt{\text{det}(\mathbf{B}\mathbf{B}^{T})}$
of the fundamental parallelepiped only depends on the lattice
$\mathcal{L}(\mathbf{B})$ and is invariant of the choice of the basis. It is
known as the covolume of the lattice. The Gram matrix of a basis $\mathbf{B}$,
is given by $\mathbf{G}=\mathbf{B}\mathbf{B}^{T}$ with
$\mathbf{G}_{ij}=\mathbf{b}_{i}\mathbf{b}_{j}^{T}$ being the entries of the
matrix.

One of the most widely studied computational problem on lattices is the
Shortest Vector Problem, or SVP.

######  Definition 1.

(The Shortest Vector Problem). Given a basis
$\mathbf{B}=(\mathbf{b}_{1},...,\mathbf{b_{N}})$ of a lattice
$\mathcal{L}(\mathbf{B})$, find the shortest non-zero vector

$\arg\min_{z}\\{\lvert\lvert
z\rvert\rvert_{2}:z\in\mathcal{L}(\mathbf{B})\backslash\\{0\\}\\}.$ (1)

with respect to the Euclidean norm.

Let $\lambda_{1}(\mathcal{L}):=\min_{z}\\{\lvert\lvert
z\rvert\rvert:z\in\mathcal{L}\backslash\\{0\\}\\}$ denote the length of the
shortest vector. Minkowski’s theorem [33] gives an upper bound on
$\lambda_{1}(\mathcal{L})$. A Euclidean ball $S\subset\mathbb{R}^{N}$ of
volume $\textnormal{vol}(S)>2^{N}\sqrt{\textnormal{vol}(\mathcal{L})}$
contains at least one lattice point in $\mathcal{L}$ that is not the origin.
Then,
$\lambda_{1}(\mathcal{L})\leq\sqrt{N}\textnormal{vol}(\mathcal{L})^{1/2N}$.
Note that, the LLL-algorithm cannot find a vector within the Minkowski bound
efficiently.

The SVP plays a significant role in PQC since it is known to be NP-hard under
randomized reductions [34]. Consequently, some primitives in LBC use short
vectors. Since the SVP has been of interest for the cryptology community, many
generalizations have arisen from it. One of them is the Densest Sub-lattice
Problem, which seeks the densest $K$-dimensional sub-lattice of an arbitrary
lattice. This problem was initially introduced in [35], and subsequently
Dadush and Miccancio developed the fastest classical algorithm for it [21].

######  Definition 2.

(The Densest Sub-lattice Problem [35]). Given a basis
$\mathbf{B}=(\mathbf{b}_{1},...,\mathbf{b}_{N})$ that describes a lattice
$\mathcal{L}$, and an integer $K$ such that $1\leq K\leq N$, find a
$K$-dimensional sub-lattice $\mathcal{\hat{L}}\subseteq\mathcal{L}$ such that
$\textnormal{vol}(\mathcal{\hat{L}})$ is minimal.

Rankin’s constants [11] $\gamma_{N,K}(\mathcal{L})$ are a generalization of
Minkowski’s bound, and are defined as

$\gamma_{N,K}(\mathcal{L})=\textnormal{sup}_{\mathcal{L}}\left(\min\frac{\textnormal{det}((\mathbf{b}_{1},...,\mathbf{b}_{K}))}{\textnormal{det}(\mathcal{L})^{K/N}}\right)^{2}.$
(2)

They can be interpreted as a bound on the densest sub-lattice covolume.

######  Example 1.

(DSP for $N=3$ and $K=2$). Assuming that we are given a $3$-dimensional input
basis and that $K=2$, the algorithm should return the two vectors that span
the $2$-dimensional densest sub-lattice. This example is represented in Fig.
1, where the red vectors represent the input and one solution of the problem
could be given by the blue vectors. In this scenario, the input basis is

$\mathbf{B}=\begin{bmatrix}1&1&0\\\ 0&-1&-1\\\ 0&0&1\end{bmatrix}$

and a solution for the 2-DSP is given by

$\hat{\mathbf{B}}=\begin{bmatrix}0&-1&0\\\ -1&0&0\end{bmatrix}$

embedded in the 2-dimensional subspace spanned by the $x,y$ axes. Here, the
rows of the transformation matrix $\mathbf{X}$ are defined by
$\mathbf{X}=\\{(0,1,1),(-1,-1,0)\\}$.

Figure 1: Representation of the 2-Densest Sub-lattice Problem for $N=3$. The
red arrows represent a 3D input bad basis. One solution of the problem for
$K=2$ is given by the blue short vectors that span a 2D square lattice.

Notice that, the $1$-dimensional densest sub-lattice of an arbitrary lattice
is equivalent by definition to the SVP. The other extreme, the $(N-1)$-DSP, is
analogous to the SVP on the dual basis. In fact, for every $K$, the $K$-DSP
restricted to $K$ is at least as hard as the SVP. Furthermore, we know that
$K=N/2$ is the hardest instance since we can always add orthogonal vectors to
the input basis and use a half-volume oracle to solve any $K$-DSPK,N. The best
known algorithms for $K$-DSP with $K$ close to $N/2$ have $N^{2}$ in the
runtime exponent, while SVP enumeration algorithms only have an $N$.

###  II.2 Variational quantum algorithm

Figure 2: Representation of the quantum circuit for the QAOA. The initial
state is a superposition of all possible configurations. Then, $p$ layers are
applied, each of them composed of the cost Hamiltonian $H$, which separates
the states by their phase, and the rotation operator with the mixer
Hamiltonian ($H_{M}$) in the exponent, transforming the phase into amplitude.
In the end, the states of the qubits are measured, the output is post-
processed, and the cost function is calculated using the initial parameters
$(\bm{\gamma},\bm{\beta})$. Afterwards, the angles are updated and the process
is repeated until convergence.

Classical computers are unable to solve certain problems efficiently. For
certain classes of problems, like period finding, we know large fault-tolerant
quantum computers will offer speedups, and for other classes, we suspect they
can offer speedups but have no guarantees. In the near term, however, these
devices are not expected to be fault-tolerant. One approach to attempt quantum
advantage in the NISQ era is Variational Quantum Algorithms (VQAs).

The basic procedure for VQAs is the following:

  1. 1.

Prepare an initial state with $n$ available qubits $|0\rangle^{n}$.

  2. 2.

Apply a sequence of unitary gates to construct the ansatz
$|\psi(\bm{\theta})\rangle=U_{p}(\bm{\theta}_{p}),...,U_{1}(\bm{\theta}_{1})|0\rangle^{n}$.

  3. 3.

Evaluate a cost function $C(\bm{\theta})$.

  4. 4.

Update parameters $\bm{\theta}$ via classical optimization to minimize the
cost function $C(\bm{\theta})$.

  5. 5.

Repeat the process many times until convergence. The output of the algorithm
is the parameterized quantum circuit defined by the optimal parameters.

  6. 6.

Sample from the trained parameterized quantum circuit to obtain candidate
solutions.

Picking an ansatz depends on a variety of factors, including resources
available, the structure of the problem under consideration, and others. The
cost function is designed so that it is minimized at the optimal solution,
thus optimizing towards the minimum cost will result in a high probability of
sampling good solutions.

However, it is important to remark one of the main limitations of VQAs:
Barren-Plateaus phenomenon [36]. It consists of an effect produced when the
gradient vanishes in the classical optimization process. As a consequence, the
algorithm is not able to find the solution and the process can get trapped in
local minima.

One of the most widely used VQAs is the Quantum Approximate Optimization
Algorithm (QAOA) [37]. Given a cost Hamiltonian that encodes the solution of a
combinatorial optimization problem in its ground state, the purpose of the
algorithm is to return an approximate solution to the problem. It has been
shown that for low-depth QAOA, speedups can be achieved in comparison to
classical algorithms for certain instances [38]. The QAOA Hamiltonian
integrates the principles of the Transverse Ising model [39] and the $Z$-cost
Hamiltonian. The Transverse Ising model represents a system of interacting
spins in the presence of a transverse field induced by Pauli-$X$ operators.
The spins are influenced by the Ising coupling term and the transverse field.
Thus, the Hamiltonian can leverage from the interaction between the spins and
the transverse field to explore the solution space efficiently. In contrast,
the $Z$-cost Hamiltonian drives the system towards optimal solutions by
manipulating the quantum state based on the cost function.

Concretely, in the case of QAOA for solving problems in the Transverse Ising
model, one starts with an initial state $|\psi_{0}\rangle$, usually a
superposition of all possible solutions as represented in Fig. 2. Then, a
sequence of two unitary operators $U(C,\gamma)=\exp{(-i\gamma H)}$ and
$U(B,\beta)=\exp{(-i\beta\sum_{i=1}^{n}X_{i})}$, generated by the cost
Hamiltonian and the mixer Hamiltonian, are applied $p$ times. The
parameterized quantum circuit simulation allows us to evolve the quantum
system under the action of the two unitaries defined, $p$ times. At the end of
this process, the state of the qubits is measured, and the cost is updated.
After each iteration, the angles $(\bm{\gamma},\bm{\beta})$ are adjusted and
all the steps are repeated until convergence of the cost function. When
increasing $p$, the quality of the approximation of the final state to the
ground state of the cost Hamiltonian is enhanced. In the limit
$p\rightarrow\infty$, the algorithm provides a precise emulation of the
adiabatic quantum algorithm thus achieving overlap with the ground state close
to 1.

##  III A quantum algorithm for the Densest Sub-lattice Problem

In [21] it is shown that if $\mathcal{L}$ is an $N$-dimensional lattice,
$\mathcal{\hat{L}}\subseteq\mathcal{L}$ a $K$-dimensional sub-lattice of
minimum determinant and $\mathbf{v}\in\mathcal{L}$ be any lattice vector,
then, either $\mathcal{\hat{L}}$ contains all shortest lattice vectors or the
length of all vectors that span the densest sub-lattice is bounded by
$\lambda_{K}(\mathcal{\hat{L}})\leq K\lambda_{1}(\mathcal{L})$. This lemma
enables to develop a classical enumerative algorithm for the $K$-DSP with
exponential running time $K^{O(KN)}$.

In this section, we derive the mapping of the Densest Sub-lattice Problem to a
$Z$ spins Hamiltonian such that its first excited state $E_{1}$ corresponds to
the densest sub-lattice of a given ambient lattice. We also provide the space
requirements for the quantum algorithm, as well as an approach to penalize
trivial solutions of the $K$-DSP by upper-bounding the spectral gap.

###  III.1 Hamiltonian formulation for the $K$-DSP

Given a basis $\mathbf{B}$ that describes a $N$-dimensional lattice
$\mathcal{L}$, we seek $K$-linearly independent vectors
$\mathbf{v}_{1},...,\mathbf{v}_{K}$ that span a sub-lattice
$\mathcal{\hat{L}}\subseteq\mathcal{L}$ with the smallest determinant.

Let us consider that $K=2$, for simplicity, and that $N$ can take any value.
Nevertheless, one can see Appendix A for the formulation of the $K$-DSP for
$K=3$. Then, the goal is to find two linearly independent vectors that span
the densest sub-lattice, or equivalently, find the $2$-dimensional sub-lattice
with the smallest covolume or determinant. Thus, we can express these two
lattice points as a linear combination of input basis vectors such that

$\displaystyle\mathbf{v}_{1}$
$\displaystyle=\mathbf{x}\mathbf{B}=x_{1}\mathbf{b}_{1}+...+x_{N}\mathbf{b}_{N},$
$\displaystyle\vspace{5mm}\mathbf{v}_{2}$
$\displaystyle=\mathbf{y}\mathbf{B}=y_{1}\mathbf{b}_{1}+...+y_{N}\mathbf{b}_{N}.$
(3)

Recall that the Gram matrix is a square matrix for any $K$ and $N$. The
Gramian, which is the determinant of the Gram matrix, is equal to the covolume
squared of a lattice $\mathcal{L}$,

$\text{vol}(\mathcal{L})=\sqrt{\text{det}(\mathbf{G(\mathbf{b}_{1},...,\mathbf{b}_{N})})}.$
(4)

Therefore, the covolume of a sub-lattice $\mathcal{\hat{L}}$ of dimension
$K=2$ of an $N$-dimensional ambient lattice $\mathcal{L}$ can be expressed as

$\text{vol}(\mathcal{\hat{L}})^{2}=\begin{vmatrix}\langle\mathbf{v}_{1}|\mathbf{v}_{1}\rangle&\langle\mathbf{v}_{1}|\mathbf{v}_{2}\rangle\\\
\langle\mathbf{v}_{2}|\mathbf{v}_{1}\rangle&\langle\mathbf{v}_{2}|\mathbf{v}_{2}\rangle\end{vmatrix}.$
(5)

Using Eq. (3) in the former determinant, the following relation is obtained
between the covolume of the sub-lattice and the coefficients $\mathbf{x}$ and
$\mathbf{y}$,

$\text{vol}(\mathcal{\hat{L}})^{2}=\sum_{i,j,k,l}^{N}x_{i}x_{j}y_{k}y_{l}(\mathbf{G}_{ij}\mathbf{G}_{kl}-\mathbf{G}_{ik}\mathbf{G}_{jl}).$
(6)

The different inner products $\mathbf{b}_{i}\mathbf{b}_{j}$ have been written
as $\mathbf{G}_{ij}$ and therefore, are constants given as inputs of the
algorithm.

The main goal of the problem is to find the integer variables $x_{i}$ and
$y_{j}$ such that they minimize Eq. (6). This equation simulates the cost
function and returns the different covolumes that can be found within the
system. To transform the equation into a Hamiltonian we have to consider that
the eigenvalues must correspond to the energies of the system, which in this
context are the squared covolumes. Then, the eigenvectors of this Hamiltonian
are given by the different sub-lattices that can be constructed. In this way,
when applying the problem Hamiltonian over an eigenstate (i.e. a sub-lattice)
the energy returned will be the covolume squared of the configuration
considered. Note that, to be able to obtain the integer values that define the
coefficients in Eq. (6), the integer coefficients need to be modified to
binary variables.

In [23] the authors propose a qudit mapping that will be useful for the
simulation of our algorithm. The Binary-encoded qudits mapping allows to
interpret a binary string of qubits as integers. Let us assume that we have
four qubits per qudit available as in Fig. 3. Then, the Hilbert space of the
qudit operator will be spanned by $2^{4}$ states.

100101111010

000101010010

$Q\hskip 5.69054pt$$x_{1}$$x_{2}$$...$$x_{N}$$y_{1}$$y_{2}$$...$$y_{N}$

Figure 3: Diagram representing two $4\times N$ dimensional grids of qubits.
Each of them is associated with one of the vectors that span the sub-lattice
of dimension $K$. The columns of the 2D array represent the integer values
that can take each of the coefficients $x_{i}$ and $y_{j}$. The columns, each
of which represents a qudit, are composed of four qubits.

The measurements are performed in the computational basis $Z$, so return the
eigenvalue $+1(-1)$. Since we would like to work with binary strings, we can
transform the $Z$-basis to the $(0,1)$ basis, via the operator

$\hat{O}=\frac{\mathds{1}-Z}{2}.$ (7)

From $\hat{O}$ we can now construct the qudit operator

$\hat{Q}_{bin}^{(i)}=\sum_{w=0}^{m}2^{w}\hat{O}-2^{m}\mathds{1},$ (8)

where the first term contributes by returning the integer associated to the
$i^{th}$ qudit state when the operator is applied, and the second term is used
to shift the range down to be symmetric about zero and thus allow for negative
coefficients. Rearranging Eq. (8) using Eq. (7) we obtain

$\hat{Q}_{bin}^{(i)}=-\frac{\mathds{1}}{2}-\sum_{w=0}^{m}2^{w-1}Z_{wi},$ (9)

which translates the measured qubits of the grid’s columns to integers in the
range $[-2^{m},2^{m}-1]$.

Thus, the problem Hamiltonian for the $2$-DSP results in

$H_{2DSP}=\sum_{i,j,k,l=1}^{N}\hat{Q}^{(i)}\hat{Q}^{(j)}\hat{Q}^{(k)}\hat{Q}^{(l)}(\mathbf{G}_{ij}\mathbf{G}_{kl}-\mathbf{G}_{ik}\mathbf{G}_{jl})$
(10)

which comes from Eq. (6) when the coefficients $\bm{x},\bm{y}$ are replaced by
the qudits operators. Expanding the Hamiltonian for $K=2$ we obtain

$\displaystyle
H_{2DSP}=\sum_{i,j,k,l=1}^{N}2^{-4}\left[\sum_{a,b,c,d=0}^{m}2^{a+b+c+d}Z_{ai}Z_{bj}Z_{ck}Z_{dl}+\right.$
$\displaystyle\left.+\sum_{a,b,c=0}^{m}2^{a+b+c}(((Z_{ai}+Z_{aj})Z_{bk}+Z_{ai}Z_{bj})Z_{cl}+\right.$
$\displaystyle\left.+Z_{ai}Z_{bj}Z_{ck})+\sum_{a,b=0}^{m}2^{a+b}((Z_{ai}+Z_{aj}+Z_{ak})Z_{bl}+\right.$
$\displaystyle\left.+(Z_{ai}+Z_{aj})Z_{bk}+Z_{ai}Z_{bj}+\sum_{a=0}^{m}2^{a}(Z_{ai}+Z_{aj}+\right.$
$\displaystyle\left.+Z_{ak}+Z_{al})+1\right](\mathbf{G}_{ij}\mathbf{G}_{kl}-\mathbf{G}_{ik}\mathbf{G}_{jl}),$
(11)

which corresponds to a fully connected Hamiltonian, and has up to 4-body
interactions. The Eq. (11) is the one that will be used for the simulation of
the quantum $2$-DSP solver in Section IV.

To generalize the problem Hamiltonian to any $K$, consider the $K$-DSP for a
$N$-dimensional lattice spanned by
$\mathbf{B}=(\mathbf{b}_{1},...,\mathbf{b}_{N})$. The goal is to find
$K$-linearly independent vectors
$\hat{\mathbf{{B}}}=(\mathbf{v}_{1},...,\mathbf{v}_{K})$, which generate
$\mathcal{\hat{L}}$ with the smallest covolume. Here, the Gramian of
$\hat{\mathbf{{B}}}$ is given by

$\textnormal{det}(\mathbf{G}(\mathbf{v}_{1},...,\mathbf{v}_{K}))=\begin{vmatrix}\langle\mathbf{v}_{1},\mathbf{v}_{1}\rangle&\ldots&\langle\mathbf{v}_{1},\mathbf{v}_{K}\rangle\\\
\vdots&\ddots&\vdots\\\
\langle\mathbf{v}_{K},\mathbf{v}_{1}\rangle&\ldots&\langle\mathbf{v}_{K},\mathbf{v}_{K}\rangle\end{vmatrix}.$
(12)

The determinant of a $K\times K$ square matrix $\mathbf{A}$ with entries
$a_{ij}$, can be computed using Leibniz formula

$\textnormal{det}(\mathbf{A})=\sum_{\tau\in
S_{n}}sgn(\tau)\prod^{K}_{i=1}a_{i,\tau(i)},$ (13)

where the sum runs over all the permutations $\tau$ of the symmetric group
$S_{N}$, and $sgn\in\\{\pm 1\\}$ is the sign of $\tau$. One can write the
generalized covolume of a $K$-dimensional sub-lattice in terms of the
determinant of the rank $K$ Gram matrix, formed by the $K$ lattice vectors
returned

$\textnormal{vol}(\hat{\mathcal{L}})^{2}=\sum_{\tau\in
S_{N}}sgn(\tau)\prod^{K}_{i=1}\langle\mathbf{v}_{i},\mathbf{v}_{\tau(i)}\rangle.$
(14)

To encode the Hamiltonian of the general $K$-DSP, one can write the vectors
$\mathbf{v}_{i}$ in terms of the qudit operators

$H_{DSP}=\sum_{\tau\in
S_{N}}sgn(\tau)\prod^{K}_{i=1}\left(\sum^{N}_{\alpha,\beta=1}\hat{Q}^{(i)}_{\alpha}\hat{Q}^{(\tau(i))}_{\beta}\mathbf{G}_{\alpha,\beta}\right)$
(15)

where the operators $\hat{Q}^{(i)}_{\alpha}$ and $\hat{Q}^{(\tau(i))}_{\beta}$
act on the qudits $\alpha$ and $\beta$ within a register, and $i,\tau(i)$
index the qubit grids. Each qubit grid describes a single vector, two of which
are shown in Fig. 3. Here, $\mathbf{G}$ is the Gram matrix of the full
$N$-dimensional input basis $\mathbf{B}$. The output of this operation
consists of two integer values associated with the classical coefficients
$x_{i,\alpha}$ and $x_{\tau(i),\beta}$ that generate the solution vectors
$\mathbf{v}_{i}$ and $\mathbf{v}_{\tau(i)}$. The eigenenergies of $H_{DSP}$
are then the $\textnormal{vol}(\hat{\mathcal{L}})^{2}$ where the
$\hat{\mathcal{L}}$ is the sub-lattice corresponding to the relevant
eigenvector.

One appeal of using the Leibnitz formula for the determinant is that it gives
Hamiltonians that are 2$K$-local. Since even 3-local Hamiltonians are QMA-hard
[40], in the worst case, locality does not help in the computation of low
energy states. However, for local Hamiltonians drawn from certain natural
random ensembles, locality does seem to help [32]. To efficiently implement
the Hamiltonian, the summation over the symmetric group is done in
superposition. The operators inside the summation indexed by permutations are
implemented using conditional gates. An alternative to the Leibnitz formula is
to use a efficient arithmetic circuit to compute the determinant, such as the
one derived through Gaussian elimination.

###  III.2 Classical preprocessing and spatial bound

The coordinates of the unknown vectors (such as $\mathbf{x}$ and $\mathbf{y}$
in Eq. (III.1)) in the Hamiltonian formulation are apriori unbounded integers.
Therefore, the naive search space is countably infinite. To translate the
Hamiltonian formulation into a quantum algorithm, it is necessary to confine
the solution space to be finite, preferably small. In particular, this bounds
the number of qubits required by the algorithm. For the SVP, the Minkowski
bound readily confines the search space. For $K$-DSP with $K>1$, bounding the
search space is far more intricate. We devise a polynomial-time classical
preprocessing algorithm to resolve this problem.

The classical preprocessing algorithm takes a lattice basis $\mathbf{B}_{in}$
as the input and outputs a preprocessed gap-free basis $\mathbf{B}_{P}$ in
polynomial time. First, it runs the LLL algorithm on $\mathbf{B}_{in}$ to get
another basis $\mathbf{B}_{L}$ generating the same lattice. This
$\mathbf{B}_{L}$ either has a gap or is gap-free. This notion of a Gap is one
that we define and can be tested in polynomial time 111An alternative
characterization of gap that can be found in the literature is between the
successive minima of the lattice, when there exists an index $p$ s.t
$\lambda_{p+1}(L)\gg\lambda_{p}(L)$. A lattice that has a gap larger than
$O(N^{1/2})$ according to one definition has a gap also with the other
definition and vice versa. . It is not intrinsic to a lattice and may depend
on the basis.

######  Definition 3.

(Gap). A basis $\mathbf{B}=(\mathbf{b}_{1},\ldots,\mathbf{b}_{N})$ is defined
to have a Gap if there exists an index $r$ such that,
$\max(||\mathbf{b}_{1}^{*}||,...,||\mathbf{b}_{r}^{*}||)<\min(||\mathbf{b}_{r+1}^{*}||,...,||\mathbf{b}_{N}^{*}||)$,
where $(\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{N})$ is result of the
Gram-Schmidt orthogonalization obtained from $\mathbf{B}$.

If $\mathbf{B}_{L}$ is a gap-free basis, the preprocessing algorithm outputs
$\mathbf{B}_{L}$ as $\mathbf{B}_{P}$. This is the typical case, since generic
lattices are gap-free as a consequence of Gaussian heuristic: the presence of
a gap would mean that at least one of its projected lattices has a shortest
vector much below the Gaussian heuristic, which is highly improbable. The
quality of the preprocessed basis $\mathbf{B}_{P}=\mathbf{B}_{L}$ is
quantified in Lemma 1.

######  Lemma 1 (Gap-free-LLL).

If a LLL-reduced basis $\mathbf{B}$ of $\mathcal{L}$ is gap-free, then
$||\mathbf{B}^{*}||\leq(4/3+\varepsilon)^{(N-1)/4}\textnormal{vol}(\mathcal{L})$

###### Proof.

Let $x_{i}$ denote the values of the $N$ norms $\mathbf{b}_{j}^{*}$ sorted by
increasing order. Then if there exists an index $p$ s.t.
$x_{p+1}>\sqrt{4/3}x_{p}$, let us paint in blue the indexes s.t.
$\|\mathbf{b}_{j}^{*}\|\leq x_{p}$ and in red those where
$\|\mathbf{b}_{j}\|\geq x_{p+1}$. Because of Lovász conditions [14], a red
index cannot be followed by a blue index in the basis, so the only viable
coloring is to have all the blue indexes followed by all the red indexes. Then
necessarily, $(\|\mathbf{b}_{1}^{*}\|,\dots,\|\mathbf{b}_{p}^{*}\|)$ are all
$\leq x_{p}$ and $(\|\mathbf{b}_{p+1}^{*}\|,\dots,\|\mathbf{b}_{N}^{*}\|)$ are
all $\geq x_{p+1}$, and the basis has a gap. Reciprocally, a gap-free LLL-
reduced basis satisfies $x_{i}\leq x_{i+1}\leq\sqrt{4/3}x_{i}$ for all
$i\in[1,N-1]$, and therefore, $x_{N}/(\prod
x_{j})^{1/N}=\max{\mathbf{b}_{j}^{*}}/\textnormal{vol}(\mathcal{L})^{1/N}\leq\left(\frac{4}{3}\right)^{(N+1)/4}$.
∎

If $\mathbf{B}_{L}$ is not a gap-free basis, we invoke Lemma 3 (which builds
on Lemma 2) to reduce the dimension of the problem in polynomial time. In
particular, Lemma 3 identifies a gap-free LLL-reduced basis as the
preprocessed basis $\mathbf{B}_{P}$ to be fed as the input to a $K$-DSP
problem in fewer dimension. Lemma 4 quantifies the quality of
$\mathbf{B}_{P}$.

######  Lemma 2 (Dual of sub-lattice).

Let $\mathcal{L}$ be a lattice and $\mathbf{B}$ its basis, and
$\hat{\mathcal{L}}\subseteq\mathcal{L}$ a sub-lattice of dimension $D$. Let
$K$ be the smallest index s.t. $\hat{\mathcal{L}}\subseteq
L(\mathbf{b}_{1},\dots,\mathbf{b}_{K})$, then there exists a basis
$\mathbf{C}=(\mathbf{c}_{1},\dots,\mathbf{c}_{D})$ of $\hat{\mathcal{L}}$ such
that $\|\mathbf{c}_{D}^{*}\|\geq\|\mathbf{b}_{K}^{*}\|$.

###### Proof.

There exists a $D\times K$ integer matrix $\mathbf{V}$ s.t.
$\mathbf{V}(\mathbf{b}_{1},\dots,\mathbf{b}_{K})$ is a basis of
$\hat{\mathcal{L}}$, furthermore, the last column of $\mathbf{V}$ is non-zero.
Let $\mathbf{V}^{\prime}$ be the Hermite normal form of $\mathbf{V}$, then
$\mathbf{C}=\mathbf{V}^{\prime}(\mathbf{b}_{1},\dots,\mathbf{b}_{K})$ is still
a basis of $\hat{\mathcal{L}}$, and $\mathbf{V}^{\prime}$ has a single non-
zero integer coefficient in its last column, in position $(D,K)$. It follows
that
$\texttt{span}(\mathbf{c}_{1},\dots,\mathbf{c}_{D-1})\subseteq\texttt{span}(\mathbf{b}_{1},\dots,\mathbf{b}_{K-1})$
and $\mathbf{c}_{K}=\mathbf{v}_{D,K}\mathbf{b}_{K}+\mathbf{t}$ where
$\mathbf{t}\in\texttt{span}(\mathbf{b}_{1},\dots,\mathbf{b}_{K-1})$.
Therefore,
$\|\mathbf{c}_{K}^{*}\|\geq\|\mathbf{v}_{D,K}\mathbf{b}_{K}^{*}\|\geq\|\mathbf{b}_{K}^{*}\|$.
∎

######  Lemma 3 (Gap-dimension-reduction).

If $\mathbf{B}$ is a basis of $\mathcal{L}$ and has a gap, then the $K$-DSP on
$\mathbf{B}$ reduces to a lower dimension for all $K$

###### Proof.

Assume that the input basis has a gap at index $p$ and call
$T=\max_{i\in[1,p]}{||\mathbf{b}_{i}^{*}||}$ and
$\mathbf{E}=\texttt{span}(\mathbf{b}_{1},\dots,\mathbf{b}_{p})$. Let
$(\mathbf{c}_{1},\dots,\mathbf{c}_{K})$ be a dual-HKZ-reduced basis [42] of a
sub-lattice with minimal covolume,
$\mathbf{F}=\texttt{span}(\mathbf{c}_{1},\dots,\mathbf{c}_{K})$, and let
$\pi_{K-1}$ be the projection on the orthogonal of
$\texttt{span}(\mathbf{c}_{1},\dots,\mathbf{c}_{K-1})$.

If $K\leq p$, we will prove that $\mathbf{F}\subseteq\mathbf{E}$. Suppose by
contradiction that this inclusion does not hold. In this case,
$\|\mathbf{c}_{K}^{*}\|$ is maximal across all bases, so by Lemma 2, it is
$>T$. Also, at least one of the vectors $\mathbf{b}_{1},\dots,\mathbf{b}_{p}$
is not in $\mathbf{F}$: it can either be a dimension argument if $p>K$, or due
to the non-inclusion assumption when $p=K$. So at least one of the
$\pi(\mathbf{b}_{i})$ is non zero. Let $j$ be the smallest of such index, we
therefore have $\|\pi(\mathbf{b}_{j})\|\leq\|\mathbf{b}_{j}^{*}\|\leq T$. If
we replace $\mathbf{c}_{K}$ with $\mathbf{b}_{j}$ in the basis $\mathbf{C}$,
we would obtain a sub-lattice of shorter covolume, which contradicts that
$\mathbf{C}$ is a $K$-DSP solution. Therefore,
$\mathbf{F}\subseteq\mathbf{E}$. If $K=p$, because $\mathbf{E}$ and
$\mathbf{F}$ have also the same dimension, they are equal, and
$\mathbf{b}_{1},\dots,\mathbf{b}_{p}$ is a solution of the $K$-DSP. If $K<p$,
we just proved that the $K$-DSP solution is a sub-lattice of
$(\mathbf{b}_{1},\dots,\mathbf{b}_{p})$, so we reduce the problem to a smaller
dimension. If $K>p$, we prove by duality that $\mathbf{E}\subset\mathbf{F}$,
so by projecting the input basis on the orthogonal of $\mathbf{E}$, we are
reduced to solve the smaller $(K-p)$-DSP on the $(N-p)$-dimensional projected
basis. ∎

######  Lemma 4 (Relative-basis-size).

If $\mathbf{B}$ and $\mathbf{C}$ are two bases of $\mathcal{L}$, and
$\mathbf{C}$ has a gap at index $K$, then
$\textnormal{vol}(\pi_{K}(\mathbf{C}))^{1/N-K}\leq||\mathbf{B}^{*}||$ where
$\pi_{K}$ is the orthogonal projection over
$(\mathbf{c}_{1},\dots,\mathbf{c}_{K-1})^{\perp}$.

###### Proof.

By definition, the family $\mathbf{F}=\pi_{K}(\mathbf{B})$ generates the same
lattice as $\pi_{K}(\mathbf{C})$, and
$\|\mathbf{F}^{*}\|\leq\|\mathbf{B}^{*}\|$. If we use the LLL algorithm on
$\mathbf{F}$, we obtain a basis $\mathbf{F^{\prime}}$ of $\pi_{K}(\mathbf{C})$
with $\|\mathbf{F^{\prime}}^{*}\|\leq\|\mathbf{B}^{*}\|$. In particular,
$\textnormal{vol}(\pi_{K}(\mathbf{C}))^{1/N-K}$ is the geometric mean of
$\|\mathbf{F^{\prime}}_{i}^{*}\|$, so
$\textnormal{vol}(\pi_{K}(C))^{1/N-K}\leq\|\mathbf{F^{\prime}}^{*}\|\leq\|\mathbf{B}^{*}\|$
∎

######  Corollary 1.

If $\mathbf{B}$ and $\mathbf{C}$ are two bases of $\mathcal{L}$ and
$\mathbf{C}$ is LLL-reduced, then
$||\mathbf{C}^{*}||\leq(4/3+\varepsilon)^{(N-1)/4}||\mathbf{B}^{*}||$.

###### Proof.

This is a consequence of the previous Lemma 4, when applied to the highest gap
of $\mathbf{C}$ if $\mathbf{C}$ has a gap, or the whole basis if $\mathbf{C}$
is gap-free. ∎

In the proof of Theorem 1, a key insight is that there is an output basis that
is a solution to $K$-DSP that is LLL-reduced, due to the invariance of $K$-DSP
solutions under LLL-iterations. Furthermore, irrespective of if the original
input basis $\mathbf{B}_{in}$ is gap-free, the output $\mathbf{B}_{P}$ of the
preprocessing is always LLL-reduced and gap-free. Therefore, both the input
basis $\mathbf{B}_{P}$ and the output basis $\mathbf{B}_{out}$ of the quantum
algorithm can be constrained to be LLL-reduced without loss of generality.
This structure, in concert with the quality assurance of the input basis
$\mathbf{B}_{P}$ from Lemmas 1 and 4 allows us to bound the qubits.

######  Lemma 5.

(Unimodular-transformation-bound) If $\mathbf{B}_{P}$ is a gap-free LLL basis
of $\mathcal{L}$ and $\mathbf{C}$ is an LLL-reduced basis of the same lattice,
then the unimodular transformation $\mathbf{U}$ s.t.
$\mathbf{U}\mathbf{B}_{P}=\mathbf{C}$ satisfies $\|\mathbf{U}\|_{\infty}\leq
N(4/3+\varepsilon)^{3(N-1)/4}.$

###### Proof.

Since $\mathbf{B}_{P}$ is an LLL-reduced gap-free basis, so is its (reversed)
dual $\mathbf{B}_{P}^{-t}$. Therefore, by Lemma 1, we have
$\|\mathbf{B}_{P}^{*}\|\leq(4/3+\varepsilon)^{(N-1)/4}\textnormal{vol}(\mathcal{L})$
and
$\|\mathbf{B}_{P}^{*-t}\|\leq(4/3+\varepsilon)^{(N-1)/4}\textnormal{vol}(\mathcal{L})^{-1}$.
By Corollary 1,
$\|\mathbf{C}^{*}\|\leq(4/3+\varepsilon)^{(N-1)/4}\|\mathbf{B}_{P}^{*}\|$. We
prove the Lemma by converting the Gram Schmidt norm to the spectral norm and
multiplying them together. ∎

The previous Lemma 5 allows us to bound the size of the unimodular
transformation $\mathbf{U}$ from the input basis to the output basis. The
entries of the matrix $\mathbf{U}$ consist of qubits, which are the target
coefficients we are seeking. Therefore, determining an upper limit on these
entries will enable us to bound the total number of qubits required for the
quantum solver.

######  Theorem 1.

(Bound on the number of qubits). Let $N$-dimensional lattice $\mathcal{L}$ be
the input to the quantum algorithm for the $K$-DSP as the span of a gap-free
LLL-reduced basis $\mathbf{B}_{P}=(\mathbf{b}_{1},...,\mathbf{b}_{N})$. Then,
a $KN^{2}$ qubit Hilbert search space is sufficient to ensure that at least
one exact solution of the $K$-DSP is contained.

###### Proof.

The worst case in number of qubits will occur when the input basis has no
gaps, since the dimension of the problem cannot be reduced. Let the input of
the quantum solver be a gap-free LLL-reduced basis of dimension $N$. If we
LLL-reduce a basis that is a solution of the $K$-DSP, it will still be a
solution to the problem. Therefore, there exists an LLL-reduced basis that is
the solution of the $K$-DSP.

A solution output basis can be denoted as $\mathbf{{B}}_{out}$ as

$\begin{bmatrix}\mathbf{v}_{1}\\\ \vdots\\\
\mathbf{v}_{K}\end{bmatrix}=\begin{bmatrix}x_{11}&x_{12}&\ldots&x_{1N}\\\
x_{21}&x_{22}&\ldots&x_{2N}\\\ \vdots&\vdots&\ddots&\vdots\\\
x_{K1}&x_{K2}&\ldots&x_{KN}\end{bmatrix}\begin{bmatrix}\mathbf{b}_{1}\\\
\vdots\\\ \mathbf{b}_{N}\end{bmatrix}.$ (16)

The linear system in Eq. (16) can also be expressed in terms of matrices as
$\mathbf{{B}}_{out}=\mathbf{X}\mathbf{B}_{P}$, where $\mathbf{{B}}_{out}$ and
$\mathbf{X}$ are $K\times N$ matrices, and $\mathbf{B}_{P}$ is an $N\times N$
matrix, considering the worst-case assumption. Then, we have the inequality
relating the infinity norm and the spectral matrix norm

$||\mathbf{X}||_{\infty}\leq||\mathbf{{B}}_{out}||_{sp}||\mathbf{B}_{P}^{-1}||_{sp},$
(17)

Hence, using the bound on the basis $\mathbf{B}_{P}$ and $\mathbf{{B}}_{out}$
that do not have a gap, and the inequality obtained in Lemma 5, we can write

$\displaystyle||\mathbf{X}||_{\infty}\leq
N\left(\frac{4}{3}+\varepsilon\right)^{3(N-1)/4}.$ (18)

The coefficients that describe the vectors that span the densest sub-lattice
must be bounded by $-2^{m}\leq x_{i}\leq 2^{m}-1$ for all $i=1,...,N$, where
$m$ are the qubits that suffice to represent the coefficients $x_{i}$.
Consequently, the total number of qubits can be expressed as

$n=K\sum_{i=1}^{N}m=K\sum_{i=1}^{N}\lfloor\log{2^{m}}\rfloor\leq
K\log{\prod_{i=1}^{N}2^{m}}.$ (19)

Using Eq. (18) we can write

$\displaystyle\prod_{i=1}^{N}2^{m}\leq\prod_{i=1}^{N}N\left(\frac{4}{3}+\varepsilon\right)^{3(N-1)/4}=$
(20) $\displaystyle=N^{N}\left(\frac{4}{3}+\varepsilon\right)^{3(N^{2}-N)/4}.$
(21)

Taking the logarithm of Eq. (21) and substituting into Eq. (19), we obtain
that
$\frac{3KN^{2}}{4}\log{\left(\frac{4}{3}+\varepsilon\right)}-\frac{3KN}{4}\log{\left(\frac{4}{3}+\varepsilon\right)}+N\log{N}$
qubits suffices to find the solution of the $K$-DSP using the quantum solver.
∎

We can calculate the run-time in the context of Groverization and considering
LLL preprocessing. However, the bound obtained can be reduced by allowing more
substantial reductions in the input basis. Therefore, we present the Grover
speedup for the latter case.

The pseudocode of the full algorithm for the $K$-DSP is provided in Algorithm
1, incorporates the preprocessing step, involving LLL reduction, and the QAOA
steps.

####  III.2.1 Preprocessing with an SVP oracle

If we are allowed to use an SVP oracle, we can detect if there exists a basis
with a gap in the lattice: it suffices to running dual-HKZ followed by HKZ
[42]. These alternative algorithms enable more powerful reductions of the
input basis, although they may require certain assumptions. Then, only the
gap-free case subsists in our Theorem, and it is possible to decrease the
$(4/3+\varepsilon)^{(N-1)/4}$ term that arises from the LLL-bound in Theorem
1. In particular, the number of qubits becomes $O(5KN\log{N})$, which is an
alternative construction of Dadush-Micciancio Lemma (see Appendix B for the
proof).

######  Theorem 2 (Runtime of Groverized Exhaustive Search).

Let $N^{5KN}$ be the size of the search space, and let $M$ be the number of
solutions in the space. Then, the runtime of Groverized exhaustive search for
finding a solution of the $K$-DSP is

$O\left(\frac{N^{5KN/2}}{\sqrt{M}}\right).$

###### Proof.

Consider the scenario where more powerful reduction algorithms are permitted
in the classical preprocessing step. Then, the number of qubits required to
ensure that at least one solution of the $K$-DSP is found within the search
space is $O(5KN\log{N})$, where $N$ and $K$ are the ambient lattice and the
densest sub-lattice dimensions, respectively. Consequently, the database
consists of $2^{5KN\log{N}}$ elements, which can also be expressed as
$N^{5KN}$. Drawing upon Grover’s algorithm for unstructured search [29], only
$O\left(N^{5KN/2}M^{-1/2}\right)$ queries are necessary to maximize the
probability of obtaining the target state, where $M$ is the number of
solutions. ∎

In Theorem 2, we establish that the runtime for Groverizing the exhaustive
search is bounded by $O\left(N^{5KN/2}M^{-1/2}\right)$. For the best-known
classical algorithm, the runtime is $O(K^{KN})$. When comparing both, we
observe that the runtime for the classical algorithm scales as
$2^{KN\log{K}}$, while the quantum algorithm has slightly worse performance
due to an additional logarithmic term in the exponent, resulting in
$2^{5KN\log{N}/2-1/2\log{M}}$. The observation that our quantum solver appears
moderately slower than the classical one could be attributed to certain
aspects of the proof. It is worth noting that, in certain scenarios, the Half-
Volume Problem is suspected to be easier than the Shortest Vector Problem
(SVP), particularly in the context of overstretched NTRU lattices [43, 10].
Therefore, one possible explanation for the presence of this extra term may be
linked to the slower preprocessing associated with the utilization of the SVP
oracle.

A similar run-time guarantee as in Theorem 2 is obtained when the first
excited states of the Hamiltonian are found using quantum Gibbs sampling [31].

###  III.3 Ground state penalization

As has been previously mentioned, the Hilbert space of the problem contains
trivial solutions such as the zero vector or sub-lattices spanned by linearly
dependent vectors. In this section, we propose a method to penalize the energy
of the trivial solutions, although many other approaches could be considered
[44]. The easiest way is to merely project into sub-space of non-trivial
solutions, since the sub-space of trivial solutions has a simple algebraic
characterization of having determinant zero. But this destroys the locality of
the Hamiltonian. There is an incentive to keep the locality, either for ease
of implementation or for run-time guarantees such as the one offered by
quantum Gibbs sampling [31, 32].

Let the problem Hamiltonian for the 2-Densest Sub-lattice Problem be the one
presented in Eq. (10). This Hamiltonian is a sum of up to 4-body hermitian
matrices. Its eigenvectors are the different sub-lattices that can be
generated with the available qubits of the problem, and the eigenvalues are
the squared covolumes of respective sub-lattices. Thus, the ground state space
of $H_{DSP}$, which corresponds to the eigenvalue 0, is composed of trivial
solutions such as the sub-lattice spanned by zero vectors and sub-lattices
spanned by $K$-linearly dependent vectors.

Algorithm 1 A quantum algorithm for the $K$-DSP

1:$\mathbf{B}_{in}\subseteq\mathcal{R}^{N}$, $K\colon
0<K<\textnormal{dim}(\mathbf{B}_{in})$

2:$\mathbf{B}_{out}\subseteq\mathcal{R}^{K}$ a linear subspace.

3:$\mathbf{B}_{L}\leftarrow$ Run LLL on $\mathbf{B}_{in}$

4:if $\mathbf{B}_{L}$ is gap-free then

5: $\mathbf{B}_{P}\leftarrow\mathbf{B}_{L}$

6:else if $\mathbf{B}_{L}$ has gaps then

7: By Lemma 3, reduce the dimension of the $K$-DSP

8: $\mathbf{B}_{P}\leftarrow\mathbf{B}_{L}\subseteq\mathcal{R}^{(N-p)}$

9:$n\leftarrow KN^{2}$

10:$\mathbf{G}\leftarrow\mathbf{B}_{P}\mathbf{B}_{P}^{T}$

11:procedure
MakeQaoa($H_{M},H_{DSP},\bm{\theta}\colon\mathrm{array},p\colon\mathrm{int}$)

12: $|\psi\rangle\leftarrow H^{\otimes n}|0\rangle^{\otimes n}$

13: for $t=1$ to $p$ do

14: $|\psi\rangle\leftarrow H_{M}H_{DSP}|\psi\rangle$

15: return $|\psi\rangle$

16:procedure TrainQaoa($|\psi\rangle\colon\mathrm{array}$)

17: $\textnormal{old}=0$

18: while True do

19: $|\psi\rangle\leftarrow\textsc{MakeQaoa}(\bm{\theta})$

20: $\bm{\theta}_{opt}\leftarrow$ Compute gradient of $C(\bm{\theta})$

21: $\textnormal{error}\leftarrow\langle\psi|C(\bm{\theta}_{opt})|\psi\rangle$

22: if $|\textnormal{error}-\textnormal{old}|<\textnormal{tol}$ then

23: break

24: $\textnormal{old}=\textnormal{error}$

25: return $\bm{\theta}_{opt}$

26:$\bm{\theta}_{opt}\leftarrow\textsc{TrainQaoa}(|\psi\rangle)$

27:$|\psi\rangle\leftarrow\textsc{MakeQaoa}(H_{M},H_{DSP},\bm{\theta}_{opt},p)$

28:$\mathbf{B}_{out}\leftarrow$ Measure $|\psi\rangle$ in the $Z$ basis and
post-processing

29:return $\mathbf{B}_{out}$

The main goal is to find the first excited state of $H_{DSP}$. Therefore, we
need to penalize somehow the ground state of the Hamiltonian. To achieve this,
we can add an extra term to the Hamiltonian, similarly to the Projection Lemma
in [45]. In this context, we can write

$H=H_{DSP}+re^{-sH_{DSP}},$ (22)

where $re^{-sH_{DSP}}$ corresponds to the penalizing term, and $r$ and $s$ are
positive constants to be determined.

The extra term has vanishingly small eigenvalues for excited configurations,
while its eigenvalue is equal to $1$ when considering trivial solutions.
Therefore, the eigenvalues of the total Hamiltonian $H$ for the excited state
space of $H_{DSP}$ are nearly the same as the eigenvalues of $H_{DSP}$.
However, the eigenvalues of $H$ for the ground state space of $H_{DSP}$ are
now $r$. Since $r$ and $s$ are parameters to be tuned, we can associate them
with a value such that the energy of the first excited state of $H_{DSP}$ is
lower than the energy of trivial configurations.

It is important to note several things here. Firstly, since the problem
Hamiltonian is Hermitian, it is also the case for the extra term and thus, for
the total Hamiltonian. Secondly, both terms of $H$ share the same
eigenvectors, so $H$ has the same eigenvectors as the $H_{DSP}$. Finally, the
addition of the second term implies that the Hamiltonian in Eq. (22) does not
need to be 4-body.

The Hamiltonian proposed in Eq. (22) has such a complex shape that cannot be
implemented using QAOA. Therefore, for the purpose of simulation, a second-
degree approximation could be considered such that

$H\approx r\mathds{1}+(1-rs)H_{DSP}+r\frac{s^{2}}{2}H_{DSP}H_{DSP}.$ (23)

This approximation is equivalent to considering $H=(H_{DSP}-E)^{2}$ with some
$E$ that depends on $r$ and $s$, together with an overall shift and re-
scaling. Thus, any of the formulations is feasible for the QAOA emulation.

###  III.4 Spectral gap bounding

The optimal values for $r$ and $s$, or an approximate value for $E$ need to be
determined to achieve such penalization. A tight lower bound on the spectral
gap would be enough to either tune the parameters or specify $E$. However,
proving lower bounds on the spectral gap is considered a hard problem. To
solve this issue, we can devise our algorithm with a promised spectral gap
$\epsilon_{DSP}$ as a parameter. The true spectral gap can be readily
estimated using binary search, by using the parameterized algorithm as an
oracle. In this scenario, the first excited state energy, which is equivalent
to the covolume squared of the densest sub-lattice, corresponds to the
spectral gap. Therefore, the upper limit of the binary search algorithm can be
set by bounding the Gramian composed of the set of vectors that span the
densest sub-lattice.

######  Lemma 6.

(Upper bound on the spectral gap of $H_{DSP}$). Let the input of the algorithm
be an $N$-dimensional LLL-reduced basis that defines a lattice $\mathcal{L}$.
Then, the spectral gap of the problem Hamiltonian $H_{DSP}$ is bounded by
$\Delta
E_{DSP}\leq\left(\frac{4}{3}+\varepsilon\right)^{K(N-1)}\textnormal{vol}(\mathcal{L})^{2K}$.

###### Proof.

From Rankin’s constant definition in Eq. (2),

$\textnormal{det}(\mathbf{G}(\mathbf{v}_{1},...,\mathbf{v}_{K}))\leq\gamma_{N,K}\textnormal{vol}(\mathcal{L})^{2K/N},$
(24)

since
$\textnormal{det}(\mathbf{G}(\mathbf{v}_{1},...,\mathbf{v}_{K}))=\textnormal{vol}(\hat{\mathcal{L}})^{2}$.
Rankin’s constants are upper bounded by

$\gamma_{N,K}\leq\left(\frac{\prod_{i=1}^{K}||\mathbf{v}_{i}||}{\textnormal{vol}(\mathcal{L})^{K/N}}\right)^{2},$
(25)

as shown in [46]. Previously mentioned, if we LLL-reduce a basis that is a
solution of the $K$-DSP, it remains a valid solution to the problem.
Therefore, there exists an LLL-reduced basis that is the solution of the
$K$-DSP. Hence, the length of the vectors $||\mathbf{v}_{i}||$ that span the
solution of the problem is bounded by Corollary 1. Therefore,

$\textnormal{det}(\mathbf{G}(\mathbf{v}_{1},...,\mathbf{v}_{K}))\leq\left(\frac{4}{3}+\varepsilon\right)^{K(N-1)}\textnormal{vol}(\mathcal{L})^{2K}.$
(26)

∎

Figure 4: The number of occurrences (left y-axis) and probability (right
y-axis) represented by the blue bars for each eigenvalue of the Hamiltonian in
Eq. (10) for a 3D lattice. The number of layers increases from left to right
with values set to $p=0,1,3,5$. The figures include the average energy
calculated from $10,000$ samples. The red dashed line points out the location
of the solution of the $K$-DSP equivalent to the densest sub-lattice. In the
top subplots it has been used the 3D good basis as input, while in the bottom
ones the input is a worse basis achieved when multiplying the good basis by a
unimodular matrix.

##  IV Experimental results

In this section, we present the results obtained after running a quantum
emulation of the QAOA algorithm on a classical computer to discuss the
performance of the $K$-DSP quantum solver for $K=2$. While these results are
low-dimensional, they are illustrative of what we can obtain in higher
dimensions. The results are presented for $N=3$ and $N=4$, as a function of
$p$ and the quality of the bases. Note that, relevant lattices in cryptography
have dimensions up to $400$. However, the rank of the input lattices has been
limited to $4$, since the number of qubits scales as $O(KN^{2})$, as shown in
Theorem 1. Thus, we fix the number of qubits per qudit to $2$.

Theorem 1 and Lemma 6 have been proven for LLL-reduced input bases.
Nevertheless, for experiments in low-dimensional lattices (therefore
classically simulable), we create input bases in a different manner, as for
low dimensions LLL returns trivially short bases which are not illustrative of
the capabilities of the quantum $K$-DSP algorithm. Instead, we first generate
short bases, then we scramble them by multiplying with random unimodular
matrices. In essence, we make the short basis slightly worse for the
simulations. The effect is that the optimal solutions we seek from the
algorithm are not trivial ones.

Although we evaluate the spatial scaling performance of the QAOA for the
$2$-DSP, it is not possible to extrapolate the success probability heuristic
to cryptographically relevant dimensions, though applying Grover search to the
search space does give some complexity scaling.

Figure 5: The number of occurrences (left y-axis) and probability (right
y-axis) represented by the blue bars for each eigenvalue of the Hamiltonian in
Eq. (10) for a 4D lattice. The number of layers increases from left to right
with values set to $p=0,1,3,5$. The figures include the average energy
calculated from $10,000$ samples. The red dashed line points out the location
of the solution of the $K$-DSP equivalent to the densest sub-lattice. In the
top subplots it has been used the 4D good basis as input, while in the bottom
ones the input is a worse basis achieved when multiplying the good basis by a
unimodular matrix.

In Fig. 4 we present the histograms obtained after training our quantum
algorithm using the _Keras_ library for the classical optimization of the cost
function described in Eq. (6) for $N=3$ and for different values of $p$.
First, the QAOA was trained using the expectation value of the energy as the
cost function. Then, we drew $10,000$ samples, which were measured in the $Z$
basis. The top row figures in Fig. 4 show the results when using a
$3$-dimensional short basis that defines the integer lattice. In contrast, the
bottom row plots in Fig. 4 exhibit the outcomes when the short basis was
multiplied by a unimodular matrix to obtain a lower quality basis (long basis)
for the same lattice as input.

Recall that, classically, it is more challenging to find the solutions for the
$K$-DSP problem when given bad input bases. The difficulty of the QAOA in
finding ground state solutions increases with the number of qubits due to the
exponentially increasing search space. Nevertheless, as the formulation for
the ground state penalization has not been implemented, the outputs contain
trivial solutions (i.e. the zero vector or linearly dependent vectors) which
correspond to the lowest energy states.

In both top and bottom sets of histograms in Fig. 4, the $x$-axis depicts the
covolumes squared of the sub-lattices, which are equivalent to the eigenvalues
of the Hamiltonian in Eq. (10). The blue bars represent the number of
occurrences of the covolumes squared after 10,000 samples in the left
$y$-axis, and the equivalent probability (occurrences divided by 10,000) in
the right-hand $y$-axis. The thin red dashed line shows the location of the
state that corresponds to the densest sub-lattice. The $x$-axis has been
truncated and so a small number of very high energy results are not shown in
order to improve readability of the lower energy samples. The number of layers
increases from left to right and the left-hand subplot in each row ($p=0$)
corresponds to uniform random sampling from the search space, thus
representing a benchmark against which the nonzero $p$ can be compared.

Analyzing the results, we can observe that in both sets the average energy of
the system decreases with $p$ as expected (from 13.16 at $p=0$ to 5.41 at
$p=5$ for the canonical basis, and from 28.46 to 18.32 for the worse basis).
In the top row figures, the average expected value of the energy has been
reduced by $60\%$, while in the bottom ones only by $35\%$. This shows that
the algorithm’s performance is notably enhanced when using better bases. This
underscores the importance of classical preprocessing through LLL-reduction in
cases where the algorithm is executed on more challenging lattices. The trend
is also visible on the blue bars, since the probability mass is more
concentrated to the left-hand side of the subplots for the higher $p$ values.
In this way, the ground state reaches the highest probability among all
possible solutions for $p=5$ in both the top and bottom subplots. At $p=5$,
the histograms exhibit a distribution similar to the Gibbs distribution [47],
where the number of occurrences decreases with the energy of the different
eigenvalues.

Notice that, while for good bases almost all the data is concentrated in the
first 10 excited states, for bad bases the occurrences are more evenly
distributed across the different bins, which involves a reduction of the
number of occurrences in respect the top row figures for each state.
Therefore, it is easier for the algorithm to find low energy solutions when
the input consists of short and close to orthogonal vectors, as it clearly
presents better performance in this situation. Nevertheless, the ideal QAOA
output would consist in obtaining the ground state with probability $1$ (the
adiabatic limit), represented by a blue bar of height $10,000$ at the $0$
value on the $x$-axis. This would also be the ideal scenario for $K$-DSP when
ground-state penalization is implemented.

In the same way as for $N=3$, in Fig. 5, we present the histograms obtained
when using as input a $4$-dimensional good basis in the right hand-side
figure, and a bad basis in the left hand-side figure. The $x$-axis has also
been truncated to enhance the legibility of the data.

The behavior is quite similar to the one in Fig. 4: the average energy of the
system decreases with $p$ in both sets, being lower for the top row histograms
than for the bottom set at each $p$. The occurrences at high-energy states
decreases as $p$ increases, while low energy configurations become more
common. The taller blue bars on the left side of the subplots at higher $p$
indicate higher probability density in this region. As was observed in Fig. 4,
the outputs are less concentrated around low energy values for the bad bases.

Nevertheless, noticeable differences arise when considering different
dimensions of the input basis. Firstly, since solving the $2$-DSP using a
$4$-dimensional basis requires a larger search space, it results in a more
complex QAOA circuit. The results for $N=4$ have been obtained using $16$
qubits, compared to $12$ qubits for $N=3$. In Appendix C, we can observe that
the QAOA circuit is relatively complex even for a 6-qubit system. For
4-dimensional good bases, the improvement in getting low energy configurations
when increasing $p$ is more modest than for 3-dimensional good bases, while
for 4-dimensional bad bases is barely discernible.

We can zoom in on the results by analyzing the probability for low energy
configurations, and comparing their behavior with increasing $p$. The
probability of obtaining states in ranges
$\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq 5,10,20$ is represented in Tab.
1. We show the probability with respect to $p$ and the dimension of the input
basis, as well as its quality.

The table illustrates that, increasing the number of layers from $p=1$ to
$p=5$ in all cases, enhances the probability to obtain low energy states.
Notice that, when using $3$-dimensional good bases, we obtain the best
performance of our quantum solver since the probability goes from 0.40 to 0.50
for $\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq 5$ and from 0.81 to 0.88 for
$\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq 20$. This means that in the range
$\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq 20$, the $81\%$-$88\%$ of the
outcomes are found within this low energy range versus the $10\%-20\%$
obtained between $20\leq\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq 261$.

Still, for bad bases, the impact of increasing the number of layers on the
probability of obtaining low energy states is significantly lower. The worst
case performance is found for a $4$-dimensional bad basis where only
$26\%-30\%$ are within the range $\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq
20$. This likely indicates that much higher depths are required to see the
same improvements, which would imply that any classical LLL-type preprocessing
could reduce the work and improve the performance of the quantum $K$-DSP
algorithm.

For bad bases, the probability at each $p$ is approximately 0.1 lower compared
to good bases. This behavior was expected because the average covolume of a
sub-lattice when randomly sampled will be higher for bad input bases and also
the integer values that represent the coefficients, both introducing
additional costs.

Range | Layers | $\mathbf{N=3}$ | $\mathbf{N=4}$
---|---|---|---
|  | good | bad | good | bad
| 1 | 0.399 | 0.319 | 0.215 | 0.068
$\textnormal{vol}(\hat{\mathcal{L}})^{2}\leq 5$ | 3 | 0.429 | 0.325 | 0.236 | 0.072
| 5 | 0.499 | 0.342 | 0.264 | 0.090
| 1 | 0.651 | 0.475 | 0.349 | 0.123
$\textnormal{vol}(\hat{\mathcal{L}})^{2}\leq 10$ | 3 | 0.675 | 0.480 | 0.363 | 0.130
| 5 | 0.737 | 0.501 | 0.379 | 0.159
| 1 | 0.812 | 0.676 | 0.595 | 0.257
$\textnormal{vol}(\hat{\mathcal{L}})^{2}\leq 20$ | 3 | 0.841 | 0.673 | 0.606 | 0.260
| 5 | 0.881 | 0.689 | 0.668 | 0.302
Table 1: Probability of obtaining low energy configurations within the ranges
$\textnormal{vol}^{2}(\mathcal{\hat{L}})\leq 5,10,20$ as a function of the
number of layers $p$, the dimension $N$, and the quality of the input basis
for 3D and 4D integer lattices.

###  IV.1 Algorithm scaling

Here, we discuss the running time of our quantum algorithm and the iterations
required for convergence during the training of the QAOA across various values
of $p$. The results depicted in Fig. 6 were derived from averaging the results
after reiterating six times the QAOA training, generating $10,000$ samples in
two distinct dimensions: $N=3$ (represented by blue dots) and $N=4$
(represented by red squares). Furthermore, we include the results obtained
when using as input good bases (depicted by dashed lines), and when
considering bad bases as the input of the algorithm (showed in solid lines).
The $y$-axis in both figures is on a logarithmic scale.

The top figure in Fig. 6 illustrates the running time for the four cases. The
bottom figure of Fig. 6 shows the number of iterations required to reach
convergence for $3$-dimensional and $4$-dimensional integer lattices, using
good and bad bases as inputs.

In the top subplot of Fig. 6, we can observe that the running time of the QAOA
increases exponentially with the circuit depth $p$, and with the dimension $N$
of the input basis (as each line for $4$D bases is sits around one order of
magnitude higher than the same line for $3$D bases). Notice that, as the value
of $p$ increases, the slopes that represent the data for good input bases
remain constant between the two, and also between the $3$-dimensional bad
basis case. However, for $4$-dimensional bad bases the slope appears to differ
from the others with increasing $p$.

While it is not possible to extrapolate based upon these heuristic results,
they reflect the widely known fact that training VQA’s becomes expensive fast
as the system complexity grows.

Figure 6: Scaling behavior of QAOA for the $2$-DSP. The running time of the
algorithm in logarithmic scale is represented in the top figure for a 3D (in
blue dots) and a 4D (in red squares) lattice described by good bases (in
dashed lines), and bad bases (in solid lines). In the bottom plot we show the
number of epochs in logarithmic scale required to train the QAOA to obtain the
optimal parameters for the parameterized quantum circuit.

##  V Conclusions

While SVP is a widely studied problem in lattice literature, and is closely
linked to recently standardized cryptosystems such as Kyber, Dilithium and
Falcon [8, 10], its generalization, $K$-DSP has remained much less tested. Due
to the more general structure of $K$-DSP, further examination may enable
deeper insights into the hardness of lattice problems.

The work presented here serves as a platform to enable further exploration of
this problem, and gives some indication of the complexity underlying the
structure of mathematical lattices. The formulation of the $K$-DSP
Hamiltonian, which becomes extremely complex even for small systems as in
Appendix C, serves as a tool with which we can probe the problem from a
quantum angle.

The bounding of the search space for the algorithm defined naturally lead to a
Grover-based quantum time complexity, even if no such result exists for QAOA
or AQC-based applications of the Hamiltonian defined here. We showed how to
incorporate such a Groverized $K$-DSP search under certain conditions into a
global hybrid algorithm, however we believe that with stronger conditions on
input bases, and reduced spatial requirements, future works could investigate
faster hybrid quantum/classical algorithms for tackling $K$-DSP.

The experimental results presented demonstrate the ability of our quantum
routine to sample dense lattices in low dimensions, but in order for future
versions to be of practical use, many more tricks from state-of-the-art QAOA
literature would need to be applied, such as improved cost functions like CVaR
[48] or Gibbs objective functions [47], and parameter initialization [49, 50].
Furthermore, for high $K$, the many-body $Z$ interactions present in the
Hamiltonians will require expensive decompositions in order to implement on
any future architectures [51], or architectures will have to adapt to be more
accommodating to many-body interactions [52, 53, 54]. This ‘Hamiltonian
engineering’, whether directly of the $K$-DSP Hamiltonian defined here or via
construction of new Hamiltonians is thus another area for future work both
from the quantum lattice algorithm, and the hardware design angles.

###### Acknowledgements.

We thank Martin R. Albrecht for introducing us to this problem, and Miloš
Prokop for the suggestions provided during the Hamiltonian formulation. We
also thank Martin Ganahl and Rishi Sreedhar for discussions regarding the QAOA
simulation, and Stefan Leichenauer for ideas on ground state penalization.

## References

  * Shor [1994] P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in  _Proceedings 35th Annual Symposium on Foundations of Computer Science_ (1994) pp. 124–134.
  * Rivest  _et al._ [1978] R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21, 120–126 (1978).
  * Han [2004] Elliptic curve arithmetic, in  _Guide to Elliptic Curve Cryptography_ (Springer New York, New York, NY, 2004) pp. 75–152.
  * Micciancio and Regev [2009] D. Micciancio and O. Regev, Lattice-based cryptography, in  _Post-Quantum Cryptography_, edited by D. J. Bernstein, J. Buchmann, and E. Dahmen (Springer Berlin Heidelberg, Berlin, Heidelberg, 2009) pp. 147–191.
  * Alagic  _et al._ [2020] G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, _et al._ , Status report on the second round of the nist post-quantum cryptography standardization process, US Department of Commerce, NIST 2 (2020).
  * Regev [2009] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM 56, 10.1145/1568318.1568324 (2009).
  * Ajtai [1996] M. Ajtai, Generating hard instances of lattice problems (extended abstract), in  _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_, STOC ’96 (Association for Computing Machinery, New York, NY, USA, 1996) p. 99–108.
  * Bos  _et al._ [2018] J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehle, Crystals - kyber: A cca-secure module-lattice-based kem, in  _2018 IEEE European Symposium on Security and Privacy_ (2018) pp. 353–367.
  * Ducas  _et al._ [2018] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé, Crystals-dilithium: A lattice-based digital signature scheme, IACR Transactions on Cryptographic Hardware and Embedded Systems 2018, 238–268 (2018).
  * Fouque  _et al._ [2018] P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, Z. Zhang, _et al._ , Falcon: Fast-fourier lattice-based compact signatures over ntru, Submission to the NIST’s post-quantum cryptography standardization process 36, 1 (2018).
  * Rankin [1955] R. A. Rankin, The closest packing of spherical caps in n dimensions, Glasgow Mathematical Journal 2, 139–144 (1955).
  * Hollanti  _et al._ [2008] C. Hollanti, J. Lahtonen, and H.-f. Lu, Maximal orders in the design of dense space-time lattice codes, IEEE Transactions on Information Theory 54, 4493 (2008).
  * Gusev  _et al._ [2023] V. V. Gusev, D. Adamson, A. Deligkas, D. Antypov, C. M. Collins, P. Krysta, I. Potapov, G. R. Darling, M. S. Dyer, P. Spirakis, _et al._ , Optimality guarantees for crystal structure prediction, Nature 619, 68 (2023).
  * Lenstra  _et al._ [1982] A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Mathematische annalen 261, 515 (1982).
  * Pohst [1981] M. Pohst, On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications, SIGSAM Bull. 15, 37–44 (1981).
  * Kannan [1983] R. Kannan, Improved algorithms for integer programming and related lattice problems, in  _Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing_, STOC ’83 (Association for Computing Machinery, New York, NY, USA, 1983) p. 193–206.
  * Gama  _et al._ [2010] N. Gama, P. Q. Nguyen, and O. Regev, Lattice enumeration using extreme pruning, in  _Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques_, Lecture Notes in Computer Science, Vol. 6110 (Springer, 2010) pp. 257–278.
  * Preskill [2018] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Bharti  _et al._ [2022] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, Noisy intermediate-scale quantum algorithms, Reviews of Modern Physics 94, 10.1103/revmodphys.94.015004 (2022).
  * Cerezo  _et al._ [2021] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nature Reviews Physics 3, 625 (2021).
  * [21] D. Dadush and D. Micciancio, Algorithms for the densest sub-lattice problem, in  _Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_, pp. 1103–1122, https://epubs.siam.org/doi/pdf/10.1137/1.9781611973105.79 .
  * Joseph  _et al._ [2020] D. Joseph, A. Ghionis, C. Ling, and F. Mintert, Not-so-adiabatic quantum computation for the shortest vector problem, Physical Review Research 2, 10.1103/physrevresearch.2.013361 (2020).
  * Joseph  _et al._ [2021] D. Joseph, A. Callison, C. Ling, and F. Mintert, Two quantum ising algorithms for the shortest-vector problem, Physical Review A 103, 10.1103/physreva.103.032433 (2021).
  * Albrecht  _et al._ [2023] M. R. Albrecht, M. Prokop, Y. Shen, and P. Wallden, Variational quantum solutions to the shortest vector problem, Quantum 7, 933 (2023).
  * Zhu  _et al._ [2022] Y. R. Zhu, D. Joseph, C. Ling, and F. Mintert, Iterative quantum optimization with an adaptive problem hamiltonian for the shortest vector problem, Phys. Rev. A 106, 022435 (2022).
  * Joseph  _et al._ [2022] D. Joseph, A. J. Martinez, C. Ling, and F. Mintert, Quantum mean-value approximator for hard integer-value problems, Physical Review A 105, 10.1103/physreva.105.052419 (2022).
  * Dable-Heath  _et al._ [2023] E. Dable-Heath, L. Casas, C. Porter, F. Mintert, and C. Ling, Quantum algorithmic solutions to the shortest vector problem on simulated coherent ising machines (2023), arXiv:2304.04075 [quant-ph] .
  * Schirman  _et al._ [2023] E. Schirman, C. Ling, and F. Mintert, Finding short vectors in structured lattices with reduced quantum resources (2023), arXiv:2307.12047 [quant-ph] .
  * Grover [1996] L. K. Grover, A fast quantum mechanical algorithm for database search (1996), arXiv:quant-ph/9605043 [quant-ph] .
  * Kitaev [1995] A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem (1995), arXiv:quant-ph/9511026 [quant-ph] .
  * Chi-Fang  _et al._ [2023a] Chi-Fang, Chen, M. J. Kastoryano, F. G. S. L. Brandão, and A. Gilyén, Quantum thermal state preparation (2023a), arXiv:2303.18224 [quant-ph] .
  * Chi-Fang  _et al._ [2023b] Chi-Fang, Chen, A. M. Dalzell, M. Berta, F. G. S. L. Brandão, and J. A. Tropp, Sparse random hamiltonians are quantumly easy (2023b), arXiv:2302.03394 [quant-ph] .
  * Minkowski [1910] H. Minkowski,  _Geometrie der zahlen_ (BG Teubner, 1910).
  * Ajtai [1998] M. Ajtai, The shortest vector problem in l2 is np-hard for randomized reductions (extended abstract), in  _Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing_, STOC ’98 (Association for Computing Machinery, New York, NY, USA, 1998) p. 10–19.
  * Gama  _et al._ [2006] N. Gama, N. Howgrave-Graham, H. Koy, and P. Q. Nguyen, Rankin’s constant and blockwise lattice reduction, in  _Advances in Cryptology - CRYPTO 2006_, edited by C. Dwork (Springer Berlin Heidelberg, Berlin, Heidelberg, 2006) pp. 112–130.
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications 9, 10.1038/s41467-018-07090-4 (2018).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph] .
  * Farhi  _et al._ [2015] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem (2015), arXiv:1412.6062 [quant-ph] .
  * Kadowaki and Nishimori [1998] T. Kadowaki and H. Nishimori, Quantum annealing in the transverse ising model, Physical Review E 58, 5355 (1998).
  * Kempe  _et al._ [2006] J. Kempe, A. Kitaev, and O. Regev, The complexity of the local hamiltonian problem, SIAM Journal on Computing 35, 1070 (2006).
  * Note [1] An alternative characterization of gap that can be found in the literature is between the successive minima of the lattice, when there exists an index $p$ s.t $\lambda_{p+1}(L)\gg\lambda_{p}(L)$. A lattice that has a gap larger than $O(N^{1/2})$ according to one definition has a gap also with the other definition and vice versa.
  * Korkine and Zolotareff [1877] A. Korkine and G. Zolotareff, Sur les formes quadratiques positives, Mathematische Annalen 11, 242 (1877).
  * Hoffstein  _et al._ [1998] J. Hoffstein, J. Pipher, and J. H. Silverman, Ntru: A ring-based public key cryptosystem, in  _International algorithmic number theory symposium_ (Springer, 1998) pp. 267–288.
  * Higgott  _et al._ [2019] O. Higgott, D. Wang, and S. Brierley, Variational quantum computation of excited states, Quantum 3, 156 (2019).
  * Kempe  _et al._ [2005] J. Kempe, A. Kitaev, and O. Regev, The complexity of the local hamiltonian problem (2005), arXiv:quant-ph/0406180 [quant-ph] .
  * Nguyen [2009] P. Q. Nguyen, Hermite’s constant and lattice algorithms, in  _The LLL Algorithm: Survey and Applications_ (Springer, 2009) pp. 19–69.
  * Li  _et al._ [2020] L. Li, M. Fan, M. Coram, P. Riley, and S. Leichenauer, Quantum optimization with a novel gibbs objective function and ansatz architecture search, Physical Review Research 2, 10.1103/physrevresearch.2.023074 (2020).
  * Barkoutsos  _et al._ [2020] P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, Improving variational quantum optimization using CVaR, Quantum 4, 256 (2020).
  * Sack and Serbyn [2021] S. H. Sack and M. Serbyn, Quantum annealing initialization of the quantum approximate optimization algorithm, Quantum 5, 491 (2021).
  * Wauters  _et al._ [2020] M. M. Wauters, G. B. Mbeng, and G. E. Santoro, Polynomial scaling of the quantum approximate optimization algorithm for ground-state preparation of the fully connected $p$-spin ferromagnet in a transverse field, Phys. Rev. A 102, 062404 (2020).
  * Boothby  _et al._ [2020] K. Boothby, P. Bunyk, J. Raymond, and A. Roy, Next-generation topology of d-wave quantum processors (2020), arXiv:2003.00133 [quant-ph] .
  * Jordan and Farhi [2008] S. P. Jordan and E. Farhi, Perturbative gadgets at arbitrary orders, Physical Review A 77, 10.1103/physreva.77.062329 (2008).
  * Chancellor  _et al._ [2017] N. Chancellor, S. Zohren, and P. A. Warburton, Circuit design for multi-body interactions in superconducting quantum annealing systems with applications to a scalable architecture, npj Quantum Information 3, 10.1038/s41534-017-0022-6 (2017).
  * Leib  _et al._ [2016] M. Leib, P. Zoller, and W. Lechner, A transmon quantum annealer: Decomposing many-body ising constraints into pair interactions (2016), arXiv:1604.02359 [quant-ph] .

##  Appendix A Extended Hamiltonian formulation

For the purpose of the QAOA simulation, the dimension of the sub-lattice that
we wanted to find $K$ was fixed to 2. However, it can also be calculated the
expression for $K=3$. In this context, the Gramian (equivalent to the squared
covolume of the sub-lattice) is spanned by the basis
$\hat{\mathbf{B}}=(\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3})$ can be
written as

$\textnormal{det}(\mathbf{G}(\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3}))=\begin{vmatrix}\langle\mathbf{v}_{1},\mathbf{v}_{1}\rangle&\langle\mathbf{v}_{1},\mathbf{v}_{2}\rangle&\langle\mathbf{v}_{1},\mathbf{v}_{3}\rangle\\\
\langle\mathbf{v}_{2},\mathbf{v}_{1}\rangle&\langle\mathbf{v}_{2},\mathbf{v}_{2}\rangle&\langle\mathbf{v}_{2},\mathbf{v}_{3}\rangle\\\
\langle\mathbf{v}_{3},\mathbf{v}_{1}\rangle&\langle\mathbf{v}_{3},\mathbf{v}_{2}\rangle&\langle\mathbf{v}_{3},\mathbf{v}_{3}\rangle\end{vmatrix}.$
(27)

Considering that the three output vectors are linear combinations of the input
basis, we can express them as

$\begin{cases}\mathbf{v}_{1}=\mathbf{x}\mathbf{B}=x_{1}\mathbf{b}_{1}+...+x_{N}\mathbf{b}_{N},\\\
\mathbf{v}_{2}=\mathbf{y}\mathbf{B}=y_{1}\mathbf{b}_{1}+...+y_{N}\mathbf{b}_{N},\\\
\mathbf{v}_{3}=\mathbf{z}\mathbf{B}=z_{1}\mathbf{b}_{1}+...+z_{N}\mathbf{b}_{N}.\end{cases}$
(28)

Calculating the determinant of Eq. (27) in terms of the vectors in Eq. (28),
the cost function results in

$\displaystyle\textnormal{vol}(\mathcal{\hat{L}})^{2}$
$\displaystyle=\sum_{i,j,k,l,m,n=1}^{N}x_{i}x_{j}y_{k}y_{l}z_{m}z_{n}(\mathbf{G}_{ij}\mathbf{G}_{kl}\mathbf{G}_{mn}+$
$\displaystyle+\mathbf{G}_{ik}\mathbf{G}_{lm}\mathbf{G}_{nj}+\mathbf{G}_{im}\mathbf{G}_{kj}\mathbf{G}_{nl}-\mathbf{G}_{im}\mathbf{G}_{kl}\mathbf{G}_{nj}-$
$\displaystyle-\mathbf{G}_{ik}\mathbf{G}_{lj}\mathbf{G}_{mn}-\mathbf{G}_{ij}\mathbf{G}_{km}\mathbf{G}_{nl}).$
(29)

To construct the classical Hamiltonian, we need to substitute each coefficient
by the qudits operators $\hat{Q}^{(j)}$. Applying $H_{DSP}$ over a
configuration of qubits, each operator will return the value of the
corresponding coefficient and in this way, they will output the covolume
squared of the sub-lattice which is an eigenvalue of the problem Hamiltonian
and the sub-lattice, defined by the grid of qubits, as the eigenvector.

##  Appendix B Bounds on the number of qubits for HKZ-reduced basis

Considering that we have an extremely reduced input basis, the number of
qubits that suffices to find an exact solution to the $K$-DSP can be reduced.

######  Theorem 3.

(Bound on the number of qubits). Let $N$-dimensional lattice $\mathcal{L}$ be
the input to the quantum algorithm for the $K$-DSP as the span of a gap-free
HKZ-reduced basis $\mathbf{B}=(\mathbf{b}_{1},...,\mathbf{b}_{N})$. Then, a
$5KN\log{N}$ qubit Hilbert search space is sufficient to ensure that at least
one exact solution of the $K$-DSP is contained.

###### Proof.

In Theorem 1 is shown that the unimodular transformation $\mathbf{X}$ is
bounded as

$||\mathbf{X}||_{\infty}\leq||\mathbf{{B}}_{out}||_{sp}||\mathbf{B}_{in}^{-1}||_{sp},$
(30)

where $\mathbf{{B}}_{in}$ and $\mathbf{{B}}_{out}$ correspond to the input
basis and the output basis, respectively.

Let the input be a gap-free HKZ-reduced basis [42]. Hence, the length of the
vectors is bounded by

$\displaystyle|\mathbf{b}_{i}|^{2}\leq\frac{i+3}{4}\lambda_{i}(\mathcal{L})^{2}$
(31)

When allowing for an SVP oracle for the preprocessing step, we ensure that the
input and output basis are gap-free. Therefore, the successive minima
$\lambda_{i}(\mathcal{L})$ of a lattice $\mathcal{L}$ are related as
$\lambda_{1}(\mathcal{L})\leq\lambda_{2}(\mathcal{L})\leq\ldots\leq\lambda_{N}(\mathcal{L})\leq\sqrt{N}\lambda_{1}(\mathcal{L})$.
Taking the highest value for $i$ in Eq. (31) to get an upper bound we obtain

$\displaystyle|\mathbf{b}_{i}|^{2}\leq\frac{N+3}{4}N\lambda_{1}(\mathcal{L})^{2}.$
(32)

Using Minkowski’s Theorem
$\lambda_{1}(\mathcal{L})\leq\sqrt{N}\textnormal{vol}(\mathcal{L})^{1/2N}$ the
bound on the length of the basis vectors results in

$\displaystyle|\mathbf{b}_{i}|^{2}\leq\frac{N+3}{4}N^{2}\textnormal{vol}(\mathcal{L})^{1/N}.$
(33)

The result obtained in Eq. (33) can be substituted into Eq. (30), such that

$||\mathbf{X}||_{\infty}\leq
N\left(\frac{N+3}{4}\right)^{2}N^{2}=\frac{N^{5}}{16}+\frac{3N^{4}}{8}+\frac{9N^{3}}{16},$
(34)

The coefficients that describe the vectors that span the densest sub-lattice
must be bounded by $-2^{m}\leq x_{i}\leq 2^{m}-1$ for all $i=1,...,N$, where
$m$ are the qubits required to represent the coefficients $x_{i}$.
Consequently, the total number of qubits required to run the $K$-DSP quantum
solver can be expressed as

$n=K\sum_{i=1}^{N}\lfloor\log{2^{m}}\rfloor\leq K\log{\prod_{i=1}^{N}2^{m}}.$
(35)

Using the relation in Eq. (34), we can write the inequality

$\displaystyle\prod_{i=1}^{N}2^{m}\leq$
$\displaystyle\prod_{i=1}^{N}\left(\frac{N^{5}}{16}+\frac{3N^{4}}{8}+\frac{9N^{3}}{16}\right)=$
$\displaystyle=\left(\frac{N^{5}}{16}+\frac{3N^{4}}{8}+\frac{9N^{3}}{16}\right)^{N}$
(36)

Thus, the upper bounds for the number of qubits results in

$n\leq
K\log{\left(\frac{N^{5}}{16}+\frac{3N^{4}}{8}+\frac{9N^{3}}{16}\right)^{N}},$
(37)

which implies that the quantum algorithm for the $K$-DSP requires
$O\left(5KN\log N\right)$ qubits. ∎

##  Appendix C QAOA circuit diagram

In Fig. 7 we show an illustration of a simple QAOA circuit generated using a
_Cirq_ feature called _SVGCircuit_ , used to display quantum circuits. The
circuit exemplifies the complexity of the problem, since a substantial amount
of gates are already required to implement the QAOA for $K=2$, $N=3$, and only
one qubit per qudit and one layer ($p=1$). The problem Hamiltonian employed
for the QAOA simulation is similar but more complex than the one presented in
Eq. (6).

The first logic gate applied to all the qubits in Fig. 7 is the Hadamard gate,
which generates a superposition of all possible states that can be created
with the available qubits. The rest of the quantum logic gates represent the
application of the problem operator and the mixer operator over the
superposition state. The last line of the circuit represents the measurements
that are performed at the end, which will be fed to the classical optimization
process in which the QAOA parameters are updated.

Figure 7: A minimal example of the QAOA circuit for the $K$-DSP for $K=2$ and
$N=3$ with 1 qubit per qudit and fixing the circuit depth to $p=1$. This is a
6-qubit system ($K\times N\times 1$) and the circuit is hence presented in
6-line stanzas.