Hard combinatorial problems and minor embeddings on lattice graphs
arXiv:1812.01789
Abstract
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.
arXiv comment26+7 pages; 9+1 figures
References in corpus (16)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Anderson localization casts clouds over adiabatic quantum optimization
- A case study in programming a quantum annealer for hard operational planning problems
- Phase Transition in the Number Partitioning Problem
- Error corrected quantum annealing with hundreds of qubits
- Probing for quantum speedup in spin glass problems with planted solutions
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Adiabatic quantum optimization fails for random instances of NP-complete problems
- Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
- Fast clique minor generation in Chimera qubit connectivity graphs