Mapping NP-Hard Problems to Restricted Adiabatic Quantum Architectures

Abstract

We introduce a framework for mapping NP-Hard problems to adiabatic quantum computing (AQC) architectures that are heavily restricted in both connectivity and dynamic range of couplings, for which minor-embedding -- the standard problem mapping method -- cannot be directly applied. Separating the mapping into two distinct stages, we introduce problem-specific reductions for both quadratic unconstrained binary optimisation (QUBO) and satisfiability (SAT) and develop the subdivision-embedding method that is suitable for directly embedding onto these heavily restricted architectures. The theory underpinning this framework provides tools to aid in the manipulation of Ising Hamiltonians for the purposes of Ising energy minimisation, and could be used to assist in developing and optimising further problem mapping techniques. For each of the problem mapping methods presented, we examine how the physical qubit count scales with problem size on architectures of varying connectivity.

arXiv comment35 pages, 28 figures

References in corpus (20)

• Ising formulations of many NP problems
• Robustness of adiabatic quantum computation
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• A practical heuristic for finding graph minors
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Adiabatic Quantum Computation in Open Systems
• Error corrected quantum annealing with hundreds of qubits
• Adiabatic Quantum Simulation of Quantum Chemistry
• Application of Quantum Annealing to Training of Deep Neural Networks
• On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
• Quantum annealing correction for random Ising problems
• Noise resistance of adiabatic quantum computation using random matrix theory
• Decoherence in a scalable adiabatic quantum computer
• Next-Generation Topology of D-Wave Quantum Processors
• Quantum annealing for the number partitioning problem using a tunable spin glass of ions
• Non-Markovian decoherence in the adiabatic quantum search algorithm
• Algorithm engineering for a quantum annealing platform
• Scalable Superconducting Architecture for Adiabatic Quantum Computation
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis