Quantum Computing is an emerging paradigm which is gathering a lot of popularity in the current scientific and technological community. Widely conceived as the next frontier of computation, Quantum Computing is still at the dawn of its development. Thus, current solving systems suffer from significant limitations in terms of performance and capabilities. Some interesting approaches have been devised by researchers and practitioners in order to overcome these barriers, being quantum-classical hybrid algorithms one of the most often used solving schemes. The main goal of this paper is to extend the results and findings of the recently proposed hybrid Quantum Computing - Tabu Search Algorithm for partitioning problems. To do that, we focus our research on the adaptation of this method to the Asymmetric Traveling Salesman Problem. In overall, we have employed six well-known instances belonging to TSPLIB to assess the performance of Quantum Computing - Tabu Search Algorithm in comparison to QBSolv. Furthermore, as an additional contribution, this work also supposes the first solving of the Asymmetric Traveling Salesman Problem using a Quantum Computing based method. Aiming to boost whole community's research in QC, we have released the project's repository as open source code for further application and improvements.
Quantum Computing is an emerging paradigm which is gathering a lot of popularity in the current scientific and technological community. Widely conceived as the next frontier of computation, Quantum Computing is still at the dawn of its development. Thus, current solving systems suffer from significant limitations in terms of performance and capabilities. Some interesting approaches have been devised by researchers and practitioners in order to overcome these barriers, being quantum-classical hybrid algorithms one of the most often used solving schemes. The main goal of this paper is to extend the results and findings of the recently proposed hybrid Quantum Computing - Tabu Search Algorithm for partitioning problems. To do that, we focus our research on the adaptation of this method to the Asymmetric Traveling Salesman Problem. In overall, we have employed six well-known instances belonging to TSPLIB to assess the performance of Quantum Computing - Tabu Search Algorithm in comparison to QBSolv. Furthermore, as an additional contribution, this work also supposes the first solving of the Asymmetric Traveling Salesman Problem using a Quantum Computing based method. Aiming to boost whole community's research in QC, we have released the project's repository as open source code for further application and improvements.
Quantum Computing is considered as the next frontier in computing, and it is attracting a lot of attention from the current scientific community. This kind of computation provides to researchers with a revolutionary paradigm for addressing complex optimization problems, offering a significant speed advantage and an efficient search ability. Anyway, Quantum Computing is still in an incipient stage of development. For this reason, present architectures show certain limitations, which have motivated the carrying out of this paper. In this paper, we introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses. To assess the quality of our method, we have used 7 different Traveling Salesman Problem instances as benchmarking set. The obtained outcomes support the preliminary conclusion that our algorithm is an approach which offers promising results for solving partitioning problems while it drastically reduces the access to quantum computing resources. We also contribute to the field of Transfer Optimization by developing an evolutionary multiform multitasking algorithm as initialization method.
Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone is still far to demonstrate this capability except on small-sized problems. Hybrid approaches where QC and classical computing work together have shown the most potential for solving real-world scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new hybrid quantum-classical tabu search (HQTS) algorithm to solve the capacitated vehicle routing problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the traveling salesman problem (TSP) for each route as a QUBO, solved using D-Wave's Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. While different starting solution methods, including quantum-based and classical heuristics methods, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap compared to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.
At land, sea and in the air mobility and traffic management offer a vast amount of problems with a large potential of optimization with quantum computers, e.g. service scheduling, route planning, or path optimization. Many of these problems can be described at a fundamental level by the traveling salesman problem (TSP), in which the shortest route while visiting each point exactly once is to be found [1]. The TSP has already received a lot of attention in the quantum computing community, for example, implementations for adiabatic quantum annealers exist and have been tested [2,3]. We investigate the TSP with a focus on going beyond qubits by employing continuous quantum systems. Using bosonic Qiskit we simulate potential algorithms for solving the TSP and compare their performance. [1] Flood, M. M., The traveling-salesman problem. Operations research, 4(1), 61-75, (1956). [2] Martoňák, Roman, Giuseppe E. Santoro, and Erio Tosatti., Quantum annealing of the traveling-salesman problem. Physical Review E 70.5: 057701, (2004). [3] Jain, S., Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics, 646, (2021).
Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone has still been unable to demonstrate this capability except for small-sized problems. Hybrid approaches, where QC and classical computing work together, have shown the most potential for solving real-world-scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new Hybrid Quantum-classical Tabu Search (HQTS) algorithm to solve the Capacitated Vehicle Routing Problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the Traveling Salesman Problem (TSP) for each route as a Quadratic Unconstrained Binary Optimization (QUBO) and solves it using D-Wave’s Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. Across different starting solution methods, including quantum-based and classical heuristics, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap relative to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.
With the rapid onset of the Quantum Computing (QC) paradigm in the field of computer science, the QC approach could enable better outcomes to solve some of the classical problems. It is plausible to speculate that quantum computers could outperform classical computers in machine learning tasks because quantum systems exhibit peculiar patterns that conventional systems are assumed to be incapable of producing. This work introduces the QC approach to Machine Learning solutions in computer science and provides a comparison of the performances of QC-based approaches against the classical ones. In addition, an attempt to discuss the potential of QC in solving classical computer science problems such as Shor’s algorithm, the Travelling Salesman problem(TSP), and the prime factorization problem is made through the empirical study of the same.In conclusion, we analyze the outcomes of our practical investigation and devise potential improvements that can be made to the QC methods employed by the solutions.
There has never been a more exciting time for the future of quantum computing than now. Real-world quantum computing usage is now the next XPRIZE. With that challenge in mind we have explored a new approach as a hybrid quantum-classical algorithm for solving NP-Hard optimization problems. We have focused on the classic problem of the Capacitated Vehicle Routing Problem (CVRP) because of its real-world industry applications. Heuristics are often employed to solve this problem because it is difficult. In addition, meta-heuristic algorithms have proven to be capable of finding reasonable solutions to optimization problems like the CVRP. Recent research has shown that quantum-only and hybrid quantum/classical approaches to solving the CVRP are possible. Where quantum approaches are usually limited to minimal optimization problems, hybrid approaches have been able to solve more significant issues. Still, the hybrid approaches often need help finding solutions as good as their classical counterparts. In our proposed approach, we created a hybrid quantum/classical meta-heuristic algorithm capable of finding the best-known solution to a classic CVRP problem. Our experimental results show that our proposed algorithm often outperforms other hybrid approaches.