2018/12/05 by Andrew Lucas, Lucas, Andrew
Biochemistry, Genetics and Molecular Biology · Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1812.01789
openalex publication_date 2018/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms. Firstly, computational problems must be formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants. Secondly, the interaction graph of the QUBO must have an effective minor embedding into a two-dimensional nonplanar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can be also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on next-generation hardware.