Quantum Annealing implementation of TSP with soft constraint and performance comparison with the latest D-Wave’s resources.
Jaime Vallejo Benítez-Cano · Hispana · 2022
The objective of this project is to check D-Wave’s evolution in one year based on previous research project [1] [2]. In order to evaluate this state-of-the-art, the three current D-Wave’s QPU topologies have been used for performance comparison. The aspects that have been studied are time performance, the correctness of results and stability of minor embedding into each type of quantum architecture. The problem that has been used as a test for this performance comparison has been the well-known Travelling Salesman Problem (TSP) with a soft constraint which is Sequential Ordering Problem (SOP). The different setups that have executed each approach are the following: - 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 current quantum resources have some limitations on their own. Using a pure QPU approach achieves no better results than current classical computation (CPU and GPU). However, its importance lies in the simultaneous usage of both quantum and classical resources to leverage the complexity burden and compensate for each other’s weaknesses. This is the quantum hybrid approach, which has proved to achieve nice results. These results took an execution time that is unfeasible for classical computing due to O(N!) complexity of Brute-force algorithms required to solve NP-hard problems like TSP. Regarding topologies, the use of a Zephyr prototype with many fewer qubits than Pegasus and Chimera devices has proven that Zephyr is a much better architecture due to the high connectivity of the qubits lattice that enables better minor-embedding, shorter execution times and more stability in the results obtained.