Accelerating large data modeling for quantum computation with GPUs

The goal of this dissertation is to introduce a new system capable of increasing the speed of the QUBO model creation, by virtue of the paradigms of GPU programming. At a time when the first Quantum Annealers broke on the scene, QUBO model was applied to solve combinatorial optimisation problems. Quantum Annealers are a type of Quantum Computers that take advantage of the natural properties of physical systems, both classical and quantum, in order to find the optimal solution of an optimisation problem described through a minimisation function. The usage of Quantum Computing techniques boosted the problem solution finding so that, at present, the bottleneck is in the creation of the model itself. The project QUBO on GPU (QoG), presented in this dissertation, aims to propose a brand new approach in building the QUBO model exploiting the GPU computation and so obtaining better performances in terms of speed to solve optimisation problems. First, we present the basics of Quantum Computing and the necessary concepts to understand the principles behind the Quantum Annealing. Subsequently we focus on Quantum Annealing and the related D-Wave's Quantum Annealer. After this QUBO model is presented by describing it in its mathematical basics and providing two modelling examples: the logic gate AND and the Map Colouring optimisation problem. An introduction to the General-purpose GPU programming will then follow, with its main paradigms and architectures and the technology being used in the project, namely CUDA. CUDA is the hardware architecture and framework software that NVIDIA introduced. The main purpose of this work is to create a QUBO model for a generic combinatorial quadratic problem as fast as possible. Since QUBO model is represented via an upper triangular matrix, the project also looks for the best solutions in order to compute and memorise a sparse matrix and how to optimise the access to its entries.