Risoluzione del Closest Vector Problem utilizzando il Quantum Annealing sul computer D-Wave®

The Closest Vector Problem (CVP) is a well-known optimization problem with applications in computational mathematics and lattice-based cryptography. It consists in finding the closest point of a lattice to a given vector that doesn’t belong to it. This problem is proven to be NP-Hard, then all the known classical algorithms are either inefficient or provide only approximated solutions. In this thesis, we first review the mapping of the CVP onto a spin glass Hamiltonian. We specifically target lattices defined in Schnorr’s mathematical framework for lattice based cryptography, and find solutions using The D-Wave® quantum annealer. The results obtained via quantum annealing are then compared to those obtained via established classical algorithms.

Il Closest Vector Problem (CVP) è un noto problema di ottimizzazione con applicazioni nella matematica computazionale e nella crittografia basata sui reticoli. Consiste nel trovare il punto di un reticolo più vicino a un vettore dato che non gli appartiene. Questo problema è dimostrato essere NP-Hard, quindi tutti gli algoritmi classici conosciuti sono inefficienti o ritornano soluzioni approssimate. In questa tesi esaminiamo innanzitutto la mappatura del CVP su un Hamiltoniano di vetro di spin. Ci concentriamo specificamente sui reticoli definiti nel quadro matematico di Schnorr per la crittografia basata su reticoli e troviamo soluzioni utilizzando il quantum annealer di D-Wave®. I risultati ottenuti sono poi comparati con quelli ottenuti utilizzando algoritmi classici.