Solving a Scheduling Problem for a Quantum Computing Architecture Using Constraint Programming.

Kyle E. C. Booth, Bryan O’Gorman, Jeffrey Marshall +2 more

Chia Cheng Chang, Chih-Chieh Chen, Christopher Körber +2 more

While quantum computing proposes promising solutions to computational problems not accessible with classical approaches, due to current hardware constraints, most quantum algorithms are not yet capable of computing systems of practical relevance, and classical counterparts outperform them. To practically benefit from quantum architecture, one has to identify problems and algorithms with favorable scaling and improve on corresponding limitations depending on available hardware. For this reason, we developed an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer, and investigated problem and hardware-specific limitations. This work presents the formalism of how to map ILP problems to the annealing architectures, how to systematically improve computations utilizing optimized anneal schedules, and models the anneal process through a simulation. It illustrates the effects of decoherence and many body localization for the minimum dominating set problem, and compares annealing results against numerical simulations of the quantum architecture. We find that the algorithm outperforms random guessing but is limited to small problems and that annealing schedules can be adjusted to reduce the effects of decoherence. Simulations qualitatively reproduce algorithmic improvements of the modified annealing schedule, suggesting the improvements have origins from quantum effects.

Sizhuo Yu, Tahar Nabil

Quantum annealing is a global optimization algorithm that uses the quantum tunneling effect to speed-up the search for an optimal solution. Its current hardware implementation relies on D-Wave’s Quantum Processing Units, which are limited in terms of number of qubits and architecture while being restricted to solving quadratic unconstrained binary optimization (QUBO) problems. Consequently, previous applications of quantum annealing to real-life use cases have focused on problems that are either native QUBO or close to native QUBO. By contrast, in this paper we propose to tackle inequality constraints and non-quadratic terms. We demonstrate how to handle them with a realistic use case-a bus charging scheduling problem. First, we reformulate the original integer programming problem into a QUBO with the penalty method and directly solve it on a D-Wave machine. In a second approach, we dualize the problem by performing the Hubbard-Stratonovich transformation. The dual problem is solved indirectly by combining quantum annealing and adaptive classical gradient-descent optimizer. Whereas the penalty method is severely limited by the connectivity of the realistic device, we show experimentally that the indirect approach is able to solve problems of a larger size, offering thus a better scaling. Hence, the implementation of the Hubbard-Stratonovich transformation carried out in this paper on a scheduling use case suggests that this approach could be investigated further and applied to a variety of real-life integer programming problems under multiple constraints to lower the cost of mapping to QUBO, a key step towards the near-term practical application of quantum computing.

Cynthia A. Phillips, Robert D. Carr, Anand Ganti

Marcos Yukio Siraichi

In May of 2016, IBM Research has made a quantum processor available in the cloud to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, quantum programming still lacks the compiler support that modern programming languages enjoy today. To use universal quantum computers like IBM's, programmers must design low-level circuits. In particular, they must map logical qubits into physical qubits that need to obey connectivity constraints. In this work, we shall formally introduce the qubit allocation problem and provide an exact solution to it. This optimal algorithm deals with the simple quantum machinery available today; however, it cannot scale up to the more complex architectures scheduled to appear. Thus, we will also provide heuristics to solve qubit allocation, one of which is faster, and another one that performs better than the current solutions already implemented to deal with this problem.

Gian Giacomo Guerreschi, Jongsoo Park