There exist several quantum algorithms with a proven quantum advantage. One of them is the Grover Search Algorithm [1], which finds an item in an unordered database with quadratic speed-up. By mapping optimization problems to search problems, one is able to harvest this quantum advantage. A particularly interesting NP-hard problem explored in the project QCMobility is the lock scheduling problem. Here we aim at deriving an optimal schedule to lock the incoming ships, while minimizing for example waiting times or water consumption. In this poster, we investigate the solution of the lock scheduling problem. For this purpose, we formulate it as a quadratic unconstrained binary optimization (QUBO) problem and find the global optimum with Grover Adaptive Search [2]. Our results are obtained on quantum hardware simulators. [1] L. K. Grover, Proc. 28th Annu. ACM Symp. Theory Comput., 212 - 219 (1996). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005).
There exist several quantum algorithms with a proven quantum advantage. One of them is the Grover Search Algorithm [1], which finds an item in an unordered database with quadratic speed-up. By mapping optimization problems to search problems, one is able to harvest this quantum advantage. A particularly interesting NP-hard problem explored in the project QCMobility is the lock scheduling problem. Here we aim at deriving an optimal schedule to lock the incoming ships, while minimizing for example waiting times or water consumption. In this poster, we investigate the solution of the lock scheduling problem. For this purpose, we formulate it as a quadratic unconstrained binary optimization (QUBO) problem and find the global optimum with Grover Adaptive Search [2]. Our results are obtained on quantum hardware simulators. [1] L. K. Grover, Proc. 28th Annu. ACM Symp. Theory Comput., 212 - 219 (1996). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005).
Typical industry-related optimizations, like routing, packing, or scheduling, can be reformulated as a quadratic unconstrained binary optimization (QUBO) problem [1]. In the fault-tolerant quantum computing era, a promising approach to solve these problems is the Grover Adaptive Search [2]. The Grover Adaptive Search is able to solve QUBOs with a quadratic speed-up in comparison to classical algorithms. Here different Grover runs are chained together in order to identify the optimal solution. In this poster, we present a comprehensive guide with intuitive visuals, a theoretical background and a walkthrough to help non-expert to apply the Grover Adaptive Search. In particular, we demonstrate how to parse the QUBOs into a Grover oracle - the quantum dictionary [3] - and what this implies for the different quantum registers involved. [1] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, J. Comb. Optim. 28, 58 (2014). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005). [3] A. Gilliam, C. Venci, S. Muralidharan, V. Dorum, E. May, R. Narasimhan, and C. Gonciulea, arXiv:1907.11513 (2019).
Despite quantum computing is revealing an increasingly promising technology that has the potential to introduce a significant speed-up in many areas of computation, the number of problems that it can represent and solve is currently rather limited. Therefore, one of the current challenges faced by the quantum computing community is to broaden the class of problems that can be tackled. Among these problems, scheduling problems are a class of particularly interesting and hard combinatorial problems; in this paper, we present a novel solution for representing and solving the Flexible Open Shop Scheduling Problem (FOSSP) to optimality by minimizing the makespan. We firstly present a compact formulation of this problem as a Quadratic unconstrained binary optimization (QUBO), which can be used to solve this problem with a quantum annealer. Then, we proceed to the Quantum Approximate Optimization Algorithm (QAOA) problem formulation, thus producing both the cost and mix Hamiltonians related to the problem. From the Hamiltonians, we provide the complete description of the quantum circuit that can be used to tackle the FOSSP within the QAOA framework. This second approach can be used to solve the optimization problem with a general-purpose quantum gate-based hardware.
In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.
Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.
Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.
The application of quantum algorithms on some problems in NP promises a significant reduction of time complexity. This thesis uses Grover’s Algorithm, originally designed to search an unstructured database with quadratic speedup, to find valid solution bit-strings to the NP-hard personnel scheduling problem. Under consideration of various hard and soft constraints, we implement this by using the IBMQ backend and Qiskit to optimize the German Aerospace Center’s spacecraft on-call operator scheduling. We seek an optimal assignment for 52 operators to 17 positions over a period of 180 days under constraints on schedule and personnel. Further, we evaluate the solution quality and compare the performance with classical and quantum alternatives. While still restricted by intermediate scale quantum devices in the near term, we explore new approaches in encoding and batching the problem to reduce the required number of qubits. In the end, a feasible near-term solution that scales well with the quantum devices of the upcoming years is presented.