Hard combinatorial problems and minor embeddings on lattice graphs

Abstract

Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms: Computational problems are formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants, and the interaction graph of the QUBO needs an effective minor embedding into a two-dimensional non-planar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges for present-day hardware. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on future quantum annealing hardware. While we focus on embedding problems onto Chimera lattices, the techniques we use, along with their limitations, generalize to any non-planar lattice graph.