(194c) Quantum Computing Based Hybrid Quantum-Classical Solution Approach for Complex Combinatorial Optimization Problems
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 . 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 .
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 . For decomposition based solution approach, problem size limitation is an important aspect and may yield sub-optimal solutions while utilizing large computational resources . 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 . 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.
 S. Koziel and X.-S. Yang, Computational optimization, methods and algorithms. Springer, 2011.
 C. A. Mack, "Fifty Years of Moore's Law," IEEE Transactions on Semiconductor Manufacturing, vol. 24, no. 2, pp. 202-207, 2011.
 M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2010, p. 702.
 T. T. Tran et al., "A Hybrid Quantum-Classical Approach to Solving Scheduling Problems," in Symposium on Combinatorial Search, 2016.
 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.
 M. Booth, S. P. Reinhardt, and A. Roy, "Partitioning Optimization Problems for Hybrid Classical/Quantum Execution," 2017.
 "Reverse Quantum Annealing for Local Refinement of Solutions," 1701.04579.