D-Wave Systems Quantum Computing : State-of-the-Art and Performance Comparison with Classical Computing

Sammanfattning: The aim of this project is to study Quantum Computing state-of-art and to compare it with classical computing methods. The research is focused on D-Wave Systems’ Quantum Computing approach, exploring its architectures: Chimera and Pegasus; tools, and its Quantum Annealing process. In order to study weaknesses and strengths of each method, the problem that has been analysed is the well-known TSP (Travelling Salesman Problem). Performance and capabilities comparison has involved four different set-ups to solve the problem: • D-Wave’s Exact solver (using CPU exclusively). • Pure QPU implementation using D-Wave’s Dimod solver. • GPU adapted parallelization of Classical Brute-force algorithm with NVIDIA CUDA API. • D-Wave’s Hybrid solver (which combines QPU together with classical techniques). The results of this project reveal that pure QPU implementation is faster than every other but only works for small examples yet, its scalability is limited by QPU architectures. QPU Hybrid solution seems to be the fastest and more scalable solution. Both CPU and GPU approaches are fast for small problems but when scaling, they have a solid limit that is impossible to break. This is due to the O(N!) complexity of the Brute-force algorithm. Comparison between Pegasus and Chimera architectures reveals that Pegasus performs much better due to the more complex topology and connectivity between their qubits.