Experimental study on Quantum heuristic search in an NP-hard problem

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

Eleanor Gilbert Rieffel, Stuart Hadfield, Jiang Zhang +3 more

Mohamed El-fiky, Satoshi Ono, Shigeru Nakayama

A study on Quantum Heuristic Search (QHS) in Knapsack problem is presented. The algorithm starts with superpositions of all possible search states for the problem. It uses problem cost structure to shift the phase of the state's amplitude, and a problem independent mixing operation combines the amplitude from different states. The simulator implemented in this study has shown that QHS could shift the amplitude toward solution states on average at each step, and the comparison with conventional heuristics has revealed its search performance.

Otto Menegasso Pires, Rafael de Santiago, Jerusa Marchi

Timetabling is an NP-Hard problem that searches for periodic scheduling of events that must meet a set of hard and soft constraints. Because of the difficulty in finding an exact solution, the use of heuristics to address the problem is a common practice. When only the hard constraints are considered, the timetabling problem can be reduced to graph vertex coloring. This similarity between both problems has motivated the use of graph coloring heuristics as a means to solve the timetabling problem. We propose the use of the Quantum Approximate Optimization Algorithm as a heuristic to solve the school timetabling problem. The QAOA is a hybrid quantum-classical algorithm that can be used to address combinatorial optimization problems. We simulated QAOA in a minimal example with 42 qubits using the Ket Quantum Programming Language and our results showed that it is possible to apply QAOA to the school timetabling problem.

Pulak Ranjan Giri, V. E. Korepin

Weimin Huang, Natalie M. Isenberg, Ján Drgoňa +2 more

Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.