Major and Classification
Electrical Engineering
Faculty Mentor
Federico Spedalieri, Ph.D., Department of Electrical Engineering
Department
Viterbi School of Engineering
Research Gateway Project
“NP-Hard Graph Partitioning: D-WAVE Implementation”
Project Abstract
This study involved implementing the NP-Hard Graph Partitioning problem onto the D-WAVE Two (DW2) programmable quantum annealing processor, to search for quantum speedup and improvement in solutions over classical (non-quantum) heuristic algorithms. NP problems belong to the Non-deterministic in Polynomial Time set; suggesting they are computationally infeasible. NP-Hard problems are known to be at least as hard as any NP problem. The goal of Graph Partitioning is to divide a graph (or rather network) of nodes connected by a set of edges into two equally sized groups while minimizing the cut size, the interconnection between the two groups. Areas of applications for Graph Partitioning include social sciences (social networks) and economic (market modeling) computations as well as in communications and network design. The DW2’s native problem is an Ising model, so in order to embed the problem onto the chip an Ising formulation of the problem is required. I studied the effect of varying the Ising formulation parameters and problem size in order to find improvement in performance. I found that the parameters did not affect performance in small graphs and that the DW2 outperformed my attempts at providing optimal solution. Furthermore, I discuss the limitations of such conclusions.