(194c) Quantum Computing Based Hybrid Quantum-Classical Solution Approach for Complex Combinatorial Optimization Problems

Computational optimization is a ubiquitous paradigm with wide range of applications in engineering and industry, and has received tremendous attention from both academia and industry. Primary components of an optimization process are the computational modelling and search algorithms [1]. Growing demand for best optimal solution in the optimization process require the search algorithms to be efficient and computationally tractable. However, the ever-increasing complexity of structures and systems as well as the search space growing quickly with size in case of combinatorial optimization problems result in the process being more time consuming without any guarantee of an optimal solution. This problem could be handled by advancements in computers with high processing speeds, but saturation limits of Moore’s law render the possibility of rising processing speeds unlikely [2]. So, there arises a need for novel solution approaches capable of overcoming limitations of current state-of-the-art conventional classical computers.

Quantum computing is the next frontier in computation and has attracted a lot of attention from the scientific community in recent years. It provides a novel approach to help solve some of the most complex optimization problems while offering an essential speed advantage over conventional classical computers [3]. Despite the contrasting views on its viability and whether or not quantum computers can replace classical ones, there is no denying the fact that quantum computation holds the key to a new era of computing. Due to current technological limitations of the quantum computer, harnessing the complementary strengths of classical and quantum computers to solve complex real-world problems is of utmost importance [4].

In this work, we present hybrid solution approaches utilizing both quantum and classical resources. Quantum systems built by D-wave which intrinsically realize quantum annealing algorithm are used for optimization. Such quantum annealing based machines are efficient in optimizing problems by quickly searching over the solution space [5]. For decomposition based solution approach, problem size limitation is an important aspect and may yield sub-optimal solutions while utilizing large computational resources [6]. Parallelization of such techniques reduce solving time without any augmentation of obtained solution quality. The scope of hybrid quantum-classical techniques based on reverse annealing for complex combinatorial optimization problems is also demonstrated through simulations. Refinement of solutions through a local search facilitated by quantum annealing is a more sophisticated hybrid algorithm [7]. The advantages and limitations of each solving technique with respect to each other are also discussed. To illustrate this, complex combinatorial optimization problems of practical relevance such as travelling salesman, supply chain with inventory management, cell formation and portfolio optimization are solved using the mentioned quantum-classical hybrid solution techniques. The performance of these techniques is compared to that of classical deterministic solvers with respect to computation times and quality of obtained solutions. The parallelized solution approach reduces computation time substantially while compromising solution quality. The simulated reverse annealing based technique uses up much less computation time and yields best possible solutions than standalone quantum solver or a deterministic classical solver. Since quantum computers can handle binary quadratic problems only, the non-linear model in supply chain optimization is discretized through approximation. The travelling salesman, cell formation and portfolio optimization problems being integer formulations perform better than supply chain optimization for which search space rises exponentially with size, in terms of solution quality as well as computation time.

References

[1] S. Koziel and X.-S. Yang, Computational optimization, methods and algorithms. Springer, 2011.

[2] C. A. Mack, "Fifty Years of Moore's Law," IEEE Transactions on Semiconductor Manufacturing, vol. 24, no. 2, pp. 202-207, 2011.

[3] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2010, p. 702.

[4] T. T. Tran et al., "A Hybrid Quantum-Classical Approach to Solving Scheduling Problems," in Symposium on Combinatorial Search, 2016.

[5] G. E. Santoro and E. Tosatti, "Optimization using quantum mechanics: Quantum annealing through adiabatic evolution," Journal of Physics A: Mathematical and General, vol. 39, 2006.

[6] M. Booth, S. P. Reinhardt, and A. Roy, "Partitioning Optimization Problems for Hybrid Classical/Quantum Execution," 2017.

[7] "Reverse Quantum Annealing for Local Refinement of Solutions," 1701.04579.